lc1537

双指针+分段贪心

双指针遍历两个数组，遇到相同数时选此前两数组累加和的较大值加上该数计入结果

 

再重置累加和

 

遍历完剩余元素后，把最后一段累加和的较大值加到结果里，最后取模得到答案

 int maxSum(vector<int>& nums1, vector<int>& nums2) {
        long sum1 = 0, sum2 = 0;
        long res = 0;
        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] == nums2[j]){
                res += (max(sum1, sum2) + nums1[i]);
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
            else if(nums1[i] < nums2[j]){
                sum1 += nums1[i];
                i++;                
            }
            else{
                sum2 += nums2[j];
                j++;
            }            
        }

 
        while(i < nums1.size()){
            sum1 += nums1[i];
            i++;
        }
        while(j < nums2.size()){
            sum2 += nums2[j];
            j++;
        }
        res += max(sum1, sum2);
        return res % ((int)pow(10, 9) + 7 );

lc1713

先把目标数组元素换成专属序号，再从待处理数组里挑出有专属序号的元素排成新数组

 

找新数组的最长递增序列，用目标数组长度减去这个序列长度，就是要插入的最少元素数

class Solution {
public:
    int minOperations(vector<int>& t, vector<int>& a) 
    {
        unordered_map<int, int> mp;
        for (int i = 0; i < t.size(); ++i)

                 mp[t[i]] = i;

        vector<int> nums;  //抽象为 lis
        for (int num : a) if (mp.count(num)) nums.push_back(mp[num]);

        vector<int> lis;
        for (int x : nums)

      {
            auto it = lower_bound(lis.begin(), lis.end(), x);
            if (it == lis.end())

                    lis.push_back(x);

//出现第一个≥  利用单调性 即可连上
            else *it = x;
        }

        return t.size() - lis.size();
    }
};

lc3218

“高费用的线段越早切越好”

如果切晚了会有增加segment的风险，而cost最大线段增加的总cost也最多

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)

{
        // 存储切割成本和类型，pair第一个值为成本，第二个值0代表水平(H)、1代表垂直(V)
        vector<pair<int, int>> cuts;
        for (int cost : horizontalCut) 
            cuts.emplace_back(cost, 0);
        for (int cost : verticalCut) 
            cuts.emplace_back(cost, 1);
        // 按成本从大到小排序
        sort(cuts.begin(), cuts.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first;
        });
        
        int horizontalSegments = 1, verticalSegments = 1;
        int ret = 0;
        for (auto& cut : cuts) {
            int cost = cut.first;
            int type = cut.second;
            if (type == 0) { // 水平切割
                ret += cost * horizontalSegments;
                verticalSegments++;
            }

           else { // 垂直切割
                ret += cost * verticalSegments;
                horizontalSegments++;
            }
        }
        return ret;
    }
};
 

最小生成树法

不是真的要写最小生成树，是为了证明采用这种贪心策略是“正确的”，写出来的代码是等价的....

把这个题目转成最小生成树模型，那么正确性就证明完毕了