本文主要是介绍Day32|贪心算法part02:122.买卖股票的最佳时机II、55. 跳跃游戏、45. 跳跃游戏II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
122. 买卖股票的最佳时机II
这题应该是dp的主菜,II的要求是可以无限次买无限次卖,可以用贪心做,想了下没想到思路,直接看题解。
贪心策略:
一直统计每次的差值,只要为负,不卖出,选择正才卖出。
- 局部最优:统计每天的利润,遇到正数收集起来;
- 全局最优:局部最优加起来。
class Solution {public int maxProfit(int[] prices) {int res = 0;for(int i = 0; i < prices.length; i++){if(i > 0 && prices[i] - prices[i - 1] > 0){res += prices[i] - prices[i - 1];}}return res;}}
(之后再用dp做试试)
55. 跳跃游戏
不一定非要明确一次究竟跳几步,每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。
局部最优:每次取最大跳跃步数(取最大覆盖范围),
整体最优:最后得到整体最大覆盖范围,看是否能到终点。
class Solution {public boolean canJump(int[] nums) {int maxJump = 0;for (int i = 0; i < nums.length; i++) {if(i > maxJump){return false;}maxJump = Math.max(maxJump, i + nums[i]);if(maxJump >= nums.length - 1){return true;}}return false;}
}
45. 跳跃游戏II
本题比上题难些,主要是判断跳跃的时机。
class Solution {public int jump(int[] nums) {int n = nums.length;int end = 0, farthest = 0;int jumps = 0;for (int i = 0; i < n - 1; i++) {farthest = Math.max(nums[i] + i, farthest);if (end == i) {jumps++;end = farthest;}}return jumps;}
}
- 当end == i,就是跳到当前格的时候,需要跳一步。
总结
我发现贪心很多时候是用来解决“差值”的问题,而且题目并不会要求输出具体路径,而往往是求和或者判断是否符合条件。
贪心没有套路,贪心能做的DP一定也能做,反之不一定成立。
差值问题注意起始和终止两个点的处理。
使用贪心算法的实际应用还挺多,比如赫夫曼编码也是一个经典的贪心算法应用。更多时候运用贪心算法可能不是求最优解,而是求次优解以节约时间,比如经典的旅行商问题。
这篇关于Day32|贪心算法part02:122.买卖股票的最佳时机II、55. 跳跃游戏、45. 跳跃游戏II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!