day32贪心算法 part02

贪心系列的时候，题目和题目之间貌似没有什么联系,是真的就是没什么联系，因为贪心无套路,没有个整体的贪心框架解决一系列问题，只能是接触各种类型的题目锻炼自己的贪心思维。贪心只是一类题的统称，并没有什么固定套路。

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

难点：这个题别用现实生活中买股票的经验去想，现实生活中哪有知道明天和后几天的股票价格的

其实是阅读理解题，描述问题很抽象，其实就是若相邻两数是升高，则累加其升高的值

class Solution {public int maxProfit(int[] prices) {// 先买才能卖，所以是向后比较，有的赚就买入，这就是贪心// 别的讲一堆都是干扰项// 这个题别用现实生活中买股票的经验去想，现实生活中哪有知道明天和后几天的股票价格的int pofit = 0;for (int i = 0; i < prices.length - 1; i++) {if (prices[i + 1] > prices[i]) { // 如果在第一天看到第二天股票要涨，赶紧买入，第二天卖出pofit += prices[i + 1] - prices[i];}}return pofit;}
}

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

难点：这题还行，不算难，

class Solution {public boolean canJump(int[] nums) {if (nums.length == 1) return true;int cover = nums[0];for (int i = 0; i <= cover; i++) {cover = Math.max(cover, i + nums[i]);if (cover >= nums.length - 1) return true; // 注意这里是nums.length - 1,数组取不到length}return false;}
}

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

难点：一定要跟着代码结合上面的这个图走一遍，就啥都懂了

class Solution {public int jump(int[] nums) {if (nums == null || nums.length == 1 || nums.length == 0) return 0;int curDistance = 0; // 一开始站在0这个位置上，所以当前覆盖距离就是0int maxDistance = 0; // 这个变量是用来记录当前这一步里最远能跳多远int count = 0;for (int i = 0; i < nums.length; i++) { // 遍历这些元素就是在找这一步里最远能走多远// 每遍历一个nums的元素，就要是否需要更新一次最远覆盖距离maxDistance = Math.max(maxDistance, i + nums[i]);if (maxDistance >= nums.length - 1) { // 说明再跳一步就能达到最远距离count++;return count;}//走到当前覆盖的最大区域时，更新下一步可达的最大区域// 这里是最难理解的,这里相当于走一步的过程，因为虽然当前最大覆盖距离在变// ，但是你那一步是没有走出去的if (i == curDistance) { // 这一步走到头了，该走下一步了curDistance = maxDistance; // 往最远的地方走count++;}}return count;}
}