寒假刷题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 > id2ans.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;}
};

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