2024/11/29 刷题记录

3251. 单调数组对的数目 II

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        vector<vector<int>> dp(nums.size() + 1, vector<int>(1002, 0));
        for (int i = 0; i <= nums[0]; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < nums.size(); i++) {
            int d = max(0, nums[i] - nums[i - 1]);
            for (int j = d; j <= nums[i]; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j - d];
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % int(1e9 + 7);
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < dp[nums.size() - 1].size(); i++) {
            sum += dp[nums.size() - 1][i];
            sum %= int(1e9 + 7);
        }
        return sum;
    }
};

3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        for(int i = 0; i < s.length(); i++){
            unordered_map<char, bool> mp;
            int t = 0;
            for(int j = i; j < s.length(); j++){
                if(!mp[s[j]]){
                    t++;
                    mp[s[j]] = true;
                    ans = max(ans, t);
                } else {
                    break;
                }
            }
        }
        return ans;
    }
};

438. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> dict;
    vector<int> current;

    bool same(){
        for(int i = 0; i < dict.size(); i++){
            if(dict[i] != current[i]) return false;
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p) {
        if(s.length() < p.length()) return {};
        dict = vector<int>(30);
        current = vector<int>(30);
        vector<int> ans;
        for(int i = 0; i < p.length(); i++){
            dict[p[i] - 'a']++;
            current[s[i] - 'a']++;
        }
        if(same()) ans.push_back(0);
        for(int i = p.length(); i < s.length(); i++){
            current[s[i] - 'a']++;
            current[s[i - p.length()] - 'a']--;
            if(same()) ans.push_back(i - p.length() + 1);
        }
        return ans;
    }
};

560. 和为 K 的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto& x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }
};

239. 滑动窗口最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, less<int>> q;
        unordered_map<int, int> ct;
        for(int i = 0; i < k; i++){
            q.push(nums[i]);
        }
        vector<int> ans;
        ans.push_back(q.top());
        for(int i = k; i < nums.size(); i++){
            ct[nums[i - k]]++;
            q.push(nums[i]);
            while(ct[q.top()]){
                ct[q.top()]--;
                q.pop();
            }
            ans.push_back(q.top());
        }
        return ans;
    }
};