我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

LeetCode：贪心算法（30道经典题目）

作者：我家小花儿 | 2024-07-15 16:15:24

踩

LeetCode：贪心算法

求解最优化的问题常常会有一系列的步骤，而每个步骤往往会面临着选择。贪心算法在每一步都做出最优解，寄希望于通过局部最优解来获得全局最优解。贪心算法往往是这种自顶向下的设计，先做出一个选择，然后再求解下一个问题，而不是自底向上解出许多子问题，然后再做出选择。

在做贪心选择时，我们直接做出当前问题中看起来最优的解s，而不是考虑到子问题的解，这也是贪心算法和动态规划的不同之处，在动态规划中，我们往往每一个步骤都做一个选择，这个选择往往依赖于子问题的解。而在贪心算法中，我们总是做出当时看来最佳的选择，然后再求解剩下唯一的子问题。贪心算法做出选择时可能会依赖于之前的选择或者子问题的解，但是绝对不依赖于将来的选择或者子问题的解。也就是，动态规划问题是自底向上的，而贪心算法问题是自顶向下的。

贪心算法一般按如下步骤进行：

建立数学模型来描述问题
把求解的问题分成若干个子问题
对每个子问题求解，得到子问题的局部最优解
把子问题的解局部最优解合成原来解问题的一个解

事实上，并不是所有问题都能用贪心算法进行求解。贪心算法得到的解并不一点是最佳的，因为贪心算法总是从局部出发，并没从整体考虑，贪心算法只能确定某些问题的可行性范围。利用贪心法求解的问题应具备如下两个特征：

贪心选择性质 ：一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
最优子结构性质： 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。

455. 分发饼干

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

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

