More content：力扣题记之贪心

121. 买卖股票的最佳时机✅

简单贪心 也可DP

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        int mny = 0;
        for(int i = 1; i < prices.size(); i++) {
            mny += prices[i] - prices[i-1];
            if(mny < 0)  mny = 0; //一旦亏钱就重新开始，零总比负数大吧
            else res = max(res, mny);
        }

        return res;
    }
};

55. 跳跃游戏❌

一开始想的是跳向最大长度之间中下标最大的，发现不行

不要拘泥于跳到哪，而是能跳到哪，即关注能跳到的范围

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围）

整体最优解：最后得到整体最大覆盖范围，看是否能到终点

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int dest = nums.size() - 1;
        //看跳跃覆盖范围可不可以覆盖到终点
        int cover = 0;
        for(int i = 0; i <= dest; i++) {
            if(cover < i) return false; //遇到0跳不到，中断了
            for(int j = 1; j <= nums[i] && j + i <= dest; j++) {
                cover = max(cover, i + j + nums[i+j]);
            }
            if(cover >= dest) return true;
        }
        return false;
    }
};

45. 跳跃游戏 II❌

上一题是能不能跳到终点，这题是求跳到终点的最小步数

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        int dest = nums.size() - 1;
        int res = 0;
        int curDis = 0;
        int nextDis = 0;
          
        for(int i = 0; i <= dest; i++) {
            nextDis = max(nums[i] + i, nextDis); // 更新下一步覆盖最远距离下标
            if(i == curDis) {                    // 遇到当前覆盖最远距离下标
                if(curDis != dest) {             // 如果当前覆盖最远距离下标不是终点
                    res++;                       // 需要走下一步
                    curDis = nextDis;            // 更新当前覆盖最远距离下标（相当于加油了）
                    if(nextDis >= dest) break;   // 下一步的覆盖范围已经可以达到终点，结束循环
                } else break;                    // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
            }
        }

        return res;
    }
};

763. 划分字母区间✅

遍历找到切割点，即重复字母最后出现的位置，用map记录防止重复搜索

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> map(100, -1); //标识字母出现的最后位置
        vector<int> res; //不会多于26个片段，因为一共26个英文字母

        int cutpoint = 0;
        int start = 0;
        for(int i = 0; i < s.size(); i++) {
            if(map[s[i] - '0'] == -1) { //之前没搜过
                for(int j = s.size() - 1; j >= i; j--) {
                    if(s[j] == s[i]) {
                        cutpoint = max(j, cutpoint);
                        map[s[i] - '0'] = j;
                        break;
                    }
                }
                // cout << "i = " << i << ", cutpoint = " << cutpoint << endl;
            } 
            
            if(i == cutpoint) {
                // cout << "切i = " << i << endl;
                res.push_back(cutpoint - start + 1);
                start = cutpoint + 1; 
            }
        }

        return res;
    }
};