代码随想录35期Day32-Java

Day32题目

LeetCode122.买股票的最佳时机

核心思想：很简单，只要第二天比第一天贵，就第一天买入，第二天卖出

class Solution {public int maxProfit(int[] prices) {// 只要后一天比这一天价钱高就买，然后第二天卖出int res = 0;for(int i = 1 ; i < prices.length ; i ++ ){if(prices[i] > prices[i-1]){res += prices[i]-prices[i-1];}}return res;}
}

LeetCode55.跳跃游戏

核心思想：只要看最远的跳远距离能到最后一位就可以了

class Solution {public boolean canJump(int[] nums) {// 看跳的最远能覆盖最后一位就行// count是目前能跳的最远距离int count = 0 ;if(nums.length == 1) return true;for(int i = 0 ; i <= count;  i ++){// 更新count为最远跳远距离count = Math.max(count,nums[i]+i);if(count >= nums.length-1) return true;}return false;}
}

LeetCode45跳远游戏Ⅱ：需要计算跳远的最小次数

核心思想：我使用了从后向前的遍历，比较好想但是遍历次数多些。也可以维护一个当前最大距离和最大距离，计算几步最大距离能覆盖到最后一个元素

class Solution {public int jump(int[] nums) {if (nums.length == 1)return 0;int maxCover = 0;int curCover = 0;int count = 0;for (int i = 0; i <= maxCover; i++) {// 更新最大覆盖距离maxCover = Math.max(maxCover, i + nums[i]);// 符合要求的结果if (maxCover >= nums.length - 1) {count++;return count;}// curCover是当时 第一个元素能到达的最远距离// 如果到达了第一个元素能到达的最远距离，那么就该走下一步了if (i == curCover) {count++;// 更新第二步能到达的最大距离 为 第一步覆盖到的元素中最远的一个。curCover = maxCover;}}return count;}
}

// 这是我从后向前遍历的代码
class Solution {public int jump(int[] nums) {if(nums.length == 1) return 0;// 从后向前找最大能到这里的位置// target 记录接下来一步要到达什么地方int target = nums.length- 1;int count = 0 ;while(target !=0 ){int temp = target;for(int i = temp ; i >= 0 ; i --){// 从后向前遍历保证得到的下一步是离得最远的那个。if(nums[i] + i >= temp){if(target> i){target = i;}}}count++;}return count;}
}