class Solution {
    public:
    // 大饼干喂给胃口大的
    int findContentChildren(vector<int> &g, vector<int> &s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1;
        int result = 0;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (index >= 0 && g[i] <= s[index]) {
                result++;
                index--;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

也可以小饼干先喂饱小胃口：

class Solution {
public:
    // 小饼干先喂饱小胃口
    int findContentChildren(vector<int> &g, vector<int> &s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = 0;
        for (int i = 0; i < s.size(); i++) {
            if (index < g.size() && g[index] <= s[i]) {
                index++;
            }
        }
        return index;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

376. 摆动序列

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

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

子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度。

方法一：贪心

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了。 这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。

class Solution {
public:
    int wiggleMaxLength(vector<int> &nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0;
        int preDiff = 0;
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 1; i < nums.size(); i++) {
            curDiff = nums[i] - nums[i - 1];
            // 出现峰值
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {  // 取等是为了解决在i=1的情况，记录result
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：动态规划

很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i] < nums[i - 1]）。

设dp状态dp[i][0]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
设dp状态dp[i][1]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度

则转移方程为：

dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将nums[i]接到前面某个山谷后面，作为山峰。
dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将nums[i]接到前面某个山峰后面，作为山谷。

初始状态：由于一个数可以接到前面的某个数后面，也可以以自身为子序列的起点，所以初始状态为：dp[0][0] = dp[0][1] = 1。

class Solution {
public:
    int wiggleMaxLength(vector<int> &nums) {
        vector<vector<int>> dp(nums.size(), vector<int>(2, 0));
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.size(); i++) {
            // i自己可以成为波峰或者波谷
            dp[i][0] = dp[i][0] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) { // i 是波谷
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]) { // i 是波峰
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1);
                }
            }
        }
        return max(dp[nums.size() - 1][1], dp[nums.size() - 1][0]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优化：仅需要前一个状态来进行转移，所以维护两个变量即可。

class Solution {
public:
    int wiggleMaxLength(vector<int> &nums) {
        if (nums.size() < 2) return nums.size();
        int up = 1, down = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                up = max(up, down + 1);
            } else if (nums[i] < nums[i - 1]) {
                down = max(down, up + 1);
            }
        }
        return max(up, down);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意到每有一个「峰」到「谷」的下降趋势，down 值才会增加，每有一个「谷」到「峰」的上升趋势，up 值才会增加。且过程中down 与up 的差的绝对值值恒不大于 1，即 up≤down+1 且 down≤up+1，于是有max(up,down+1)=down+1 且max(up+1,down)=up+1。这样可以省去不必要的比较大小的过程。

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int result = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum > result) result = sum; // 取区间累计的最大值
            if (sum <= 0) sum = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

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

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。

方法一：贪心

假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！

只需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

局部最优：收集每天的正利润
全局最优：求得最大利润。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(0, prices[i] - prices[i - 1]);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10

方法二：动态规划

dp数组的含义：

dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来：

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]

如果第i天不持有股票即dp[i][1]的情况，依然可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

class Solution {
public:
    // dp[i][0] 表示第i天持有股票所得现金。
    // dp[i][1] 表示第i天不持有股票所得最多现金
    int maxProfit(vector<int> &prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.size() - 1][1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？其实跳几步无所谓，关键在于可跳的覆盖范围！不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

局部最优解：每次取最大跳跃步数（取最大覆盖范围）
整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。如果cover大于等于了终点下标，直接return true就可以了。

class Solution {
public:
    bool canJump(vector<int> &nums) {
        int cover = 0;
        if (nums.size() == 1) return true;  // 只有一个元素，就是能达到
        for (int i = 0; i <= cover; i++) {  // 注意这里是小于等于cover
            cover = max(cover, i + nums[i]);
            if (cover >= nums.size() - 1) return true;   // 说明可以覆盖到终点了
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

45. 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一；
整体最优：一步尽可能多走，从而达到最小步数。

但要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

方法一：

移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

class Solution {
public:
    int jump(vector<int> &nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;  // 当前覆盖最远距离下标
        int nextDistance = 0; // 下一步覆盖最远距离下标
        int result = 0;
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nextDistance, i + nums[i]); // 更新下一步覆盖最远距离下标
            if (i == curDistance) {  // 遇到当前覆盖最远距离下标
                if (curDistance != nums.size() - 1) { // 如果当前覆盖最远距离下标不是终点
                    result++; // 需要走下一步
                    curDistance = nextDistance; // 更新当前覆盖最远距离下标
                    if (nextDistance > nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环
                } else break; // 当前覆盖最远距离下标是集合终点，直接结束
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：

针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。想要达到这样的效果，只要让移动下标，最大只能移动到nums.size() - 2的地方就可以了。
如果移动下标等于当前覆盖最大距离下标，需要再走一步，因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置）

class Solution {
public:
    int jump(vector<int> &nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;  // 当前覆盖最远距离下标
        int nextDistance = 0; // 下一步覆盖最远距离下标
        int result = 0;
        for (int i = 0; i < nums.size() - 1; i++) {  // 注意这里是小于nums.size() - 1
            nextDistance = max(nextDistance, i + nums[i]); // 更新下一步覆盖最远距离下标
            if (i == curDistance) {  // 遇到当前覆盖最远距离下标
                curDistance = nextDistance;
                result++;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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

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

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后，返回数组可能的最大和。

局部最优：让绝对值大的负数变为正数，当前数值达到最大
整体最优：整个数组和达到最大。
本题的解题步骤为：

第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和

class Solution {
    private:
    static bool cmp(int a, int b) {
        return abs(a) > abs(b);
    }
    
    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] *= -1;
                k--;
            }
        }
        if (k % 2 == 1) nums[nums.size() - 1] *= -1;
        int result = 0;
        for (int num: nums) result += num;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

方法一：暴力求解

for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历

class Solution {
    public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 记录剩余油量
            int index = (i + 1) % cost.size();
            while (rest > 0 && index != i) {  // 模拟以i为起点行驶一圈
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

显然时间复杂度是O(n^2)，在LeetCode提交会超时。

方法二：贪心（全局最优的角度）
直接从全局进行贪心选择，情况如下：

情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。

class Solution {
    public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int curSum = 0;
        int min = INT_MAX;  // 从起点出发，油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) return -1;  // 情况1
        if (min >= 0) return 0;  // 情况2
        
        for (int i = gas.size() - 1; i >= 0; i--) {  // 情况3
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这种方式直接从全局最优的角度上思考问题。

方法三：贪心
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行
全局最优：找到可以跑一圈的起始位置。

class Solution {
    public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            totalSum += rest;
            if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1; // 起始位置更新为i+1
                curSum = 0;  // curSum从0开始
            }
        }
        if (totalSum < 0) return -1;  // 说明怎么走都不可能跑一圈了
        return start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：

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

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

采用两次贪心的策略：

一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。

class Solution {
    public:
    int candy(vector<int> &ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // forward
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            }
        }
        // backward
        for (int i = ratings.size() - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) {
                // greedy 保证第i个小孩的糖果数量即大于左边的也大于右边的
                candyVec[i - 1] = max(candyVec[i] + 1, candyVec[i - 1]);  
            }
        }
        int result = 0;
        for (int num: candyVec) result += num;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

有如下三种情况：

情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

class Solution {
public:
    bool lemonadeChange(vector<int> &bills) {
        int five = 0, ten = 0, twenty = 0;
        for (int bill: bills) {
            if (bill == 5) five++;
            if (bill == 10) {
                ten++;
                five--;
                if (five < 0) return false;
            }
            if (bill == 20) {
                if (five > 0 && ten > 0) {
                    ten--;
                    five--;
                    twenty++;
                } else if (five >= 3) {
                    five -= 3;
                    twenty++;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第i个人的身高为hi ，前面正好有ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

局部最优：优先按身高高的**people**的**k**来插入。插入操作过后的**people**满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

class Solution {
private:
    static bool cmp(vector<int> a, vector<int> b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }

public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n^2)了，甚至可能拷贝好几次，就不止O(n^2)了。

改成链表：

class Solution {
private:
    static bool cmp(vector<int> a, vector<int> b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }

public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 插入到下标为position的位置
            list<vector<int>>::iterator it = que.begin();
            while (position--) it++;   // 寻找在插入位置
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数。

局部最优：当气球出现重叠，一起射，所用弓箭最少。
全局最优：把所有气球射爆所用弓箭最少。

如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remote气球，只要记录一下箭的数量就可以了。

注意题目中说的是：满足 xstart ≤ x ≤ xend，则该气球会被引爆。那么说明两个气球挨在一起不重叠也可以一起射爆。

class Solution {
    private:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }
    
    public:
    int findMinArrowShots(vector<vector<int>> &points) {
        if (points.size() == 0) return 0;
        int result = 1;  // points不为空至少需要一支箭
        sort(points.begin(), points.end(), cmp);
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) { // 挨不到
                result++;  // 需要一支箭
            } else {  // 气球i和气球i-1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

435. 无重叠区间

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

注意: 可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数。

class Solution {
    private:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[1] < b[1];
    }
    
    public:
    int eraseOverlapIntervals(vector<vector<int>> &intervals) {
        if (intervals.size() == 0) return 0;
        int result = 1;
        sort(intervals.begin(), intervals.end(), cmp);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= intervals[i - 1][1]) {
                result++;
            } else {
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
            }
        }
        return intervals.size() - result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

方法一：

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。可以分为如下两步：

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int position[27]; // i为字符，position[i]为字符出现的最后位置
        for (int i = 0; i < s.size(); i++) {
            position[s[i] - 'a'] = i; // 统计每一个字符最后出现的位置
        }

        int start = 0;
        int end = 0;
        vector<int> result;
        for (int i = 0; i < s.size(); i++) {
            end = max(end, position[s[i]- 'a']); // 找到字符出现的最远边界
            if (end == i) {
                result.push_back(end - start + 1); 
                start = i+1;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：

统计字符串中所有字符的起始和结束位置，记录这些区间(实际上也就是435.无重叠区间题目里的输入)，将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。找到的边界就是答案。

class Solution {
private:
    // 记录每个字母出现的区间
    vector<vector<int>> CountLabels(string s) {
        vector<vector<int>> hash(26, vector<int>(2, INT16_MIN));
        vector<vector<int>> hash_filter;
        for (int i = 0; i < s.size(); i++) {
            if (hash[s[i] - 'a'][0] == INT16_MIN) {
                hash[s[i] - 'a'][0] = i;
            }
            hash[s[i] - 'a'][1] = i;
        }

        // 去除字符串中未出现的字母所占用区间
        for (int i = 0; i < hash.size(); i++) {
            if (hash[i][0] != INT16_MIN) {
                hash_filter.push_back(hash[i]);
            }
        }
        return hash_filter;
    }

    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }

public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        vector<vector<int>> hash = CountLabels(s);

        // 按照左边界从小到大排序
        sort(hash.begin(), hash.end(), cmp);

        int left = 0;
        int right = hash[0][1];
        for (int i = 1; i < hash.size(); i++) {
            // 下一区间左边界大于上一右边界，即可认为出现分割点
            if (hash[i][0] > right) {
                res.push_back(right - left + 1);
                left = hash[i][0];
            }
            right = max(right, hash[i][1]);
        }
        res.push_back(right - left + 1);  // 最右端
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

56. 合并区间

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

class Solution {
private:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[0] < b[0];
    }

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

        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > res.back()[1]) {
                res.push_back(intervals[i]);
            } else {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈单调递增。

局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]置为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。

但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strN = to_string(n);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strN.size();
        for (int i = strN.size() - 1; i > 0; i--) {
            if (strN[i - 1] > strN[i]) {
                flag = i;
                strN[i - 1]--;
            }
        }
        for (int i = flag; i < strN.size(); i++) {
            strN[i] = '9';
        }
        return stoi(strN);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

方法一：贪心

做收获利润操作的时候有三种情况：

情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
情况三：不作操作，保持原有状态（买入，卖出，不买不卖）

class Solution {
public:
    int maxProfit(vector<int> &prices, int fee) {
        int result = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            // 情况二：相当于买入
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }

            // 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
            if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
                continue;
            }

            // 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
            if (prices[i] > minPrice + fee) {
                result += prices[i] - minPrice - fee;
                minPrice = prices[i] - fee; // 情况一，这一步很关键
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

如果还在收获利润的区间里，表示并不是真正的卖出，而计算利润每次都要减去手续费，所以要让minPrice = prices[i] - fee;，这样在明天收获利润的时候，才不会多减一次手续费！

方法二：动规

dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1]表示第i天不持有股票所得最多现金。

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]

所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])。

如果第i天不持有股票即dp[i][1]的情况，依然可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，**注意这里需要有手续费了，**即：dp[i - 1][0] + prices[i] - fee

所以：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)。

class Solution {
public:
    int maxProfit(vector<int> &prices, int fee) {
        // dp[i][0] 表示第i天持有股票所省最多现金。
        // dp[i][1] 表示第i天不持有股票所得最多现金
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];  // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
        }
        return max(dp[n - 1][1], dp[n - 1][0]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

首先，可以发现：

摄像头都没有放在叶子节点上，因为摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。
头结点放不放摄像头可以省下一个摄像头，叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。

从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

使用后序遍历，在回溯的过程中从下到上进行推导。

每个节点可能有如下三种状态：

该节点无覆盖，用0表示
本节点有摄像头，用1表示
本节点有覆盖，用2表示

**空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了。**因为空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。

主要有如下四类情况：

情况1：左右节点都有覆盖：左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
情况2：左右节点至少有一个无覆盖的情况：如果是以下情况，则中间节点（父节点）应该放摄像头：
- left == 0 && right == 0 左右节点无覆盖
- left == 1 && right == 0 左节点有摄像头，右节点无覆盖
- left == 0 && right == 1 左节点无覆盖，右节点摄像头
- left == 0 && right == 2 左节点无覆盖，右节点覆盖
- left == 2 && right == 0 左节点覆盖，右节点无覆盖
情况3：左右节点至少有一个有摄像头：如果是以下情况，其实就是左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
- left == 1 && right == 2 左节点有摄像头，右节点有覆盖
- left == 2 && right == 1 左节点有覆盖，右节点有摄像头
- left == 1 && right == 1 左右节点都有摄像头
情况4：头结点没有覆盖：递归结束之后，还要判断根节点，如果没有覆盖，result++

class Solution {
public:
    int result;

    // 0：该节点无覆盖  1：本节点有摄像头  2：本节点有覆盖
    int minCameraCover(TreeNode *root) {
        result = 0;
        // 情况4  root 无覆盖
        if(traversal(root) == 0) result++;
        return result;
    }

    int traversal(TreeNode *cur) {
        // 空节点，该节点有覆盖
        if (cur == nullptr) return 2;

        int left = traversal(cur->left);
        int right = traversal(cur->right);

        // 情况1  左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2  左右节点至少有一个无覆盖的情况
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3  左右节点至少有一个有摄像头
        if (left == 1 || right == 1) return 2;

        return -1; // 不会走到这儿来
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

后面的题目是使用Python做的。比较简单，所以没有太多说明。

561. 数组拆分 I

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该最大总和。

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])
1
2
3
4

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums_ = sorted(nums)
        return sum([nums_[i] for i in range(len(nums_)) if i % 2 == 0])
1
2
3
4

680. 验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

回文串的特点是左右对称。假如有两个指针从字符串的两端同时向中间走：如果遇到的元素相等，则该相等的元素是最终回文字符串的一部分。判断回文字符串：s == s[::-1]

使用双指针

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if s == s[::-1]:
            return True
        l, r = 0, len(s) - 1
        while l < r:  # 双指针
            if s[l] == s[r]:
                l, r = l + 1, r - 1
            else:  # 若不相等必有一个要被删除才能满足回文串
                a = s[l + 1:r + 1]  # 删掉s[l]
                b = s[l: r]  # 删掉s[r]
                return a == a[::-1] or b == b[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
'运行

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

贪心：面对20元找零时，优先用掉10元面额的

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        my_bill = []
        for bill in bills:
            try:
                if bill == 5:
                    my_bill.append(bill)
                elif bill == 10:
                    my_bill.remove(bill - 5)
                    my_bill.append(bill)
                else:
                    my_bill.append(20)
                    if 10 in my_bill:
                        my_bill.remove(10)
                        my_bill.remove(5)
                    else:
                        my_bill.remove(5)
                        my_bill.remove(5)
                        my_bill.remove(5)
            except ValueError:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                ten += 1
                five -= 1
                if five < 0: return False
            else:
                if ten > 0:
                    ten -= 1
                    five -= 1
                else:
                    five -= 3
                if ten < 0 or five < 0:
                    return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1217. 玩筹码

数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。

最开始的时候，同一位置上也可能放着两个或者更多的筹码。返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

注意是把每个筹码的位置存在数组中的。

优先把所有偶数位置的筹码都移动到第二个位置上，把所有奇数位置的筹码都移动到第一个位置上，花费代价为0，接下来的移动就是比较位置1和位置2的筹码个数哪个小——这样题目就转化成了比较数组中奇数的个数和偶数的个数，取更小的个数。

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        data = [num % 2 for num in position]
        return min(data.count(0), len(position) - data.count(0))
1
2
3
4

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        odd, even = 0, 0
        for num in position:
            if num % 2 == 0:
                even += 1
            else:
                odd += 1
        return min(even, odd)
1
2
3
4
5
6
7
8
9

942. 增减字符串匹配

给定只含 “I”（增大）或 “D”（减小）的字符串 S ，令 N = S.length。返回 [0, 1, …, N] 的任意排列 A 使得对于所有 i = 0, …, N-1，都有：

如果 S[i] == “I”，那么 A[i] < A[i+1]
如果 S[i] == “D”，那么 A[i] > A[i+1]

返回的是排列，也就意味着0到S.size()范围内的每个数只能出现一次，这是一个消耗性选择的过程。

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low, high = 0, len(s)
        ret = []
        for strs in s:
            if strs == "I":
                ret.append(low)
                low += 1
            if strs == "D":
                ret.append(high)
                high -= 1
        ret.append(low)
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        length = len(s)
        i, d = 0, 0
        ret = [0] * (length + 1)
        for k in range(length):
            if s[k] == "I":
                ret[k] += i
                i += 1
        if i == 0:
            ret[-1] = 0
        else:
            ret[-1] = max(ret) + 1
        for kk in range(length - 1, -1, -1):
            if s[kk] == "D":
                d += 1
                ret[kk] = ret[-1] + d
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

976. 三角形的最大周长

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。

贪心在于：如果最大边的前两条边都不能满足a+b>c，那么更往前的边值更小，也比不可能满足条件，就无需考虑了，只需要考虑连续的3条边即可。

为什么只需要判断 a + b > c ?

为什么只需要判断数组中相邻的三个数？

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1, 1, -1):
            if nums[i - 1] + nums[i - 2] > nums[i]:
                return nums[i - 1] + nums[i - 2] + nums[i]
        return 0
1
2
3
4
5
6
7

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

给定一个整数数组A，我们只能用以下方法修改该数组：我们选择某个索引i并将 A[i]替换为-A[i]，然后总共重复这个过程K次。（我们可以多次选择同一个索引）以这种方式修改数组后，返回数组可能的最大和。

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        num = sum([True if k < 0 else False for k in nums])
        if num == 0 and k % 2 != 0:
            nums[0] = -nums[0]
        elif num >= k:
            nums[:k] = [-m for m in nums[:k]]
        else:
            nums[:num] = [-m for m in nums[:num]] # 都是正的
            nums.sort()
            if (k - num) % 2 != 0:
                nums[0] = -nums[0]
        return sum(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
        if k % 2 != 0:
            nums.sort()
            nums[0] = -nums[0]
        return sum(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13

1013. 将数组分成和相等的三个部分

给你一个整数数组 arr，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。形式上，如果可以找出索引 i + 1 < j 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) 就可以将数组三等分。

三等分，每一等分的和都为sum/3

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        s = sum(arr)
        if s % 3 != 0:
            return False
        target = s // 3
        n, i, cur = len(arr), 0, 0
        while i < n:
            cur += arr[i]
            i += 1
            if cur == target:
                break

        if cur != target:
            return False
        while i + 1 < n:
            cur += arr[i]
            if cur == target * 2:
                return True
            i += 1
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1323. 6和9组成的最大数字

给你一个仅由数字 6 和 9 组成的正整数 num。你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成6。请返回你可以得到的最大数字。

把第一个6变为9就行了

class Solution:
    def maximum69Number (self, num: int) -> int:
        num_ = list(str(num))
        for i in range(len(num_)):
            if num_[i] == '6':
                num_[i] = '9'
                break
        ret = ''
        for j in num_:
            ret += j
        return int(ret)
1
2
3
4
5
6
7
8
9
10
11
'运行

class Solution:
    def maximum69Number (self, num: int) -> int:
        return int(str(num).replace('6', '9', 1))
1
2
3
'运行

1403.非递增顺序的最小子序列

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。注意，题目数据保证满足所有约束条件的解决方案是唯一的。同时，返回的答案应当按非递增顺序排列。

降序排序，只要大于sum(nums)的一半就行

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True)
        s = sum(nums)
        if len(nums) == 1:
            return nums
        if len(nums) == 2 and len(set(nums)) == 1:
            return nums
        for i in range(1, len(nums)):
            if sum(nums[:i]) > s // 2: # 只要大于sum(nums)的一半就行
                return nums[:i]
1
2
3
4
5
6
7
8
9
10
11

1710. 卡车上的最大单元数

请你将一些箱子装在一辆卡车上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：

numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。

整数 truckSize 表示卡车上可以装载箱子的最大数量。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。返回卡车可以装载单元的最大总数。

按装载单元数量降序排序

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: x[1], reverse=True)
        m = len(boxTypes)
        count = 0
        for i in range(m):
            if boxTypes[i][0] < truckSize:
                count += boxTypes[i][1] * boxTypes[i][0]
                truckSize -= boxTypes[i][0]
            else:
                count += truckSize * boxTypes[i][1]
                break
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13

$\quad$
$\quad$
$\quad$

以上题解大多来自【代码随想录】（里面有更详细的讲解，强推！！），在此基础上做了一定总结，并附带一些自己的理解。

后续题目，随缘更新~

END

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/830144