贪心 | Bo Peng

贪心算法的本质是利用局部最优来推出整体最优，不过需要注意的是很多情况下局部最优是没办法推导出整体最优的。

简单题目

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸s[j]。如果s[j] >= g[i]，我们可以将这个饼干j 分配给孩子i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例1：

 输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
 

示例2：

 输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
 

提示：

1 <= g.length <= 3 * 10⁴
0 <= s.length <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 1

Solution

本题中我们可以先对g和s进行排序，然后优先满足胃口小的孩子的需求。整个算法可以通过两个指针对g和s同时进行遍历来实现。

题目链接：

python代码：

 class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g = sorted(g)
        s = sorted(s)

        i = j = 0
        res = 0

        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                i += 1
                res += 1
            
            j += 1
        
        return res
 

C++代码：

 class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int res = 0;
        int i = 0, j = 0;

        while (i < g.size() && j < s.size()) {
            if (g[i] <= s[j]) {
                ++res;
                ++i; ++j;
            } else ++j;
        }

        return res;
    }
};
 

1005. K次取反后最大化的数组和

给你一个整数数组nums和一个整数k，按以下方法修改该数组：

选择某个下标i并将nums[i]替换为-nums[i]。

重复这个过程恰好k次。可以多次选择同一个下标i。

以这种方式修改数组后，返回数组可能的最大和。

示例1：

 输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 

示例2：

 输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
 

示例3：

 输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
 

提示：

1 <= nums.length <= 10⁴
-100 <= nums[i] <= 100
1 <= k <= 10⁴

Solution

本题的解法在于尽可能多地把nums中的负值修改为正值，如果全部负值都变号后还有修改次数剩余则一直修改绝对值最小的那个值。整个算法流程如下：

将nums中的数字按绝对值大小从大到小排序
从前向后遍历，如果nums[i] < 0且k > 0则令其变号，同时k -= 1
完成遍历后如果k > 0，则继续对nums[-1]进行变号
对修改后的nums求和即为所求

题目链接：

python代码：

 class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        ## sort the array with abs
        nums = sorted(nums, key=abs, reverse=True)

        ## change signs of negative num
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1
        
        if k > 0:
            nums[-1] *= (-1)**k
        
        return sum(nums)
 

C++代码：

 bool cmp(int x, int y) {
    return abs(x) > abs(y);
}

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);

        for (int i=0; i<nums.size(); ++i) {
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                --k;
            }
        }

        if (k % 2 == 1) nums[nums.size()-1] *= -1;

        int res = 0;
        for (int x : nums) res += x;

        return res;
    }
};
 

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排队购买你的产品，(按账单bills支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付5美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组bills，其中bills[i]是第i位顾客付的账。如果你能给每位顾客正确找零，返回true，否则返回false。

示例1：

 输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
 

示例2：

 输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
 

提示：

1 <= bills.length <= 10⁵
bills[i]不是5就是10或是20

Solution

本题中根据bills[i]有以下找零情况：

bills[i] == 5时无需找零
bills[i] == 10时需要1张5元
bills[i] == 20时需要3张5元，或者1张10元和1张5元

因此5元的功能要比10元多一些，在找零时我们则应该尽可能先找10元然后再找5元。基于这样的观察，我们可以使用five和ten来记录已经收到的5元和10元数量，然后在找零时进行相应地递减。如果任意一个变量小于0则说明无法继续找零，返回False；否则继续遍历直到结束，返回True。

题目链接：

python代码：

 class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0

        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five < 0:
                    return False
                
                five -= 1
                ten  += 1
            else:
                if five > 0 and ten > 0:
                    five -= 1
                    ten  -= 1
                elif five > 2:
                    five -= 3
                else:
                    return False
        
        return True
 

C++代码：

 class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0, twenty = 0;

        for (int bill : bills) {
            if (bill == 5) ++five;
            else if (bill == 10) {
                if (five <= 0) return false;

                ++ten;
                --five;
            }
            else if (bill == 20) {
                if (five > 0 && ten > 0) {
                    --five;
                    --ten;
                    ++twenty;
                } else if (five >= 3) {
                    five -= 3;
                    ++twenty;
                } else return false;
            }
        }

        return true;
    }
};
 

