贪心算法

  • 贪心算法介绍
    • 1. 柠檬水找零
    • 2. 将数组和减半的最少操作次数
    • 3. 最大数
    • 4. 摆动序列(贪心思路)
    • 5. 最长递增子序列(贪心算法)
    • 6. 递增的三元子序列
    • 7. 最长连续递增序列
    • 8. 买卖股票的最佳时机
    • 9. 买卖股票的最佳时机Ⅱ(贪心算法)
    • 10. K 次取反后最大化的数组和
    • 11. 按身高排序
    • 12. 优势洗牌
    • 13. 最长回文串
    • 14. 增减字符串匹配
    • 15. 分发饼干
    • 16. 最优除法
    • 17. 跳跃游戏Ⅱ
    • 18. 跳跃游戏
    • 19. 加油站
    • 20. 单调递增的数字

贪心算法介绍

什么是贪心算法呢？

首先，我们需要知道贪心策略，即解决问题的策略，将局部最优转变为全局最优；

  • 把解决问题的过程分为若干步；
  • 解决每一步的时候，都选择当前看起来”最优的”解法；
  • “希望”得到全局最优解

贪心算法的特点：

  1. 提出贪心策略，但是贪心策略的提出是没有标准和模板的，可能每一道题的贪心策略都是不同的；
  2. 贪心策略的正确性没有保障，因为我们提出的”贪心策略”有可能是错误的，正确的贪心策略是需要”证明的”；常用的证明方法是我们学过的数学中见过的证明方法。

下面我们结合题目进行分析。

1. 柠檬水找零

题目链接 -> Leetcode -860.柠檬水找零

Leetcode -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^5
  • bills[i] 不是 5 就是 10 或是 20

贪⼼策略：分情况讨论：

  • 遇到 5 元钱，直接收下；
  • 遇到 10 元钱，找零 5 元钱之后，收下；
  • 遇到 20 元钱：
    • 先尝试凑 10 + 5 的组合；
    • 如果凑不出来，拼凑 5 + 5 + 5 的组合；

代码如下：

class Solution {public:bool lemonadeChange(vector& bills){int five = 0, ten = 0;for(int i = 0; i = 3){five -= 3;}else{return false;}}}return true;}};

2. 将数组和减半的最少操作次数

题目链接 -> Leetcode -2208.将数组和减半的最少操作次数

Leetcode -2208.将数组和减半的最少操作次数

题目：给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

