122.买卖股票的最佳时机II
思路:
用profit记录每一轮的利益,tempPrice记录手中的价格(假装买入第一天),result记录获得的收益
如果当前价格-手中持有价格小于上一轮profit(新一轮贡献为负数),则按上一轮价格卖出,result+=profit, 买入新的股票,profit=0;如果大于等于上一轮profit则继续持有,现在的profit = profit[i]-tempPrice;
最后如果profit不等于0,说明最后一天还在持有,要在最后进行卖出,result+=profit;
返回result;
看视频后:
这题的贪心贪在把收益分割成每天的收益,只收获收益为正的收益。
Day[0-3]=Day[3]-Day[2]+Day[2]-Day[1]+Day[1]-Day[0]
int result=0;
for(int i=1;i<prices.size();i++)
result+=max(0,prices[i]-prices[i-1]);
return result;
55. 跳跃游戏
思路:
nums.size()==1可直接返回;
用temp决定跳跃幅度,每次都跳最大,如果能跳到终点就可以返回true,否则false。但过不了部分案例。
看视频后:
cover决定覆盖范围,cover的更新应当为cover=max(temp,i+nums[i]) ,如果覆盖范围大于等于最后一个下标,返回true. 如果遍历到最后都没有覆盖到最后一个下标,返回false.
不用max则可能缩小了覆盖范围,如新的节点的覆盖范围变小的时候。
45.跳跃游戏II
思路:
思路错误。
看视频后:
关键在于以最小的步数增加最大的覆盖范围,直到覆盖范围覆盖了终点。
本题需要统计两个覆盖范围,当前一步的覆盖范围和下一步的覆盖范围。移动下标达到了当前覆盖的最远距离下标时,步数就要加一,来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑,当移动下标达到了当前覆盖的最远距离下标时
如果当前覆盖最远距离下标不是是集合终点,步数就加一,还需要继续走。
如果当前覆盖最远距离下标就是是集合终点,步数不用加一,因为不能再往后走了。
每一轮 nextDistance = max(nums[i]+i,nextDistance)
如果 i 已经碰到这一轮的终点(curDistance)了, count++,把下一轮距离赋给这一轮距离,如果下一轮距离已经抵达终点,则直接break; 最终return count;