1221. 分割平衡字符串

平衡字符串中，'L'和'R'字符的数量是相同的。

给你一个平衡字符串s，请你将它分割成尽可能多的子字符串，并满足：

每个子字符串都是平衡字符串。

返回可以通过分割得到的平衡字符串的最大数量。

示例1：

 输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
 

示例2：

 输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。
 

示例3：

 输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。
 

提示：

2 <= s.length <= 1000
s[i] = 'L' 或 'R'
s是一个平衡字符串

Solution

本题比较简单，我们只需要对字符串s进行遍历并统计当前出现过的L和R即可。每当L和R出现过的数量相同时就令记数res加1，最后返回res即可。

题目链接：

python代码：

 class Solution:
    def balancedStringSplit(self, s: str) -> int:
        L = R = 0
        res = 0

        for char in s:
            if char == "L":
                L += 1
            else:
                R += 1
            
            if L == R:
                res += 1
        
        return res
 

C++代码：

 class Solution {
public:
    int balancedStringSplit(string s) {
        int count = 0;
        int res = 0;

        for (auto ch : s) {
            if (ch == 'L') ++count;
            else --count;

            if (count == 0) ++res;
        }

        return res;
    }
};
 

序列问题

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如，[1, 7, 4, 9, 2, 5]是一个摆动序列，因为差值(6, -3, 5, -7, 3)是正负交替出现的。
相反，[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列可以通过从原始序列中删除一些(也可以不删除)元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组nums，返回nums中作为摆动序列的最长子序列的长度。

示例1：

 输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
 

示例2：

 输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
 

示例3：

 输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
 

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Solution

本题的技巧在于把数组想象成高度，这样最长摆动子序列的长度就是山峰和山谷的数目。

接下来考虑一些可能出现的情况。如果出现了平坡则需要把平的地方去掉。

总结一下，我们需要两个变量curDiff和preDiff记录当前位置和上一个山峰山谷的高度差。当curDiff * preDiff <= 0时说明当前位置可能符合摆动序列，需要进一步判断curDiff是否为0。如果curDiff == 0说明当前位于平坡上需要越过，否则对preDiff进行更新。整个算法流程可以参考如下。

题目链接：

python代码：

 class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        res = 1
        curDiff, preDiff = 0, 0

        for i in range(len(nums)-1):
            curDiff = nums[i+1] - nums[i]

            if curDiff * preDiff <= 0 and curDiff != 0:
                res += 1
                preDiff = curDiff

        return res
 

C++代码：

 class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();

        int curDiff = 0, preDiff = 0;
        int res = 1;

        for (int i=0; i<nums.size()-1; ++i) {
            curDiff = nums[i+1] - nums[i];

            if (preDiff * curDiff <= 0 && curDiff != 0) {
                ++res;
                preDiff = curDiff;
            }
        }

        return res;
    }
};
 

53. 最大子数组和

给你一个整数数组nums，请你找出一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和。

子数组是数组中的一个连续部分。

示例1：

 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 

示例2：

 输入：nums = [1]
输出：1
 

示例3：

 输入：nums = [5,4,-1,7,8]
输出：23
 

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Solution

本题中我们需要使用变量cur记录当前的子列之和，用res记录遇见过的最大子列之和。cur < 0时子列累加新的数字不如重新开始，因此我们重置子列起点并将cur设置为0。这样只需对nums进行一次遍历即可。

题目链接：

 class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        N = len(nums)

        res = -float("inf")
        cur = 0

        for i in range( N):
            cur += nums[i]

            ## update res
            if cur > res:
                res = cur
            
            ## reset
            if cur < 0:
                cur = 0

        return res
 

本题的另一种解法是利用动态规划。我们定义一个数组dp[]，其中dp[i]表示以nums[i]结尾的和最大的子列的和。当我们得到dp[i-1]之后，dp[i]有两种情况：

nums[i]在以nums[i-1]结尾的子列之中，此时dp[i] = dp[i-1]+nums[i]
nums[i]不在以nums[i-1]结尾的子列之中，此时需要开启一个新的子列dp[i] = nums[i]

