代码随想录算法训练营第三十二天|LeetCode122,55,45

代码随想录算法训练营第三十二天|LeetCode122,55,45

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

本题的思路感觉与前一天的摆动序列类似。前天是最大自序和，今天是差的和最大

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！

其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

 public int maxProfit(int[] prices) {

        int profit = 0;
        for (int i = 1; i < prices.length; i++){
            int dif = prices[i] - prices[i -1];
            if (dif >= 0){
                profit += dif;
            }
        }
        return profit;
    }
1
2
3
4
5
6
7
8
9
10
11

55.跳跃游戏

刚看到本题一开始可能想：当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？（确实陷进这个）

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例，试试贪心！

i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。

而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。

如果cover大于等于了终点下标，直接return true就可以了。

这个题还有一点就是for循环里的判断条件是变的。

    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;
    }
1
2
3
4
5
6
7
8
9
10

45.跳跃游戏II（*）

相比于上一道题，这个题的在考察最大范围的基础上需要考 以最小跳跃次数来扩大最大范围。

解题思路：

以最小的步数增加覆盖范围

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

 public int jump(int[] nums) {
        //处理特殊情况
        if (nums == null || nums.length == 1) {
            return 0;
        }
        //记录跳跃次数
        int count = 0;
        //记录当前覆盖的最大区域
        int curDistance = 0;
        //记录下一次最大的覆盖区域
        int nextDistance = 0;
        //这里的循环条件与上一题也不一样。
        for (int i = 0; i< nums.length;i++){
            nextDistance = Math.max(nums[i] + i, nextDistance); //更新下一步的最远覆盖距离
            if (i == curDistance){//如果已经到了当前最远覆盖距离
                if (curDistance<nums.length -1){//仍然不是终点
                    count++;//走下一步
                    curDistance = nextDistance;//更新当前范围
                    if(nextDistance > nums.length-1){
                        //如果更新范围后覆盖了终点
                        break;
                    }

                }

            }
        }
        return count;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30