2024/11/28 刷题记录

3250. 单调数组对的数目 I

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        vector<vector<int>> dp(nums.size() + 1, vector<int>(51, 0));
        for (int i = 0; i <= nums[0]; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = 0; j <= nums[i]; j++) {
                for (int k = j; k <= nums[i + 1]; k++) {
                    if (nums[i] - j >= nums[i + 1] - k) {
                        dp[i + 1][k] += dp[i][j];
                        dp[i + 1][k] %= 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;
    }
};

49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string> > ans;
        unordered_map<string, int> mp;
        unordered_map<int, vector<string> > mp_ans;
        for(int i = 0; i < strs.size(); i++){
            string newstr = strs[i];
            sort(newstr.begin(), newstr.end());
            if(mp[newstr]){
                mp_ans[mp[newstr]].push_back(strs[i]);
            } else {
                vector<string> new_v;
                new_v.push_back(strs[i]);
                mp[newstr] = mp_ans.size() + 1;
                mp_ans[mp_ans.size() + 1] = new_v;
            }
        }
        for(auto i : mp_ans){
            ans.push_back(i.second);
        }

        return ans;
    }
};

128. 最长连续序列

class Solution {
public:
    unordered_map<int, bool> init;
    unordered_map<int, int> mp;
    unordered_map<int, int> ans_mp;

    int find(int x){
        int fa = x;
        while(fa != mp[fa]){
            fa = mp[fa];
        }
        mp[x] = fa;
        return fa;
    }

    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            mp[nums[i]] = nums[i];
            ans_mp[nums[i]] = 1;
            init[nums[i]] = true;
        }
        for(int i = 0; i < nums.size(); i++){
            vector<int> fas;
            vector<int> pos;
            if(init[nums[i] - 1]) pos.push_back(nums[i] - 1);
            pos.push_back(nums[i]);
            if(init[nums[i] + 1]) pos.push_back(nums[i] + 1);
            int max_num = 0;
            int max_pos = 1e9 + 8;
            for(int i = 0; i < pos.size(); i++){
                int fa = find(pos[i]);
                if(ans_mp[fa] > max_num){
                    max_pos = fa;
                    max_num = ans_mp[fa];
                }
            }
            cout<<max_pos<<" "<<max_num<<endl;
            if(init[nums[i] - 1] && find(mp[nums[i] - 1]) != max_pos){
                ans_mp[max_pos] += ans_mp[find(mp[nums[i] - 1])];
                mp[find(mp[nums[i] - 1])] = max_pos;
            }
            if(mp[find(mp[nums[i]])] != max_pos){
                ans_mp[max_pos] += ans_mp[find(mp[nums[i]])];
                mp[find(mp[nums[i]])] = max_pos;
            }
            if(init[nums[i] + 1] && mp[find(mp[nums[i] + 1])] != max_pos){
                ans_mp[max_pos] += ans_mp[mp[find(mp[nums[i] + 1])]];
                mp[find(mp[nums[i] + 1])] = max_pos;
            }
            cout<<ans_mp[max_pos]<<endl;
            ans = max(ans, ans_mp[max_pos]);
        }
        return ans;
    }
};

283. 移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int b = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0){
                for(int j = max(i + 1, b); j < nums.size(); j++){
                    if(nums[j] != 0){
                        swap(nums[i], nums[j]);
                        break;
                    }
                    b = max(b, j);
                }
            }
        }
        return;
    }
};

11. 盛最多水的容器

两端的指针每次移动较小的那个，因为可以证明的是如果移动较大的一端，之后的任何情况都不可能比现在的情况好。

这道题最开始可以考虑暴力的情况，也就是如果全搜索，应该是两端的指针每次有两种选择，移动左边或者右边，然后再根据上面说的问题考虑是否可以剪枝。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while(l < r){
            ans = max(ans, min(height[l], height[r]) * (r - l));
            if(height[l] < height[r]){
                l = l + 1;
            } else {
                r = r - 1;
            }
        }
        return ans;
    }
};

15. 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<string, bool> st;
        unordered_map<int, int> ext;
        for (int i = 0; i < nums.size(); i++) {
            ext[nums[i]] += 1;
        }
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size(); i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.size(); j++) {
                int c = -(nums[i] + nums[j]);
                if (ext[c]) {
                    if (!((c == nums[i] || c == nums[j]) && ext[c] < 2) &&
                        !((c == nums[i] && c == nums[j]) && ext[c] < 3)) {
                        vector<int> nv;
                        nv.push_back(nums[i]);
                        nv.push_back(nums[j]);
                        nv.push_back(c);
                        sort(nv.begin(), nv.end());
                        string k = to_string(nv[0]) + "/" + to_string(nv[1]) +
                                   "/" + to_string(nv[2]);
                        if (!st[k]) {
                            ans.push_back(nv);
                        }
                        st[k] = true;
                    }
                }
            }
        }
        return ans;
    }
};