这样就得到递推关系dp[i] = max(dp[i-1]+nums[i], nums[i])。完成递推后选择最大的dp[i]即可。

题目链接：

python代码：

 class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [nums[0] for _ in range(N)]
        
        for i in range(1, N):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        
        return max(dp)
 

C++代码：

 class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        
        int res = nums[0];

        for (int i=1; i<nums.size(); ++i) {
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            res = max(res, dp[i]);
        }

        return res;
    }
};
 

738. 单调递增的数字

当且仅当每个相邻位数上的数字x和y满足x <= y时，我们称这个整数是单调递增的。

给定一个整数n，返回小于或等于n的最大数字，且数字呈单调递增。

示例1：

 输入: n = 10
输出: 9
 

示例2：

 输入: n = 1234
输出: 1234
 

示例3：

 输入: n = 332
输出: 299
 

提示：

1 <= n <= 10⁹

Solution

本题解法在于从后向前对每一位数字进行遍历。如果第i位数字小于前一位则令第i-1位数字减1，并且把第i位后面的数字都变成9。

题目链接：

python代码：

 class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        strN = list(str(n))
        N = len(strN)

        for i in range(N-1, 0, -1):
            if int(strN[i-1]) > int(strN[i]):
                strN[i-1] = str(int(strN[i-1]) - 1)
                strN[i:]  = '9' * (N - i)
        
        return int("".join(strN)) 
 

C++代码：

 class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strN = to_string(n);
        int N = strN.size();

        for (int i=N-1; i>0; --i) {
            if (strN[i-1] > strN[i]) {
                --strN[i-1];

                for (int j=i; j<N; ++j) strN[j] = '9';
            }
        }

        return stoi(strN);
    }
};
 

股票问题

122. 买卖股票的最佳时机 II

给你一个整数数组prices，其中prices[i]表示某支股票第i天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

示例1：

 输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
 

示例2：

 输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
 

示例3：

 输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
 

提示：

1 <= prices.length <= 3*10⁴
0 <= prices[i] <= 10⁴

Solution

本题的贪心解法是尽可能多地进行交易，然后只选择其中利润大于0的，这样就能得到最大利润。

题目链接：

python代码：

 class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0

        for i in range(1, len(prices)):
            profit = prices[i] - prices[i-1]
            if profit > 0:
                res += profit

        return res
 

C++代码：

 class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int N = prices.size();
        int res = 0;

        for (int i=1; i<N; ++i) {
            if (prices[i] > prices[i-1]) res += prices[i] - prices[i-1];
        }

        return res;
    }
};
 

本题的另一种解法是利用动态规划。我们定义一个数组dp[]，其中dp[i]表示以第i天的最大利润。当我们得到dp[i-1]之后，dp[i]有两种情况：

买入第i天的股票并卖出，此时dp[i] = dp[i-1] + (prices[i] - prices[i-1])
什么也不做，此时dp[i] = dp[i-1]

这样就得到递推关系dp[i] = dp[i-1] + max(0, prices[i] - prices[i-1])。完成递推后直接返回最后一位dp[-1]即可。

题目链接：

python代码：

 class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)

        dp = [0 for _ in range(N)]

        for i in range(1, N):
            dp[i] = dp[i-1] + max(0, prices[i] - prices[i-1])
            
        return dp[-1]
 

C++代码：

 class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int N = prices.size();
        vector<int> dp(N, 0);

        for (int i=1; i<N; ++i) {
            dp[i] = dp[i-1] + max(0, prices[i] - prices[i-1]);
        }

        return dp[N-1];
    }
};
 

区间问题

55. 跳跃游戏

给定一个非负整数数组nums，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例1：

 输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 

示例2：

 输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
 

提示：

1 <= nums.length <= 3*10⁴
0 <= nums[i] <= 10⁵

Solution

本题的解法是使用一个变量cover来记录棋子当前能够到达的最远距离。在初始状态下cover = nums[0]，此时棋子可以到达[0, cover]之间的任意位置。然后我们对所有能够到达的位置i进行遍历，同时更新cover = max(cover, i+nums[i])。如果cover >= len(nums)-1说明棋子可以移动到终点，直接返回True；而如果i移动到cover位置还没有返回则说明无法移动到终点，返回False。

