1. 分发饼干
这道题目和我们之前讲到的田忌赛马的问题很相似，只不过这这里不需要劣等马去抵消掉优等马，直接上贪心策略：
先将两个数组排序。针对胃口较小的孩子，从小到大挑选饼干:
- i. 如果当前饼干能满足，直接喂(最小的饼干都能满足，不要浪费大饼干) ;
- ii. 如果当前饼干不能满足，放弃这个饼干，去检测下一个饼干(这个饼干连最小胃口的孩子都无法满足，更别提那些胃口大的孩子了)。
直接上代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0;
int j = 0;
int ret = 0;
while(j < s.size() && i < g.size())
{
if(s[j] >= g[i])
ret++,j++,i++;
else
j++;
}
return ret;
}
};2. 最优除法
我们可以看到这个题目的要求，它要求表达式的结果最大，那么在除数中我们可以尽量让分子大一点，让分母小一点即可，这就是我们的贪心策略：在最终的结果中，前两个数的位置是无法改变的，前两个数必定一个在分子，一个在分母，题目中说明每⼀个数的都是大于等于 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 = to_string(nums[0]) + "/(" + to_string(nums[1]);
for(int i = 2; i < n; i++)
{
ret += "/" + to_string(nums[i]);
}
ret += ")";
return ret;
}
};3. 跳跃游戏Ⅱ
动态规划解法:
- a.状态表示：dp[i] 表示从0位置开始，到达i位置时候的最小跳跃次数
- b.状态转移方程：对于dp[i],我们遍历0~i-1区间(用指针j表示)，只要能够从j位置跳到i位置(nums[j]+j>=i) ，我们就用 dp[j]+ 1更新dp[i]里面的值，找到所有情况下的最小值即可。
类似层序遍历的过程:
- 用类似层序遍历的过程，将第i次跳跃的「起始位置」和「结束位置」找出来，用这次跳跃的情况，更新出下一次跳跃的「起始位置」和「终止位置」这样「循环往复」，就能更新出到达n一1位置的最小跳跃步数
直接上代码：
class Solution {
public:
int jump(vector<int>& nums) {
int left = 0;
int right = 0;
int ret = 0;
int maxpos = 0;
while(true)
{
// 判断是否已经跳到最后一个位置
if(nums.size() - 1 <= maxpos)
return ret;
// 遍历当层节点的最大步数
for(int i = left; i <= right; i++)
{
maxpos = max(maxpos, nums[i] + i);
}
// 更新下一层的区间
left = right + 1;
right = maxpos;
ret++;
}
}
};4. 跳跃游戏
这个题目和上面的题目思路基本上差不多，但是上一个题目的明显说了一定会到达最后一个下标位置，而我们这道题目是判断能否到达最后一个下标位置，基于上一个题目我们仅需修改⼀下返回值即可，直接上代码啦！！！
class Solution {
public:
bool canJump(vector<int>& nums) {
int left = 0;
int right = 0;
int maxpos = 0;
int n = nums.size();
while(left <= right)// 以防跳不到 n - 1 的位置
{
// 判断是否已经能跳到最后⼀个位置
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;
}
};5. 加油站
暴力解法：
- a. 依次枚举所有的起点；
- b. 从起点开始，模拟⼀遍加油的流程
- c. 如果油的剩余量小于0，代表无论怎样，你都不可能绕环路行驶一周，否则可以。
class Solution
{
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
int n = gas.size();
for (int i = 0; i < n; i++) // 依次枚举所有的起点
{
int rest = 0; // 标记⼀下净收益
for (int step = 0; step < n; step++) // 枚举向后⾛的步数
{
int index = (i + step) % n; // 求出⾛step步之后的下标
rest = rest + gas[index] - cost[index];
if (rest < 0) break;
}
if (rest >= 0) return i;
}
return -1;
}
};但是此时会超出时间限制，复杂度太高，我们可以优化一下哈，我们发现，当从 i 位置出发，走了 step 步之后，如果失败了。那么 [i, i + step] 这个区间内任意⼀个位置作为起点，都不可能环绕⼀圈。
因此我们枚举的下⼀个起点，应该是 i + step + 1。
class Solution
{
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
int n = gas.size();
for (int i = 0; i < n; i++) // 依次枚举所有的起点
{
int rest = 0; // 标记⼀下净收益
int step = 0;
for (; step < n; step++) // 枚举向后⾛的步数
{
int index = (i + step) % n; // 求出⾛step步之后的下标
rest = rest + gas[index] - cost[index];
if (rest < 0) break;
}
if (rest >= 0) return i;
i = i + step; // 优化
}
return -1;
}
};
