目录
看到题目的第一想法
观察题目，想一下怎么从局部推出整体
若递减则continue，若递增则把差值相加，得到的就是结果
看到代码随想录之后的想法
代码随想录：局部，每天的股票利润
全局：把每天的股票利润加起来的就是总体的股票利润
自己实现过程中遇到的困难
卡哥的思路更简洁一点，可以借鉴，负数用0来代替，进行收集
没有困难，贪心就是这样，没有规律。。靠常识，找到了就很简单
class Solution {
//我的做法，如果为递减则往下走，如果为递增则加上差值
//把局部的差值都加上就是全局的最优了 画图观察，想贪心的思路
/*public int maxProfit(int[] prices) {
//prices
//如果是递增，则继续往下走，直到要递减时卖出
int sum = 0;
for(int i=0;i<prices.length-1;i++){
if(prices[i+1]<prices[i]){
continue;
}
sum+=(prices[i+1] - prices[i]);
}
return sum;
}*/
//卡哥做法 获取每天的正利润，然后把正利润加起来获得全局的正利润
public int maxProfit(int[] prices) {
//prices
//如果是递增，则继续往下走，直到要递减时卖出
int sum = 0;
for(int i=0;i<prices.length-1;i++){
//如果为负数则为0
sum+=Math.max(prices[i+1] - prices[i],0);
}
return sum;
}
}55. 跳跃游戏
本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解
看到题目的第一想法
没有思路，没有想到
看到代码随想录之后的想法
从覆盖范围的角度来思考
每个元素的覆盖范围，看是否能到达最后
自己实现过程中遇到的困难
1 我的写法是遍历整个数组，如何从当前范围来得到下一个范围，会很矛盾，无法去把控每一个元素的覆盖
2 卡哥做法是，遍历当前范围，然后通过当前范围的遍历，不断扩大当前的范围，若当前范围能覆盖全部则return true，如果当前范围遍历完了还是没有覆盖全部，则return false
class Solution {
public boolean canJump(int[] nums) {
//局部 看每个节点的覆盖范围的角度来思考
//我的做法错误的地方，一开始想着遍历整个数组，无法把控每个元素的覆盖返回
/*for(int i=0;i<nums.length;i++){
if(nums[i]+i>=nums.length-1){
return true;
}
if(nums[i]==0){
return false;
}
}
return false;*/
//通过局部的覆盖范围，来推出是否能覆盖全局
//循环应该从范围入手
if(nums.length==1){
return true;
}
int cover = nums[0];
for(int i=0;i<=cover;i++){
//每次重新赋值最大的覆盖范围,取当前cover 和nums[i]+i的最大值
cover = Math.max(cover,nums[i]+i);
//范围应该为nums.length-1局部最优推出全局最优，找不出反例，试试贪心！
if(cover>=nums.length-1){
return true;
}
}
return false;
}
}看到题目的第一想法
从覆盖范围的角度来思考
每个元素的覆盖范围，看到最后能走多少步
但是最小步数不知道要怎么想出来
看到代码随想录之后的想法
也是通过覆盖范围的角度来思考
贪心 每次局部走最远的距离，到达终点的次数最小
用next记录下一次跳跃最远的距离，用cur记录本次要走的距离
但是会把当前覆盖范围给走完，用一个next来记录当前覆盖范围中的子元素的最大覆盖范围，如果当前覆盖范围走完了，则让当前覆盖范围等于next(相当于一次跳跃)，继续走
若当前覆盖范围>=nums.length-1 就统计了最小次数
自己实现过程中遇到的困难
1 我的写法是for遍历当前覆盖范围，其实是没必要多此一举的直接遍历整个数组即可
会不太好记录count cur和cover 一样
2 记录count 时，先让cur为0，每次进入循环记录next，若当前下标走到cur了，则开始跳跃，让cur=next，count++，若cur>=nums.length-1 返回count
class Solution {
/*public int jump(int[] nums) {
if(nums.length==1){
return 0;
}
int count = 1;
//覆盖范围 每次调整一次覆盖范围 则+1
//需要取覆盖范围里最大的一个，跳的最远
int cover = nums[0];
for(int i = 0;i<cover;i++){
if(cover>=nums.length){
return count;
}
if(cover<nums[i]+i){
count++;
cover = nums[i]+i;
}
}
return count;
}*/
public int jump(int[] nums) {
if(nums.length==1){
return 0;
}
int count = 0;
//覆盖范围 每次调整一次覆盖范围 则+1
//每次取局部最远的，看是否跳到终点
//需要取覆盖范围里最大的一个，跳的最远
//如何取最远的的一个，使用next值，当当前的cover走到头时，若没有到达终点
//则取next 继续走，同时获取最大的
//当前能走的最远距离 为cur
int cur = 0;
int next = 0;
for(int i = 0;i<nums.length;i++){
next = Math.max(nums[i]+i,next);
if(i==cur){
//如果当前没到终点，则取next，继续往下走
if(i<nums.length){
cur=next;
count++;
if(cur>=nums.length-1)
{
return count;
}
}
}
}
return count;
}
}