题目链接：

python代码：

 class Solution:
    def canJump(self, nums: List[int]) -> bool:
        i = 0
        cover = nums[0]

        while i <= cover:
            cover = max(cover, i+nums[i])

            if cover >= len(nums)-1:
                return True
            
            i += 1
        
        return False
 

C++代码：

 class Solution {
public:
    bool canJump(vector<int>& nums) {
        int N = nums.size();
        int cover = nums[0];

        int i = 0;

        while (i <= cover) {
            cover = max(cover, i+nums[i]);

            if (cover >= N-1) return true;

            ++i;
        }

        return false;
    }
};
 

45. 跳跃游戏 II

给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。

每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i + j]处:

0 <= j <= nums[i]
i + j < n

返回到达nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。

示例1：

 输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 

示例2：

 输入: nums = [2,3,0,1,4]
输出: 2
 

提示：

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
题目保证可以到达nums[n-1]

Solution

本题要比跳跃游戏复杂一些。我们需要使用两个指针：end用来记录当前能够到达的最远端，cover用来记录下一个区域的最远端。在位置i处进行更新cover = max(cover, i+nums[i])，到达end后再使用cover来更新end即可。

题目链接：

python代码：

 class Solution:
    def jump(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0

        end = cover = 0

        for i in range(N-1):
            cover = max(cover, i+nums[i])

            if i == end:
                res += 1
                end = cover

        return res
 

C++代码：

 class Solution {
public:
    int jump(vector<int>& nums) {
        int N = nums.size();
        int cover = 0, end = 0;

        int res = 0;

        for (int i=0; i<N-1; ++i) {
            cover = max(cover, i+nums[i]);

            if (i == end) {
                ++res;
                end = cover;
            }
        }

        return res;
    }
};
 

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组points，其中points[i] = [xstart, xend]表示水平直径在xstart和xend之间的气球。你不知道气球的确切y坐标。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为xstart，xend，且满足xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。

给你一个数组points，返回引爆所有气球所必须射出的最小弓箭数。

示例1：

 输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
 

示例2：

 输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
 

示例3：

 输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
 

提示：

1 <= points.length <= 10⁵
points[i].length == 2
-2³¹ <= xstart < xend <= 2³¹ - 1

Solution

本题的直观解法是每次选择具有最多气球的区间发射弓箭。但实际上我们只需要对气球排序并进行遍历，并且选择重叠气球中右边边界的最小值来发射弓箭即可。

题目链接：

python代码：

 class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points, key = lambda p: p[0])
        N = len(points)
        res = 1

        for i in range(1, N):
            if points[i][0] > points[i-1][1]:
                res += 1
            else:
                points[i][1] = min(points[i][1], points[i-1][1])

        return res
 

C++代码：

 bool cmp(vector<int> &x, vector<int> &y) {
    return x[0] < y[0];
}

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;

        sort(points.begin(), points.end(), cmp);
        int res = 1;

        for (int i=1; i<points.size(); ++i) {
            if (points[i][0] > points[i-1][1]) ++res;
            else points[i][1] = min(points[i-1][1], points[i][1]);
        }

        return res;
    }
};
 

435. 无重叠区间

给定一个区间的集合intervals，其中intervals[i] = [startᵢ, endᵢ]。返回需要移除区间的最小数量，使剩余区间互不重叠。

示例1：

 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
 

示例2：

 输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
 

示例3：

 输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
 

提示：

1 <= intervals.length <= 10⁵
intervals[i].length == 2
-5 * 10⁴ <= startᵢ < endᵢ <= 5 * 10⁴

Solution

本题可以理解为预订会议，我们希望在同一个房间中安排尽可能多的会议。因此我们首先需要按照会议的结束时间进行排序，选择第一个结束的会议以便给后面预留出更多的时间，即令end = intervals[0][1]。然后对剩下的会议进行遍历，如果会议开始时间intervals[i][0]大于结束时间end则选中它并更新end = intervals[i][1]，这样就增加了预订会议的数量。完成遍历后就得到了最多可以安排的会议数量，即互不重叠的区间数。

