贪心算法理论基础
局部最优推出全局最优
根据示例可知就是尽量满足每个孩子
局部最优就是大饼干给胃口大的，全局最优就是尽量满足多的孩子。
先将饼干和小孩数组排序，然后从后往前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
class Solution {
public:
int findContentChildren(vector& g, vector& 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 && s[index] >= g[i]) result++, index--;
}
return result;
}
};
也可以先用小饼干先喂饱小胃口
class Solution {
public:
int findContentChildren(vector& g, vector& 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;
}
};
题目2：376.摆动序列
其实也可以理解成：删除单调坡度上中间的节点
由于题目要求返回的是子序列的长度，那么只需要统计波峰波谷数量，要注意的是序列两端的数也是波峰或波谷
class Solution {
public:
int wiggleMaxLength(vector& nums) {
if (nums.size() <= 1) return nums.size();
int curdiff = 0; //当前一对差值
int prediff = 0; //前一对差值
int result = 1; //初始为1，默认序列最后有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curdiff = nums[i + 1] - nums[i];
if ((curdiff > 0 && prediff <= 0) || (prediff >= 0 && curdiff < 0)) result++, prediff = curdiff; //更新峰值
}
return result;
}
};
还有动规的解法
题目3：53.最大子序和
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
遍历nums，从头开始用count累积；
如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和；
如果count加上nums[i]为正数，则继续累加，并将count的值保存下来。
class Solution {
public:
int maxSubArray(vector& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) result = count; //取区间累计的最大值
if (count <= 0) count = 0; //重置最大子序起始位置，因为遇到负数一定是拉低总和
}
return result;
}
};
知足常乐，我不贪心，所以选择暴力解法：
类似于双指针法
class Solution {
public:
int maxSubArray(vector& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) { // 设置起始位置
count = 0;
for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
count += nums[j];
result = count > result ? count : result;
}
}
return result;
}
};
题目4：122.买卖股票的最佳时机Ⅱ
利润最大化就要在低的时候买入、高的时候卖出
在示例2中第一天买入，第五天卖出，利润为prices[4]-prices[0]，可以分解为(prices[4]-prices[3])+(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])
class Solution {
public:
int maxProfit(vector& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) { //i从1开始，因为到第二天才会有利润
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
题目5：55.跳跃游戏
这一题得关键在于：不要纠结每次跳几步，而是看最后能不能覆盖到终点。
什么意思呢，比如[1,2,3,4,5,6,7,8,9,10]，如果最远能到达的10，那么就一定可以到达8。
那么就可以根据最远可以到达的位置，判断是否能跳跃到最后一个下标。如果最远可以到达的位置大于等于数组中最后一个位置，就说明可以到达最后一个下标。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
class Solution {
public:
bool canJump(vector nums) {
int most = 0;
if (nums.size() == 1) return true;
for (int i = 0; i < nums.size(); i++) {
if (i <= most) {
most = max(i + nums[i], most); //i+nums[i] 要加上本身处于的位置
if (most >= nums.size() - 1) return true;
}
}
return false;
}
};
题目6：45.跳跃游戏Ⅱ
和上一题相比，变成了跳跃到最后一个位置最少要多少步
如果从前往后遍历数组，每次找到可以到达的最远位置，直到到达终点。
其实就是 每次在能跳到的范围内，选一个跳的最远的位置，这样跳到终点的步数一定最少。
更新当前位置所能到达的最远位置记为end，边走边更新最远位置curfar，当到达end时记为一步，并更新curfar
class Solution {
public:
int jump(vector& nums) {
int curfar = 0; //当前能跳到的最远位置
int end = 0; //上次能跳到的最远位置
int result = 0;
for (int i = 0; i < nums.size() - 1; i++) {
curfar = max(curfar, i + nums[i]); //找目前能跳的最远的位置
if (i == end) { //到达上次跳跃能到达的最远位置，更新并且步数加一
end = curfar;
result++;
}
}
return result;
}
};
官方题解给出的代码解释感觉跟代码并不好对应，其实就是遍历数组，找最远位置，到最远位置了步数就加一
