寒假刷题Day22

一、2570. 合并两个二维数组 - 求和法

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        int i = 0, j = 0, n1 = nums1.size(), n2 = nums2.size();
        int tmp = 0;
        vector<vector <int>> ans;
        while(i < n1 && j < n2){
            int id1 = nums1[i][0], id2 = nums2[j][0];
            if(id1 == id2){
               ans.push_back({id1, nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (id1 < id2) {
                ans.push_back(nums1[i]);
                i++;
            } else { // id1 > id2
                ans.push_back(nums2[j]);
                j++;
            }
        }
             // 处理剩余部分
        while (i < n1) {
            ans.push_back(nums1[i]);
            i++;
        }
        while (j < n2) {
            ans.push_back(nums2[j]);
            j++;
        }
        return ans;  
    }
};

总体思路是先处理两条数组一样长的地方，再单独处理较长的那一条剩下的

二、LCP 18. 早餐组合

不出所料，暴力会超时。。。（谁家早餐店几千种卖早餐！！！带87979元吃早餐哈哈哈）

class Solution {
public:
    int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) {
        const int mod = 1e9 + 7;
        int ans = 0;
        sort(staple.begin(), staple.end());
        sort(drinks.begin(), drinks.end());
        int j = drinks.size() - 1;
        for (int i = 0; i < staple.size(); i++) {
            while (j >= 0 && staple[i] + drinks[j] > x) j--;
            if (j == -1) break;
            ans += j + 1;
            ans %= mod;
        }
        return ans;
    }
};

找 staple[i] + drinks[j] <= x 的位置

ans += j+1 是因为 j 是下标，0 到 j 满足条件

三、1855. 下标对中的最大距离

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int i = 0, j = 0, n1 = nums1.size(), n2 = nums2.size();
        int ans = 0;
        while(i < n1 && j < n2){
            if(j < i){
                j = i;
            }
            if(nums1[i] <= nums2[j]){
                ans = max(ans, (j - i));
                j++;
            }else{
                i++;
            }
        }
        return ans;
    }
};

有点摸到双指针套路了，也是维护加计算