题目链接：

 class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x: x[1])
        N = len(intervals)

        count = 1
        end = intervals[0][1]

        for i in range(1, N):
            if end <= intervals[i][0]:
                count += 1
                end = intervals[i][1]

        return N-count
 

C++代码：

 bool cmp(vector<int> &x, vector<int> &y) {
    return x[1] < y[1];
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;

        sort(intervals.begin(), intervals.end(), cmp);

        int count = 1;
        int end = intervals[0][1];

        for (int i=1; i<intervals.size(); ++i) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                ++count;
            }
        }

        return intervals.size() - count;
    }
};
 

763. 划分字母区间

给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是s。

返回一个表示每个字符串片段的长度的列表。

示例1：

 输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 
 

示例2：

 输入：s = "eccbbbbdec"
输出：[10]
 

提示：

1 <= s.length <= 500
s仅由小写英文字母组成

Solution

本题中我们首先需要使用一个字典last来记录每个字符最后出现的位置。然后对s中的字符char进行遍历，此时char构成的区间为[i, right]。为了保证区间内包含全部的字符char，在遍历时我们需要不断拓展right = max(right, last[char])。当遍历到达right位置时就得到了一个划分区间[left, right]，添加到res中并更新left = right+1即可。整个算法流程可以参考如下。

题目链接：

python代码：

 class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {char: i for i, char in enumerate(s)}

        res = []
        left = right = 0

        for i, char in enumerate(s):
            right = max(right, last[char])

            if i == right:
                res.append(right-left+1)
                left = right+1

        return res
 

C++代码：

 class Solution {
public:
    vector<int> partitionLabels(string s) {
        int table[26] = {0};

        for (int i=0; i<s.size(); ++i) {
            table[s[i] - 'a'] = i;
        }

        vector<int> res;
        int left = 0, right = 0;

        for (int i=0; i<s.size(); ++i) {
            right = max(right, table[s[i] - 'a']);

            if (i == right) {
                res.push_back(right - left + 1);
                left = right + 1;
            }
        }

        return res;
    }
};
 

56. 合并区间

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [startᵢ, endᵢ]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例1：

 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 

示例2：

 输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 

提示：

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= startᵢ <= endᵢ <= 10⁴

Solution

本题的解法类似于用最少数量的箭引爆气球和无重叠区间。这里我们首先按照区间的起始位置对intervals进行排序，然后使用[start, end]来记录当前的区间位置。接下来对intervals进行遍历，如果其中的元素与[start, end]产生了重叠则更新end = max(end, intervals[i][1])，否则说明[start, end]已经是当前最大的重叠区间需要将其添加到res中并且用intervals[i]来进行更新。完成遍历后需要注意[start, end]保留了最后一个重叠区间，我们需要将其手动添加到res中。

题目链接：

python代码：

 class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        N = len(intervals)
        intervals = sorted(intervals, key=lambda x: (x[0], x[1]))

        start, end = intervals[0]
        res = []

        for i in range(1, N):
            if intervals[i][0] <= end:
                end = max(end, intervals[i][1])
            
            else:
                res.append([start, end])
                start = intervals[i][0]
                end   = intervals[i][1]
        
        ## add the last interval
        res.append([start, end])

        return res
 

C++代码：

 bool cmp(vector<int> &x, vector<int> &y) {
    return x[0] < y[0];
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);

        vector<vector<int>> res;
        int start = intervals[0][0], end = intervals[0][1];

        for (int i=1; i<intervals.size(); ++i) {
            if (intervals[i][0] > end) {
                res.emplace_back(vector<int>{start, end});

                start = intervals[i][0];
                end   = intervals[i][1];
            } else end = max(end, intervals[i][1]);
        }

        res.emplace_back(vector<int>{start, end});

        return res;
    }
};
 

权衡问题

135. 分发糖果

n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到1个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例1：

 输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
 

示例2：

 输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
 

提示：

n == ratings.length
1 <= n <= 2 * 10⁴
0 <= ratings[i] <= 2 * 10⁴

Solution

本题的难点在于理解题意，实际上题目要求可以表述如下：

左规则：当ratings[i-1] < ratings[i]时，candies[i] > candies[i-1]
右规则：当ratings[i] > ratings[i+1]时，candies[i] > candies[i+1]