示例 1：
输入：nums = [5, 19, 8, 1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为[5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 – 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33 / 2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

示例 2：
输入：nums = [3, 8, 20]
输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为[1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 – 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31 / 2 = 15.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^7

贪心策略：

  • 每次挑选出「当前」数组中「最大」的数，然后「减半」；
  • 直到数组和减少到至少一半为止。

为了「快速」挑选出数组中最大的数，我们可以利用「堆」这个数据结构。

代码如下：

class Solution {public:int halveArray(vector& nums) {int ret = 0;double sum = 0;priority_queue pq;// 统计数组总和，并将元素放入大堆中for(auto& num : nums) {sum += num;pq.push(num);}// sum 取一半，每次取当前数组中最大的元素减少一半，sum 并减去这个数，然后更新大堆，统计操作次数sum /= 2.0;while(sum > 0){double num = pq.top() / 2.0;pq.pop();sum -= num;pq.push(num);ret++;}return ret;}};

3. 最大数

题目链接 -> Leetcode -179.最大数

Leetcode -179.最大数

题目：给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：
输入：nums = [10, 2]
输出：“210”

示例 2：
输入：nums = [3, 30, 34, 5, 9]
输出：“9534330”

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 10^9

思路：贪心，可以先优化，将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及比较操作就会很方便。

贪心策略：按照题目的要求，重新定义一个新的排序规则，然后排序即可。

我们定义的排序规则：

  • 「A 拼接 B」 大于 「B 拼接 A」，那么 A 在前，B 在后；
  • 「A 拼接 B」 等于 「B 拼接 A」，那么 A B 的顺序无所谓；
  • 「A 拼接 B」 小于 「B 拼接 A」，那么 B 在前，A 在后；

例如 [“10”, “2”] 两个数，“10” 和 “2” 拼接为 “102”；“2” 和 “10” 拼接为 “210”；因为按字典序比较 “210” 大于 “102”，所以 “210” 在前面。

代码如下：

class mysort{public:bool operator()(const string& x, const string& y){return x + y > y + x;}};class Solution {public:string largestNumber(vector& nums) {// 先将数字转为字符串放入 strs 中vector strs;for(auto& num : nums) strs.push_back(to_string(num));// 按仿函数的方法排序sort(strs.begin(), strs.end(), mysort());// 将排好序的字符串拼接起来放入 ret 中string ret;for(auto& str : strs) ret += str;// 如果第一位为 0 就返回 0if(ret[0] == '0') return "0";return ret;}};

4. 摆动序列(贪心思路)

题目链接 -> Leetcode -376.摆动序列

Leetcode -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

思路：贪心算法，其中这道题我们在动态规划专题也做过。这道题的贪心策略：对于某一个位置来说：

  • 如果接下来呈现上升趋势的话，我们让其上升到波峰的位置；
  • 如果接下来呈现下降趋势的话，我们让其下降到波谷的位置。

因此，如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波谷的个数即可。

代码如下：

class Solution {public:int wiggleMaxLength(vector& nums) {if(nums.size() < 2) return nums.size();// right 代表后一个数减去当前这个数的差，正数代表上升趋势，负数代表下降趋势，即当前这个数右边数的趋势// left 代表当前这个数左边数的趋势，0代表不确定，因为首尾位置必选，所以初始化的时候给 left 初始化为0int left = 0, right = 0, ret = 0;for(int i = 0; i < nums.size() - 1; i++){right = nums[i + 1] - nums[i];if(right == 0) continue; // 忽略掉相同的数if(right * left <= 0) ret++;left = right;}// 加上最后一个位置return ++ret;}};

5. 最长递增子序列(贪心算法)

题目链接 -> Leetcode -300.最长递增子序列

Leetcode -300.最长递增子序列

题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3, 6, 2, 7] 是数组[0, 3, 1, 6, 2, 2, 7] 的子序列。

示例 1：
输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出：4
解释：最长递增子序列是[2, 3, 7, 101]，因此长度为 4 。

示例 2：
输入：nums = [0, 1, 0, 3, 2, 3]
输出：4

示例 3：
输入：nums = [7, 7, 7, 7, 7, 7, 7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

贪心策略：我们在考虑最长递增子序列的长度的时候，其实并不关心这个序列长什么样子，我们只是关心最后一个元素是谁。这样新来一个元素之后，我们就可以判断是否可以拼接到它的后面。

因此，我们可以创建一个数组，统计长度为 x 的递增子序列中，最后一个元素是谁。为了尽可能的让这个序列更长，我们仅需统计长度为 x 的所有递增序列中最后一个元素的「最小值」。

统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使用「二分」来查找插入位置。

代码如下：

class Solution {public:int lengthOfLIS(vector& nums){int n = nums.size();vector ret;ret.push_back(nums[0]);for(int i = 1; i  ret.back()){ret.push_back(nums[i]);}else{// 利用二分插入（ret数组已经有序）// 找出第一次大于等于 nums[i] 的元素，使 nums[i] 替代它的位置int left = 0, right = ret.size() - 1;while(left = nums[i]) right = mid;else left = mid + 1;}ret[left] = nums[i];}}return ret.size();}};

6. 递增的三元子序列

题目链接 -> Leetcode -334.递增的三元子序列

Leetcode -334.递增的三元子序列

题目：给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标(i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1, 2, 3, 4, 5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：
输入：nums = [5, 4, 3, 2, 1]
输出：false
解释：不存在满足题意的三元组

示例 3：
输入：nums = [2, 1, 5, 0, 4, 6]
输出：true
解释：三元组(3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

  • 1 <= nums.length <= 5 * 10^5
  • -2^31 <= nums[i] <= 2^31 – 1

贪心策略：最长递增子序列的简化版。不用一个数组存数据，仅需两个变量即可。也不用二分插入位置，仅需两次比较就可以找到插入位置。

代码如下：

class Solution {public:bool increasingTriplet(vector& nums) {int n = nums.size();int x = nums[0], y = INT_MAX;for(int i = 1; i  y) return true; // 如果 nums[i] 大于 y，说明它可以放在 y 后面，这时候长度为3，直接返回 trueelse if(nums[i] > x) y = nums[i]; // 如果nums[i]大于x，说明它的大小位于 x 和 y 之间，所以可以替代 yelse x = nums[i]; // 否则，就是比 x 小，可以替代x}return false;}};

7. 最长连续递增序列

题目链接 -> Leetcode -674.最长连续递增序列

Leetcode -674.最长连续递增序列

题目：给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列[nums[l], nums[l + 1], …, nums[r – 1], nums[r]] 就是连续递增子序列。

示例 1：
输入：nums = [1, 3, 5, 4, 7]
输出：3
解释：最长连续递增序列是[1, 3, 5], 长度为3。
尽管[1, 3, 5, 7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：
输入：nums = [2, 2, 2, 2, 2]
输出：1
解释：最长连续递增序列是[2], 长度为1。

提示：

  • 1 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9

思路：思路与 第五题 类似，区别在于本题是要找连续的区间，所以当我们找到开始不连续的元素时，将 ret 数组清空，重新插入；每次判断结束判断找到最长递增序列。

代码如下：

class Solution {public:int findLengthOfLCIS(vector& nums) {int ans = 1;vector ret; ret.push_back(nums[0]);for(int i = 1; i  ret.back()) {ret.push_back(nums[i]);}else{ret.clear();ret.push_back(nums[i]);}ans = fmax(ans, ret.size());}return ans;}};

8. 买卖股票的最佳时机

题目链接 -> Leetcode -121.买卖股票的最佳时机

Leetcode -121.买卖股票的最佳时机

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7, 1, 5, 3, 6, 4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6 – 1 = 5 。
注意利润不能是 7 – 1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7, 6, 4, 3, 1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

思路：由于只能交易一次，所以对于某一个位置 i ，要想获得最大利润，仅需知道前⾯所有元素的最小值。然后在最小值的位置「买入」股票，在当前位置「卖出」股票即可。

代码如下：

class Solution {public:int maxProfit(vector& prices){int prevMin = INT_MAX, ret = 0;for (auto& p : prices){ret = max(ret, p - prevMin); // 记录最大利润prevMin = min(prevMin, p);// 记录最小买入价格}return ret;}};

9. 买卖股票的最佳时机Ⅱ(贪心算法)

题目链接 -> Leetcode -122.买卖股票的最佳时机Ⅱ

Leetcode -122.买卖股票的最佳时机Ⅱ

题目：给你一个整数数组 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^4
  • 0 <= prices[i] <= 10^4

贪心策略：由于可以进行无限次交易，所以只要是一个「上升区域」，我们就把利润拿到手就好了，即需要找到一个区间上升的末端，所以我们可以是使用双指针来寻找。

代码如下：

class Solution {public:int maxProfit(vector& prices) {// 贪心 + 双指针int ret = 0;for(int start = 0; start < prices.size();){int end = start + 1;// 找到上升的末端while(end  prices[end - 1]) end++;// 利润等于上升的末端 - 上升区间的起始，如果不是上升的区间，即是自己减去自己，不影响ret += prices[end - 1] - prices[start];start = end;}return ret;}};

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

题目链接 -> Leetcode -1005.K 次取反后最大化的数组和

Leetcode -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^4
  • -100 <= nums[i] <= 100
  • 1 <= k <= 10^4

贪心策略：每次只需把最小的改变符号即可，所以我们可以借助优先级队列完成。

代码如下：

class Solution {public:void GetTopToOpNum(priority_queue<int, vector, greater>& pq){int num = pq.top();pq.pop();num = -num;pq.push(num);}int largestSumAfterKNegations(vector& nums, int k) {int ret = 0;priority_queue<int, vector, greater> pq;for(auto& num : nums)pq.push(num);// 每次取最小的变正数while(k--) GetTopToOpNum(pq);while(!pq.empty()){ret += pq.top();pq.pop();}return ret;}};

11. 按身高排序

注意：本题没有用到贪心的思想，是为了下一题田忌赛马做准备。

题目链接 -> Leetcode -2418.按身高排序

Leetcode -2418.按身高排序

题目：给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高 降序 顺序返回对应的名字数组 names 。

示例 1：
输入：names = [“Mary”, “John”, “Emma”], heights = [180, 165, 170]
输出：[“Mary”, “Emma”, “John”]
解释：Mary 最高，接着是 Emma 和 John 。

示例 2：
输入：names = [“Alice”, “Bob”, “Bob”], heights = [155, 185, 150]
输出：[“Bob”, “Alice”, “Bob”]
解释：第一个 Bob 最高，然后是 Alice 和第二个 Bob 。

提示：

  • n == names.length == heights.length
  • 1 <= n <= 10^3
  • 1 <= names[i].length <= 20
  • 1 <= heights[i] <= 10^5
  • names[i] 由大小写英文字母组成
  • heights 中的所有值互不相同

思路：我们不能直接按照 i 位置对应的 heights 来排序，因为排序过程是会移动元素的，但是 names 内的元素是不会移动的。由题意可知，names 数组和 heights 数组的下标是一一对应的，因此我们可以重新创建出来一个下标数组，将这个下标数组按照 heights[i] 的大小排序。那么，当下标数组排完序之后，里面的顺序就相当于 heights 这个数组排完序之后的下标。之后通过排序后的下标，依次找到原来的 name ，完成对名字的排序。

代码如下：

class Solution {public:vector sortPeople(vector& names, vector& heights) {int n = heights.size();// 创建一个下标数组，用这个数组重写排序方法，按照身高排序，再利用这个下标数组找到对应的身高和名字vector index;for(int i = 0; i  heights[j];});vector ret;for(int i = 0; i < n; i++)ret.push_back(names[index[i]]);return ret;}};

12. 优势洗牌

题目链接 -> Leetcode -870.优势洗牌

Leetcode -870.优势洗牌

题目：给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：
输入：nums1 = [2, 7, 11, 15], nums2 = [1, 10, 4, 11]
输出：[2, 11, 7, 15]

示例 2：
输入：nums1 = [12, 24, 8, 32], nums2 = [13, 25, 32, 11]
输出：[24, 32, 8, 12]

提示：

  • 1 <= nums1.length <= 10^5
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 10^9

思路：在做此题之前我们需要了解一个故事：田忌赛马。由田忌赛马的故事我们可以得出一个最优的决策方式：

  • 当己方此时最差的比不过对面最差的时候，让我方最差的去换取掉对面最好的（反正都要输，不如去拖掉对面一个最强的）；
  • 当己方此时最差的能比得上对面最差的时候，就让两者比对下去（最差的都能获胜，为什么还要输呢？）。

由此我们每次的决策，都会使我方处于优势。

代码如下：

class Solution {public:vector advantageCount(vector& nums1, vector& nums2) {int n = nums2.size();vector index(n);for(int i = 0; i < n; i++) index[i] = i;sort(nums1.begin(), nums1.end());// 对nums1排序sort(index.begin(), index.end(), [&](int x, int y) {return nums2[x] < nums2[y];}); //对nums2的下标数组重写排序方法vector ret(n);int left = 0, right = n - 1; // left 和 right 指向index数组的下标// 田忌赛马（贪心）// 遍历 nums1 数组，用nums1的下等马(最小数)跟nums2的下等马(最小数)比较，如果比nums2中的马大，就直接放入ret数组中以 index[left] 为下标的位置，然后 left 迭代往后走；否则用 nums1 的下等马(最小数) 换取 nums2 的上等马(最大数)，然后 right 迭代往前走for(auto& num : nums1){if(num > nums2[index[left]]) ret[index[left++]] = num;else ret[index[right--]] = num;}return ret;}};

13. 最长回文串

题目链接 -> Leetcode -409.最长回文串

Leetcode -409.最长回文串

题目：给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

示例 1:
输入:s = “abccccdd”
输出 : 7
解释 :
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。

示例 2 :
输入 : s = “a”
输出 : 1

示例 3：
输入 : s = “aaaaaccc”
输出 : 7

提示 :

  • 1 <= s.length <= 2000
  • s 只由小写 和 / 或 大写英文字母组成

贪心策略：用尽可能多的字符去构造回文串：

  • 如果字符出现偶数个，那么全部都可以用来构造回文串；
  • 如果字符出现奇数个，减去一个之后，剩下的字符能够全部用来构造回文串；
  • 最后再判断一下，如果有字符出现奇数个，就把它单独拿出来放在中间；

代码如下：

class Solution {public:int longestPalindrome(string s) {vector arr(128);for(auto& ch : s) arr[ch - 'A']++;bool flag = true;int ret = 0;for(int i = 0; i < 128; i++){// 偶数个if(arr[i] % 2 == 0) {ret += arr[i];}// 奇数个else{if(flag){ret += arr[i];flag = false;}else{ret += arr[i] - 1;}}}return ret;}};

14. 增减字符串匹配

题目链接 -> Leetcode -942.增减字符串匹配

Leetcode -942.增减字符串匹配

题目：由范围[0, n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中 :

如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

示例 1：
输入：s = “IDID”
输出：[0, 4, 1, 3, 2]

示例 2：
输入：s = “III”
输出：[0, 1, 2, 3]

示例 3：
输入：s = “DDI”
输出：[3, 2, 0, 1]

提示：

  • 1 <= s.length <= 10^5
  • s 只包含字符 “I” 或 “D”

贪心策略：

  • 当遇到 ‘I’ 的时候，为了让下一个上升的数可选择的「范围更多」，当前选择「最小」的那个数；

  • 当遇到 ‘D’ 的时候，为了让下一个下降的数可选择的「范围更多」，选择当前「最大」的那个数。

    class Solution {public:vector diStringMatch(string s) {vector ret;// left 和 right 分别标记最大值和最小值int left = 0, right = s.size();for(auto& ch : s){if(ch == 'I') ret.push_back(left++);else ret.push_back(right--);}// 把最后一个数放进去ret.push_back(left);return ret;}};

15. 分发饼干

题目链接 -> Leetcode -455.分发饼干

Leetcode -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^4
  • 0 <= s.length <= 3 * 10^4
  • 1 <= g[i], s[j] <= 2^31 – 1

贪心策略：先将两个数组排序。针对胃口较小的孩子，从小到大挑选饼干：

  • 如果当前饼干能满足，直接喂给这个孩子（最小的饼干都能满足，不要浪费大饼干）；
  • 如果当前饼干不能满足，放弃这个饼干，去检测下一个饼干（这个饼干连最小胃口的孩子都无法满足，其它的孩子也不能满足）。

代码如下：

class Solution {public:int findContentChildren(vector& g, vector& s) { // 排序sort(g.begin(), g.end());sort(s.begin(), s.end());int kids = 0, mine = 0, ret = 0;while(kids < g.size() && mine < s.size()){// 如果能够满足当前孩子，就把饼干分给这个孩子if(g[kids] <= s[mine]){kids++;ret++;}// 无论满不满足当前孩子，都要往下遍历饼干mine++;}return ret;}};

16. 最优除法

题目链接 -> Leetcode -553.最优除法

Leetcode -553.最优除法

题目：给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如，[2, 3, 4] -> 2 / 3 / 4 。

例如，nums = [2, 3, 4]，我们将求表达式的值 “2/3/4”。
但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意：你的表达式不应该包含多余的括号。

示例 1：
输入 : [1000, 100, 10, 2]
输出 : “1000/(100/10/2)”
解释 : 1000 / (100 / 10 / 2) = 1000 / ((100 / 10) / 2) = 200
但是，以下加粗的括号 “1000/((100/10)/2)” 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 “1000/(100/10/2)”。
其他用例 :
1000 / (100 / 10) / 2 = 50
1000 / (100 / (10 / 2)) = 50
1000 / 100 / 10 / 2 = 0.5
1000 / 100 / (10 / 2) = 2

示例 2:
输入: nums = [2, 3, 4]
输出 : “2/(3/4)”
解释 : (2 / (3 / 4)) = 8 / 3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

说明 :

  • 1 <= nums.length <= 10
  • 2 <= nums[i] <= 1000

对于给定的输入只有一种最优除法。

贪心策略：在最终的结果中，前两个数的位置是无法改变的。
因为每一个数的都是大于等于 2 的，为了让结果更大，我们应该尽可能的把剩下的数全都放在「分子」上。

代码如下：

class Solution {public:string optimalDivision(vector& nums) {//在最终的结果中，前两个数的位置是无法改变的。//因为每⼀个数都是大于等于 2 的，为了让结果更大，我们应该尽可能的把剩下的数全都放在分⼦上if(nums.size() == 1) return to_string(nums[0]);if(nums.size() == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);for(int i = 2; i < nums.size(); i++){ret += "/" + to_string(nums[i]);}ret += ")";return ret;}};

17. 跳跃游戏Ⅱ

题目链接 -> Leetcode -45.跳跃游戏Ⅱ

Leetcode -45.跳跃游戏Ⅱ

题目：给定一个长度为 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^4
  • 0 <= nums[i] <= 1000

题目保证可以到达 nums[n – 1]

思路：类似层序遍历的过程：用类似层序遍历的过程，将第 i 次跳跃的「起始位置」和「结束位置」找出来，用这次跳跃的情况，更新出下一次跳跃的「起始位置」和「终止位置」。这样「循环往复」，就能更新出到达 n – 1 位置的最小跳跃步数。

代码如下：

class Solution {public:int jump(vector& nums) {//⽤类似层序遍历的过程，将第 i 次跳跃的「起始位置」和「结束位置」找出来，⽤这次跳跃的情况，更新出下⼀次跳跃的「起始位置」和「终⽌位置」int left = 0, right = 0, maxPos = 0, ret = 0;while(left = nums.size() - 1) return ret;for(int i = left; i <= right; i++){maxPos = max(i + nums[i], maxPos);}left = right + 1;right = maxPos;ret++;}return -1; // 跳不到的情况}};

18. 跳跃游戏

题目链接 -> Leetcode -55.跳跃游戏

Leetcode -55.跳跃游戏

题目：给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 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 <= 10^4
  • 0 <= nums[i] <= 10^5

思路：和 跳跃游戏II 一样，仅需修改一下返回值即可。

代码如下：

class Solution {public:bool canJump(vector& nums) {// 和跳跃游戏Ⅱ的思路一样int left = 0, right = 0, maxPos = 0, n = nums.size();while(left = n - 1) return true;for(int i = left; i <= right; i++){maxPos = max(maxPos, nums[i] + i);}left = right + 1;right = maxPos;}return false;}};

19. 加油站

题目链接 -> Leetcode -134.加油站

Leetcode -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^5
  • 0 <= gas[i], cost[i] <= 10^4

思路：依次枚举所有的起点；从起点开始，模拟⼀遍加油的流程；使用贪⼼优化：我们发现，当从 i 位置出发，⾛了 step 步之后，如果失败了。那么 [i, i + step] 这个区间内任意⼀个位置作为起点，都不可能环绕⼀圈。因此我们枚举的下⼀个起点，应该是 i + step + 1.

代码如下：

class Solution {public:int canCompleteCircuit(vector& gas, vector& cost) {int n = gas.size();// 暴力枚举每一个位置，模拟从每个位置开始出发，能不能回到原位，使用step 变量标记走了多少步for(int i = 0; i < n; i++){int rest = 0, step = 0; // step 记录走的步数，判断是否已经走了一圈for(; step < n; step++){int index = (i + step) % n;// 使下标呈环状，当越界时继续返回数组的起始位置rest = rest + gas[index] - cost[index];if(rest = 0) return i;// 优化，不加这句会超时；这句话的原理就是假设我们从a位置开始枚举到d位置，发现不行，那么从b、c位置开始枚举到d也是不行的，所以我们直接让i跳过step步，从它的下一步开始枚举（循环内会++）i += step;}return -1;}};

20. 单调递增的数字

题目链接 -> Leetcode -738.单调递增的数字

Leetcode -738.单调递增的数字

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

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

示例 1:
输入: n = 10
输出: 9

示例 2:
输入: n = 1234
输出: 1234

示例 3:
输入: n = 332
输出: 299

提示:

  • 0 <= n <= 10^9

思路：

  1. 将整数 n 转换为字符串形式，以便于对其进⾏修改操作，并将其存储在字符串变量 str 中。
  2. 初始化⼀个变量 pos，⽤于记录从⾼位到低位第⼀个不满⾜单调递增的数字的位置。初始值为 -1，表示在第⼀位之前。
  3. 从⾼位到低位遍历字符串 str，寻找第⼀个不满⾜单调递增的数字的位置。当遇到⼀个数字⼩于前⼀个数字时，记录这个位置为 pos，并退出循环。
  4. 如果 pos 被更新，说明存在需要修改的数字，执⾏以下操作：

a. 将 pos 位置后的所有数字修改为 9，这样可以保证修改后的数字是最⼤的。

b. 将 pos 位置的数字减⼀，因为这是最⼩的减少量，同时也能够保证修改后的数字仍然⼩于原数字 n.

c. 检查 pos 前⼀位数字是否⼩于减⼀后的 pos 位置数字，如果⼩于，则说明在 pos 位置之前还有相同的数字，需要将 pos 前⼀位数字减⼀，并将 pos 位置修改为 9。

d.重复这个操作，直到 pos 前⼀位数字⼤于等于减⼀后的 pos 位置数字或 pos 已经移动到了第⼀位。

  1. 将修改后的字符串 str 转换为整型数字并返回。

代码如下：

class Solution {public:int monotoneIncreasingDigits(int n) {string str = to_string(n);int index = 0;// 找到第一个递减的位置while(index + 1 < str.size() && str[index] = 0 && str[index] == str[index - 1]) index--;str[index]--; // 找到后减一// 后面的全变9for(int i = index + 1; i < str.size(); i++)str[i] = '9';return stoi(str);}};