贪心算法
贪心算法介绍
什么是贪心算法呢？
首先，我们需要知道贪心策略，即解决问题的策略，将局部最优转变为全局最优；
- 把解决问题的过程分为若干步；
- 解决每一步的时候，都选择当前看起来"最优的"解法；
- "希望"得到全局最优解
贪心算法的特点：
- 提出贪心策略，但是贪心策略的提出是没有标准和模板的，可能每一道题的贪心策略都是不同的；
- 贪心策略的正确性没有保障，因为我们提出的"贪心策略"有可能是错误的，正确的贪心策略是需要"证明的"；常用的证明方法是我们学过的数学中见过的证明方法。
下面我们结合题目进行分析。
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<int>& bills)
{
int five = 0, ten = 0;
for(int i = 0; i < bills.size(); i++)
{
// 5 元
if(bills[i] == 5)
{
five++;
}
// 10元
else if(bills[i] == 10)
{
ten++;
if(five == 0) return false;
five--;
}
// 20 元
else
{
// 5 块和 10 块都有的时候优先找5+10
if(five && ten)
{
ten--;
five--;
}
else if(five >= 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<int>& nums)
{
int ret = 0;
double sum = 0;
priority_queue<double> 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<int>& nums)
{
// 先将数字转为字符串放入 strs 中
vector<string> 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 就返回 0
if(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<int>& nums)
{
if(nums.size() < 2) return nums.size();
// right 代表后一个数减去当前这个数的差，正数代表上升趋势，负数代表下降趋势，即当前这个数右边数的趋势
// left 代表当前这个数左边数的趋势，0代表不确定，因为首尾位置必选，所以初始化的时候给 left 初始化为0
int 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<int>& nums)
{
int n = nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i = 1; i < n; i++)
{
// 因为我们的思路是会让数组有序的，所以当 nums[i ]大于 ret 数组最后一个元素就直接尾插
if(nums[i] > ret.back())
{
ret.push_back(nums[i]);
}
else
{
// 利用二分插入（ret数组已经有序）
// 找出第一次大于等于 nums[i] 的元素，使 nums[i] 替代它的位置
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(ret[mid] >= 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<int>& nums)
{
int n = nums.size();
int x = nums[0], y = INT_MAX;
for(int i = 1; i < n; i++)
{
if(nums[i] > y) return true; // 如果 nums[i] 大于 y，说明它可以放在 y 后面，这时候长度为3，直接返回 true
else if(nums[i] > x) y = nums[i]; // 如果nums[i]大于x，说明它的大小位于 x 和 y 之间，所以可以替代 y
else 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<int>& nums)
{
int ans = 1;
vector<int> ret;
ret.push_back(nums[0]);
for(int i = 1; i < nums.size(); i++)
{
if(nums[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<int>& 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<int>& prices)
{
// 贪心 + 双指针
int ret = 0;
for(int start = 0; start < prices.size();)
{
int end = start + 1;
// 找到上升的末端
while(end < prices.size() && prices[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<int>, greater<int>>& pq)
{
int num = pq.top();
pq.pop();
num = -num;
pq.push(num);
}
int largestSumAfterKNegations(vector<int>& nums, int k)
{
int ret = 0;
priority_queue<int, vector<int>, greater<int>> 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<string> sortPeople(vector<string>& names, vector<int>& heights)
{
int n = heights.size();
// 创建一个下标数组，用这个数组重写排序方法，按照身高排序，再利用这个下标数组找到对应的身高和名字
vector<int> index;
for(int i = 0; i < n; i++) index.push_back(i);
// 对下标进行排序
sort(index.begin(), index.end(), [&](int i, int j)
{
return heights[i] > heights[j];
});
vector<string> 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<int> advantageCount(vector<int>& nums1, vector<int>& nums2)
{
int n = nums2.size();
vector<int> 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<int> 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<int> 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<int> diStringMatch(string s) { vector<int> 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<int>& g, vector<int>& 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<int>& 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<int>& nums)
{
//⽤类似层序遍历的过程，将第 i 次跳跃的「起始位置」和「结束位置」找出来，⽤这次跳跃的情况，更新出下⼀次跳跃的「起始位置」和「终⽌位置」
int left = 0, right = 0, maxPos = 0, ret = 0;
while(left <= right) // 以防跳不到 n - 1位置
{
// 先判断⼀下是否已经能跳到最后⼀个位置
if(maxPos >= 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<int>& nums)
{
// 和跳跃游戏Ⅱ的思路一样
int left = 0, right = 0, maxPos = 0, n = nums.size();
while(left <= right)
{
if(maxPos >= 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<int>& gas, vector<int>& 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) break;
}
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
思路：
- 将整数 n 转换为字符串形式，以便于对其进⾏修改操作，并将其存储在字符串变量 str 中。
- 初始化⼀个变量 pos，⽤于记录从⾼位到低位第⼀个不满⾜单调递增的数字的位置。初始值为 -1，表示在第⼀位之前。
- 从⾼位到低位遍历字符串 str，寻找第⼀个不满⾜单调递增的数字的位置。当遇到⼀个数字⼩于前⼀个数字时，记录这个位置为 pos，并退出循环。
- 如果 pos 被更新，说明存在需要修改的数字，执⾏以下操作：
a. 将 pos 位置后的所有数字修改为 9，这样可以保证修改后的数字是最⼤的。
b. 将 pos 位置的数字减⼀，因为这是最⼩的减少量，同时也能够保证修改后的数字仍然⼩于原数字 n.
c. 检查 pos 前⼀位数字是否⼩于减⼀后的 pos 位置数字，如果⼩于，则说明在 pos 位置之前还有相同的数字，需要将 pos 前⼀位数字减⼀，并将 pos 位置修改为 9。
d.重复这个操作，直到 pos 前⼀位数字⼤于等于减⼀后的 pos 位置数字或 pos 已经移动到了第⼀位。
- 将修改后的字符串 str 转换为整型数字并返回。
代码如下：
class Solution {
public:
int monotoneIncreasingDigits(int n)
{
string str = to_string(n);
int index = 0;
// 找到第一个递减的位置
while(index + 1 < str.size() && str[index] <= str[index + 1]) index++;
if(index + 1 == str.size()) return n; // 全是递增的情况
// 回推，如果第一个递减的位置的数字相同，找到最高位的那个
while(index - 1 >= 0 && str[index] == str[index - 1]) index--;
str[index]--; // 找到后减一
// 后面的全变9
for(int i = index + 1; i < str.size(); i++)
str[i] = '9';
return stoi(str);
}
};
版权归原作者 YoungMLet 所有， 如有侵权，请联系我们删除。