目录
①力扣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^40 <= s.length <= 3 * 10^41 <= g[i], s[j] <= 2^31 - 1
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
}
};解析代码
贪心策略：先将两个数组排序。针对胃口较小的孩子，从小到大挑选饼干：
- 如果当前饼干能满足，直接喂（最小的饼干都能满足，不要浪费大饼干）。
- 如果当前饼干不能满足，放弃这个饼干，去检测下一个饼干（这个饼⼲连最小胃口的孩子都无法满足，更别提那些胃口大的孩子了）。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int cur1 = 0, cur2 = 0, sz1 = g.size(), sz2 = s.size(), ret = 0;
while(cur1 < sz1 && cur2 < sz2)
{
if(s[cur2] >= g[cur1])
++ret, ++cur1, ++cur2;
else
++cur2;
}
return ret;
}
};
②力扣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 <= 102 <= nums[i] <= 1000- 对于给定的输入只有一种最优除法。
class Solution {
public:
string optimalDivision(vector<int>& nums) {
}
};解析代码
贪心策略：（如果想到下面与数学相关的策略，代码就很简单）
无论这个括号放到哪里，最终都会得到 x / y 的形式，所以要让分子x尽可能大，分母y尽可能小。在最终的结果中，前两个数的位置是无法改变的（第一个数在分子，第二个数在分母）。因为每一个数的都是大于等于 2 的，为了让结果更大，我们应该尽可能的把剩下的数全都放在分子上。
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
if(n == 1)
return to_string(nums[0]);
if(n == 2)
return to_string(nums[0]) + '/' + to_string(nums[1]);
string ret;
for(int i = 0; i < n; ++i)
{
if(i == 1)
ret += '(';
ret += to_string(nums[i]);
if(i != n - 1)
ret += '/';
}
return ret + ')';
}
};③力扣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^40 <= nums[i] <= 1000- 题目保证可以到达
nums[n-1]
class Solution {
public:
int jump(vector<int>& nums) {
}
};解析代码1_动态规划
动态规划解法：（时间是O（N^2），刚好能AC，下面的贪心解法是O（N））
状态表示：dp[i] 表⽰从 0 位置开始，到达 i 位置时候的最小跳跃次数
状态转移方程：对于 dp[i] ，遍历 0 ~ i - 1 区间（用指针 j 表示），只要能够从 j 位置跳到 i 位置（ nums[j] + j >= i ），就用 dp[j] + 1 更新 dp[i] 里面的值，找到所有情况下的最小值即可。
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[j] + j >= i)
{
dp[i] = dp[j] + 1;
break;
}
}
}
return dp[n -1];
}
};
解析代码2_贪心
用类似层序遍历的过程，将第 i 次跳跃的起始位置和结束位置找出来，用这次跳跃的情况，更新出下一次跳跃的起始位置和结束位置。这样循环往复，就能更新出到达 n - 1 位置的最小跳跃步数。时间复杂度是O（N）。
class Solution {
public:
int jump(vector<int>& nums) {
int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
// 这一次起跳的左端点，右端点，下一次起跳的右端点
while(left <= right)
{
if(maxPos >= n - 1)
return ret;
for(int i = left; i <= right; ++i)
{
maxPos = max(maxPos, i + nums[i]);
}
left = right + 1; // 更新起跳左右端点并++ret
right = maxPos;
++ret;
}
return -1; // 不会走到这
}
};
④力扣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^40 <= nums[i] <= 10^5
class Solution {
public:
int canJump(vector<int>& nums) {
}
};解析代码
（和力扣45. 跳跃游戏 II基本一样，只需修改返回值，可以重敲一遍看有没有掌握）用类似层序遍历的过程，将第 i 次跳跃的起始位置和结束位置找出来，用这次跳跃的情况，更新出下一次跳跃的起始位置和结束位置。这样循环往复，就能更新出到达 n - 1 位置的最小跳跃步数。时间复杂度是O（N）。
class Solution {
public:
int canJump(vector<int>& nums) {
int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
// 这一次起跳的左端点，右端点，下一次起跳的右端点
while(left <= right)
{
if(maxPos >= n - 1)
return true;
for(int i = left; i <= right; ++i)
{
maxPos = max(maxPos, i + nums[i]);
}
left = right + 1; // 更新起跳左右端点并++ret
right = maxPos;
++ret;
}
return false;
}
};
⑤力扣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 == ncost.length == n1 <= n <= 10^50 <= gas[i], cost[i] <= 10^4
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
}
};解析代码
暴力解法：依次枚举所有的起点，从起点开始，模拟一遍加油的流程。
下面是暴力解法的代码（时间复杂度是O（N^2），会超时）
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for(int i = 0; i < n; ++i)
{
int diff = 0, step = 0;
for(; step < n; ++step)
{
int index = (i + step) % n; // 求出⾛ step 步之后的下标
diff += gas[index] - cost[index];
if(diff < 0)
break;
}
if(diff >= 0) // 正常跳出
return i;
}
return -1;
}
};贪心优化：发现当从 i 位置出发，走了 step 步之后，如果失败了。那么 [i, i + step] 这个区间内任意一位置作为起点，都不可能环绕一圈（假设 i 位置有一个和暴力解法里面的diff，区间左边的diff肯定是大于0的，否则不能走到右边，如果减去左边的区间，从中间的区间某一个 i 开始，则肯定也是失败的，因为减的是大于0的）。因此枚举的下一个起点，应该是 i + step + 1 。
只需在暴力的解法加上一句代码，时间复杂度就从O（N^2）变为O（N）：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for(int i = 0; i < n; ++i)
{
int diff = 0, step = 0;
for(; step < n; ++step)
{
int index = (i + step) % n; // 求出⾛ step 步之后的下标
diff += gas[index] - cost[index];
if(diff < 0)
break;
}
if(diff >= 0) // 正常跳出
return i;
i += step; // i再++直接到step的后面->O(N)
}
return -1;
}
};
⑥力扣738. 单调递增的数字
难度 中等
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
提示:
0 <= n <= 10^9
class Solution {
public:
int monotoneIncreasingDigits(int n) {
}
};解析代码
下面是暴力的代码（会超时，因为找一个数的数位是logN的，总时间是O（N*logN））
class Solution {
public:
int monotoneIncreasingDigits(int n) {
for(int i = n; i >= 0; --i)
{
string str = to_string(i);
int j = 1, sz = str.size();
bool flag = true;
for(; j < sz; ++j)
{
if(str[j] < str[j - 1])
{
flag = false;
break;
}
}
if(flag)
return i;
}
return 9;
}
};贪心策略： 假设有一个数 n，它有 m 位数字，每一位数字分别是 d.1, d.2 , ..., dm 。
想要修改这个数字，使得修改后的结果既小于原数字 n ，又满足单调递增和最大化。为了实现这个目标，我们需要将不满足递增的高位数字尽可能地减小。
首先需要找到一个位置 k，使得d.1 ≤ d.2 ≤ ... ≤ d.k > d.k+1 ... （例如：12335412，k=4，d.k=5）。这个位置 k 表示从高到低，第一个不满足单调递增的数字的位置。我们需要将这个数字 减1，因为这是最小的减小量。
接下来需要将低位数字都修改为9，这样可以保证修改后的数字是最大的，并且还能保证单调递增。但是要处理找到第一个不满足单调递增的数字的位置，前面数字和此sh大小相等的情况（还是上面的k）：
需要继续修改这个数字。需要找到一个位置 t ，使得d.1 ≤ d.2 ≤ ... < d.t = d.t+1 = ... = d.k。这个位置 t 表示从高到低，最后一个高位数字相等的位置。我们需要将 d.t 减 1，并将之后的所有数字都修改为9，以满足d.1 ≤ d.2 ≤ ... ≤ d.t − 1 ≤ 9 ≤ ... ≤ 9，即高位数字的单调递增和低位数字的最大化。例如：1224444361，成功修改后的最大值为1223999999。
通过这种修改方式，可以得到一个新的数字，它既小于原数字 n，又满足单调递增和最大化。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string s = to_string(n);
int i = 0, m = s.size();
while(i + 1 < m && s[i] <= s[i + 1])
i++; // 找第⼀个递减的位置
if(i == m - 1) // 如果没有递减的
return n;
while(i - 1 >= 0 && s[i] == s[i - 1])
--i; // 回推
--s[i]; // 开始修改
for(int j = i + 1; j < m; ++j)
s[j] = '9';
return stoi(s);
}
};
⑦力扣991. 坏了的计算器
难度 中等
在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：
- 双倍（Double）：将显示屏上的数字乘 2；
- 递减（Decrement）：将显示屏上的数字减
1。
给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。
示例 1：
输入：startValue = 2, target = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.
示例 2：
输入：startValue = 5, target = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.
示例 3：
输入：startValue = 3, target = 10
输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.
提示：
1 <= startValue, target <= 10^9
class Solution {
public:
int brokenCalc(int startValue, int target) {
}
};解析代码
贪心策略：正难则反：当反着来思考的时候（让target 接近startValue，选择除2/加1操作）：
- 当 target > startValue的时候，对于奇数来说，只能执行加1操作（因为奇数除2就是小数了，这就是反过来思考的优势，这样做的动机是我们可以总是贪心地执行除2操作），对于偶数来说，最好的方式就是执行除2操作（因为加1后还要加1变为偶数）。
- 当 target <= startValue的时候，只能执行加1操作。
这样的话，每次的操作都是固定唯一的。
class Solution {
public:
int brokenCalc(int startValue, int target) {
int ret = 0;
while(target > startValue) // 进来先是target大
{
if(target % 2 == 1)
++target;
else
target /= 2;
++ret;
}
return ret + startValue - target;
}
};
本篇完。
下一篇是记忆化搜索类型的OJ。
下下篇是贪心算法的第四部分。