这样我们就可以通过两次遍历来求出每个孩子获得的糖果数。整个算法流程可以参考如下。

题目链接：

python代码：

 class Solution:
    def candy(self, ratings: List[int]) -> int:
        N = len(ratings)
        candies = [1 for _ in range(N)]

        ## left to right
        for i in range(1, N):
            if ratings[i-1] < ratings[i]:
                candies[i] = candies[i-1]+1

        ## right to left
        for i in range(N-2, -1, -1):
            if ratings[i+1] < ratings[i]:
                candies[i] = max(candies[i], candies[i+1]+1)

        return sum(candies)
 

C++代码：

 class Solution {
public:
    int candy(vector<int>& ratings) {
        int N = ratings.size();
        vector<int> candies(N, 1);

        for (int i=1; i<N; ++i) {
            if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
        }

        for (int i=N-2; i>=0; --i) {
            if (ratings[i] > ratings[i+1]) candies[i] = max(candies[i], candies[i+1] + 1);
        }

        int res = 0;
        for (int c : candies) res += c;

        return res;
    }
};
 

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组people表示队列中一些人的属性(不一定按顺序)。每个people[i] = [hᵢ, kᵢ]表示第i个人的身高为hᵢ，前面正好有kᵢ个身高大于或等于hᵢ的人。

请你重新构造并返回输入数组people所表示的队列。返回的队列应该格式化为数组queue，其中queue[j] = [hⱼ, kⱼ]是队列中第j个人的属性(queue[0]是排在队列前面的人)。

示例1：

 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
 

示例2：

 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
 

提示：

1 <= people.length <= 2000
0 <= hᵢ <= 10⁵
0 <= kᵢ < people.length
题目数据确保队列可以被重建

Solution

本题中我们需要对people中的元素按照身高从大到小排序，对于身高一样的则按照kᵢ进行排序。排序后我们对people进行遍历，然后按照每个元素的kᵢ进行插入来重新构造一个新的数组，这样可以保证它前面正好有kᵢ个比它高的元素。

题目链接：

python代码：

 class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people = sorted(people, key= lambda p: (-p[0], p[1]))

        queue = []
        for p in people:
            queue.insert(p[1], p)
        
        return queue
 

C++代码：

 bool cmp(vector<int> &x, vector<int> &y) {
    if (x[0] == y[0]) return x[1] < y[1];

    return x[0] > y[0];
}

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);

        vector<vector<int>> res;

        for (int i = 0; i < people.size(); ++i) {
            int position = people[i][1];
            res.insert(res.begin() + position, people[i]);
        }

        return res;
    }
};
 

其它

134. 加油站

在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。

你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组gas和cost，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

示例1：

 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
 

示例2：

 输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
 

提示：

gas.length == n
cost.length == n
1 <= n <= 10⁵
0 <= gas[i], cost[i] <= 10⁴

Solution

本题的暴力解法是从每一个加油站出发尝试行驶一圈，如果能完成一圈则返回起始加油站编号，否则返回-1。显然暴力解法的复杂度为O(n²)，说明这并不是一种高效的解法。

本题的贪心解法需要使用两个变量start来记录起始加油站编号，以及cur来记录start到当前加油站时剩余的汽油量。首先我们需要判断是否存在解，即是否满足sum(gas) >= sum(cost)，如果不满足则直接返回-1。然后从start = 0开始遍历，更新cur += gas[i] - cost[i]作为start到i位置剩余的汽油量。如果cur < 0则说明从start出发会出现油量不足的问题，更进一步来说从区间[start, i]上的任意位置出发经过i都会出现油量不足，因此我们需要令start = i+1重新进行尝试并将cur置零。完成遍历后start即为所求。

题目链接：

 class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        cur = 0
        start = 0

        for i in range(len(gas)):
            cur += gas[i] - cost[i]

            if cur < 0:
                cur = 0
                start = i+1
        
        return start
 

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例1：

 输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
 

示例2：

 输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
 

提示：

给定树的节点数的范围是[1, 1000]。
每个节点的值都是0。

Solution

