122.买卖股票的最佳时机II
题目链接：122.买卖股票的最佳时机II
文档讲解：代码随想录
状态：没悟到思路，不会
思路
贪心思想：每天都买，能赚则留，不能赚则抛
当时疑惑的点：例如股票价格：[1,2,3,4]如果是一直上升的趋势，每天买第二天卖与第一天买最后一天卖是同样的结果。即能卖就卖，不用等待。
题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i = 1;i<prices.size();i++)
{
if(prices[i]-prices[i-1]>0)res +=prices[i]-prices[i-1];
}
return res;
}
};
55.跳跃游戏
思路
思考过程：因为每个数字可以代表1-n的步长，每个都遍历极其复杂，所以用覆盖范围表达，有一个最远距离，近处的都可以找到。将问题从离散->可度量（重要思想）；与此同时，每个点都包含着重要信息，在到达终点前遍历各个点必不可少。
覆盖范围如下图所示：
我们不一定可以跳到最后，注意for循环是在cover范围内而非nums的范围内。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。（人尽皆知）
题解
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
for(int i = 0;i<=cover;i++)
{
cover = max(cover,nums[i]+i);
if(cover >= nums.size()-1)return true;
}
return false;
}
};
45.跳跃游戏II
思路
本题一定有解，问题转化为如何最快速的以正确路径到终点。
贪心点：要以最小的步长到达终点，每一步都要尽可能大，算法流程如下：
- 到达一个下标点，获得元素值，知道可到达的范围
- 遍历范围内所有元素！！！这个很重要，获得每个信息
- 在到达范围边界时再取一个最大的步长前进
注意其中离散->范围->离散的转化思考过程
题解
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() == 1)return 0;
int cover = nums[0];
int count = 1;
int max = INT_MIN;
for(int i = 0;i<nums.size();i++)
{
if(cover>=nums.size()-1)break;
if(i>cover)
{
count++;
cover = max;
}
if(i+nums[i]>max)max = i+nums[i];
}
return count;
}
};
1005.K次取反后最大化的数组和
题目链接：1005.K次取反后最大化的数组和
文档讲解：代码随想录
状态：很简单AC
思路
很简单的模拟题，思考过程和贪心算法吻合。
算法流程如下：
首先将数组排序，如果最小的是负数转正（贪心思想-最大增长），若k仍有剩余，然后除二取余，将最小的数变负(贪心思想-最小损失)。
题解
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int sum = 0;
sort(nums.begin(),nums.end());
for(int i = 0;i<nums.size();i++)
{
if(nums[i]<0 && k>0)
{
nums[i] = -nums[i];
k--;
}
sum += nums[i];
}
if(k!=0)k = k%2;
if(k == 0)return sum;
else return sum-2*(*min_element(nums.begin(),nums.end()));
}
};
小小疲惫，还是要静下心来思考