代码随想录 Day-21（贪心算法）

目录力扣题目 122.买卖股票的最佳时机 Ⅱ思路解法力扣题目 55.跳跃游戏错误的解法正确的解法力扣题目 45.跳跃游戏 Ⅱ力扣题目 122.买卖股票的最佳时机 Ⅱ思路贪心算法局部最优然后全局最优怎么局部最优题意无非就是低的买入高的卖出。而且有了 “53.最大的子序和” 经验可以想象成两天之间只要两天的一个差值是大于0那么就有的赚而且其实自己思考一下可以发现虽然题目中要求最多只可以持股一个但是实际实现不用去管这个条件无论怎么样都可以实现。那么解法就是计算每天的一个利润值将大于0的利润全部加起来其实就是题目的答案。解法public int maxProfit(int[] prices) { int sum 0; int diff 0; for (int i 1; i prices.length; i) { diff prices[i] - prices[i-1]; // 直接和0比较那么不用使用if判断条件也可以直接相加 sum Math.max(diff, 0); } return sum; } /** class Solution { public int maxProfit(int[] prices) { int length prices.length; int sum 0; for(int i1; ilength; i){ int temp prices[i] - prices[i-1]; sum Math.max(temp,0); } return sum; } } */力扣题目 55.跳跃游戏错误的解法应该要考虑特殊的情况例如nums{0}或者 nums{12}或者 nums{01}等特殊情况由第一个元素为0的时候可以得出结论应该在覆盖的范围里面更新覆盖范围这样当nums{023}结果才会对class Solution { public boolean canJump(int[] nums) { //这里记录下标就是用来判断覆盖的长度 int index nums.length - 1; int cover nums[0]; if(nums.length 1) return true; //这里不需要等号因为i到达最后一个位置的时候也不能跳 for(int i1; iindex; i){ cover Math.max(inums[i], cover); if(cover index) return true; } return false; } }正确的解法class Solution { public boolean canJump(int[] nums) { //这里记录下标就是用来判断覆盖的长度 int index nums.length - 1; int cover 0; if(nums.length 1) return true; //这里不需要等号因为i到达最后一个位置的时候也不能跳 for(int i0; icover; i){ cover Math.max(inums[i], cover); if(cover index) return true; } return false; } }力扣题目 45.跳跃游戏 Ⅱclass Solution { public int jump(int[] nums) { if (nums null || nums.length 0 || nums.length 1) { return 0; } //记录跳跃的次数 int count0; //当前的覆盖最大区域 int curDistance 0; //最大的覆盖区域 int maxDistance 0; //因为题意已经表明肯定可以走到终点所以是可以直接用数组的大小来确定i的范围 //上一题并不是可以都可以走到终点所以不可以这样写 for (int i 0; i nums.length; i) { //在可覆盖区域内更新最大的覆盖区域 maxDistance Math.max(maxDistance,inums[i]); //说明当前一步再跳一步就到达了末尾 if (maxDistancenums.length-1){ count; break; } //走到当前覆盖的最大区域时更新下一步可达的最大区域 if (icurDistance){ curDistance maxDistance; count; } } return count; } }