【随想录】Day32—第八章 贪心算法 part02

---

题目1: 买卖股票的最佳时机 II

• 题目链接：122. 买卖股票的最佳时机 II

---

1- 思路

贪心：

• 求数组中相邻两个元素的差值，例如数组 [ 1, 5 , 3 ]
• 如果是第一天买如，第三天卖出，相当于 p[2] - p[0] = p[2] - p[1] + p[1] - p[0]
• 贪心思路：实际上就是求相邻两个元素的差值和，若差值大于 0 则收集结果，为利润，本题贪心即 求 所有正数差值和

---

2- 题解

⭐买卖股票的最佳时机 II ——题解思路

class Solution {
    public int maxProfit(int[] prices) {
        int[] sub = new int[prices.length-1];
        int index = 0;
        int res = 0;
        for(int i = 1 ; i < prices.length;i++){
            sub[index++] = prices[i] - prices[i-1];
        }
        for(int i = 0 ; i < sub.length;i++){
            if(sub[i]>0){
                res+=sub[i];
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

题目2: 55. 跳跃游戏

• 题目链接：55. 跳跃游戏

---

1- 思路

贪心

• 定义一个 int cover变量，代表数组的覆盖范围
• 通过覆盖范围来遍历数组，每次更新 cover = cover + nums[i]，同时覆盖范围取 范围内最大值
• 贪心思路：遍历 cover 范围内的数组，每次根据 当前数组的 nums 值，取当前范围最大的可到达数 为当前 cover 值
  • 如果 cover 超出 数组长度 直接返回 true
  • 否则返回 false

---

2- 题解

⭐跳跃游戏 ——题解思路

class Solution {
    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
11
12
13

---

题目3: 45. 跳跃游戏 II

• 题目链接：45. 跳跃游戏 II

---

1- 思路

• 区分于 跳跃游戏的区别在于，并非每次是跳的最大次数就最少

贪心

• **贪心思路：**以最少的步数，尽可能多的增加覆盖范围 cover ，区别于跳跃游戏基础版的点在于，再定义一个 nextCover，记录每次遍历到的最大范围，但每次不一定更新 cover
  • 只有在当前 cover 走不下去时候，再更新 cover，对结果进行 ++

---

2- 题解

⭐跳跃游戏 II ——题解思路

class Solution {
    public int jump(int[] nums) {
        int cover = 0;
        int nextCover = 0;
        int res = 0;
        for(int i = 0 ; i < nums.length;i++){
            nextCover = Math.max(nums[i]+i,nextCover);
            if(i==cover){
                if(cover!=nums.length-1){
                    res++;
                    cover = nextCover;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---