本题中我们需要尽可能地在叶节点的父节点上放置摄像头才能得到最少的摄像头数量，因此我们需要使用后序遍历来对二叉树进行处理。首先我们规定每个节点有三种状态：

0表示该节点没有被摄像头覆盖
1表示该节点有放置摄像头
2表示该节点已经被摄像头覆盖

接下来我们定义一个遍历函数traversal()返回当前节点的状态。根据后续遍历，我们需要先访问左节点和右节点来得到它们的状态left和right，然后分情况讨论：

如果left == 2且right == 2，说明两个子节点都被摄像头覆盖了，则当前节点没有摄像头覆盖返回0
如果left == 0或right == 0，说明两个子节点中至少有一个没有被摄像头覆盖，我们需要在当前节点放置摄像头并返回1
如果left == 1或right == 1，说明两个子节点中至少有一个摄像头，当前节点已经被摄像头覆盖并返回2

对于空节点我们把它标记为2，这样可以保证叶节点及其父节点可以正确地标记为0和1。最后我们使用一个变量res记录下放置的摄像头总数即可。

题目链接：

 # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        res = 0

        def traversal(root: Optional[TreeNode]) -> int:
            if not root:
                return 2
            
            nonlocal res

            left = traversal(root.left)
            right= traversal(root.right)

            if left == 2 and right == 2:
                return 0
            elif left == 0 or right == 0:
                res += 1
                return 1
            elif left == 1 or right == 1:
                return 2
        
        if traversal(root) == 0:
            res += 1
        
        return res
 

649. Dota2 参议院

Dota2的世界里有两个阵营：Radiant(天辉)和Dire(夜魇)。

Dota2参议院由来自两派的参议员组成。现在参议院希望对一个Dota2游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
宣布胜利：如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串senate代表每个参议员的阵营。字母'R'和'D'分别代表了Radiant(天辉)和Dire(夜魇)。然后，如果有n个参议员，给定字符串的大小将是n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在Dota2游戏中决定改变。输出应该是"Radiant"或"Dire"。

示例1：

 输入：senate = "RD"
输出："Radiant"
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。
 

示例2：

 输入：senate = "RDD"
输出："Dire"
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
 

提示：

n == senate.length。
1 <= n <= 10⁴。
senate[i]为 'R'或'D'

Solution

本题的题干比较复杂，但实际上就是字符串中前面的字符可以屏蔽掉后面的字符。如果屏蔽后字符串中只剩下一种字符，则该字符的阵营胜利。因此本题的解法是使用两个队列R和D分别按顺序存储每个阵营议员的位置，然后模拟投票过程：

如果R和D有一方为空则结束投票，非空的阵营获胜
如果R和D均非空，则比较它们的首元素r和d。假设r比较小，则说明Radiant阵营的议员可以率先行使权力，将Dire阵营的议员进行屏蔽。此时d会永久弹出队列中，而则r则会重新加入到R中并且更新为r+N，这样就完成了屏蔽的过程。

题目链接：

 class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        N = len(senate)
        
        from collections import deque
        R = deque([])
        D = deque([])

        for i, s in enumerate(senate):
            if s == "R":
                R.append(i)
            else:
                D.append(i)
        
        while R and D:
            r = R.popleft()
            d = D.popleft()

            if r < d:
                R.append(r+N)
            else:
                D.append(d+N)
        
        return "Radiant" if R else "Dire"
 

简单题目

455. 分发饼干

Solution

1005. K次取反后最大化的数组和

Solution

860. 柠檬水找零

Solution

1221. 分割平衡字符串

Solution

序列问题

376. 摆动序列

Solution

53. 最大子数组和

Solution

738. 单调递增的数字

Solution

股票问题

122. 买卖股票的最佳时机 II

Solution

区间问题

55. 跳跃游戏

Solution

45. 跳跃游戏 II

Solution

452. 用最少数量的箭引爆气球

Solution

435. 无重叠区间

Solution

763. 划分字母区间

Solution

56. 合并区间

Solution

权衡问题

135. 分发糖果

Solution

406. 根据身高重建队列

Solution

其它

134. 加油站

Solution

968. 监控二叉树

Solution

649. Dota2 参议院

Solution

Reference