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;
    }
}