【随想录】Day32—第八章 贪心算法 part02

本文主要是介绍【随想录】Day32—第八章 贪心算法 part02，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 买卖股票的最佳时机 II

• 题目链接：122. 买卖股票的最佳时机 II

---

1- 思路

贪心：

• 求数组中相邻两个元素的差值，例如数组 [ 1, 5 , 3 ]
• 如果是第一天买如，第三天卖出，相当于 p[2] - p[0] = p[2] - p[1] + p[1] - p[0]
• 贪心思路：实际上就是求相邻两个元素的差值和，若差值大于 0 则收集结果，为利润，本题贪心即 求 所有正数差值和

---

2- 题解

⭐买卖股票的最佳时机 II ——题解思路

class Solution {public int maxProfit(int[] prices) {int[] sub = new int[prices.length-1];int index = 0;int res = 0;for(int i = 1 ; i < prices.length;i++){sub[index++] = prices[i] - prices[i-1];}for(int i = 0 ; i < sub.length;i++){if(sub[i]>0){res+=sub[i];}}return res;}
}

---

题目2: 55. 跳跃游戏

• 题目链接：55. 跳跃游戏

---

1- 思路

贪心

• 定义一个 int cover变量，代表数组的覆盖范围
• 通过覆盖范围来遍历数组，每次更新 cover = cover + nums[i]，同时覆盖范围取 范围内最大值
• 贪心思路：遍历 cover 范围内的数组，每次根据 当前数组的 nums 值，取当前范围最大的可到达数 为当前 cover 值
  • 如果 cover 超出 数组长度 直接返回 true
  • 否则返回 false

---

2- 题解

⭐跳跃游戏 ——题解思路

class Solution {public boolean canJump(int[] nums) {int cover = 0;for(int i = 0 ; i<=cover ;i++){cover = Math.max(i+nums[i],cover);if(cover >= nums.length-1){return true;}}return false;}
}

---

题目3: 45. 跳跃游戏 II

• 题目链接：45. 跳跃游戏 II

---

1- 思路

• 区分于 跳跃游戏的区别在于，并非每次是跳的最大次数就最少

贪心

• **贪心思路：**以最少的步数，尽可能多的增加覆盖范围 cover ，区别于跳跃游戏基础版的点在于，再定义一个 nextCover，记录每次遍历到的最大范围，但每次不一定更新 cover
  • 只有在当前 cover 走不下去时候，再更新 cover，对结果进行 ++

---

2- 题解

⭐跳跃游戏 II ——题解思路

class Solution {public int jump(int[] nums) {int cover = 0;int nextCover = 0;int res = 0;for(int i = 0 ; i < nums.length;i++){nextCover = Math.max(nums[i]+i,nextCover);if(i==cover){if(cover!=nums.length-1){res++;cover = nextCover;}}}return res;}
}

---

这篇关于【随想录】Day32—第八章 贪心算法 part02的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---