算法训练营（day32）

贪心算法理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

举个例子，在规定次数内从一堆钞票里怎么拿面额最大的钞票，根据贪心算法的思想：每次拿最大的就好（够贪就行O(∩_∩)O）

贪心算法一般分为如下四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

总而言之，贪心算法的本质其实就是 找到局部最优解，再比较所有的局部最优，得到全局最优。

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

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

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

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

解题思路

解题过程：

思路一：贪心算法

  1. 局部最优：收集每天的正利润
  2. 全局最优：累加正利润及最大利润

思路二：动态规划

  1. 定义 0 为没有持有股票， 1 为持有股票

  2. dp[i][0] 取两种情况的最大值

    • 没有持有股票的现金
    • 把股票卖了，减去买股票的支出后所赚的钱

  3. dp[i][1]也取两种情况的最大值

    • 持有股票，剩下的钱
    • 当天买股票，剩下的钱

详细代码

解法一：贪心

1
2
3
4
5
6
7
8
9
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for(int i = 1; i < prices.length; i++){
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

解法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for(int i = 1; i < prices.length; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/

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

判断你是否能够到达最后一个下标。

解题思路

解题过程：

思路一：贪心

  1. 局部最优：当前下标指定的值 能跳到的 最远下标
  2. 全局最优：如果 最远下标 不小于 nums.length - 1，则说明可以到达最后一个下标

思路二：动态规划

  1. 同上

详细代码

思路一：贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int jump = 0;
        for(int i = 0; i <= jump; i++){
            jump = Math.max(jump, i + nums[i]);
            if(jump >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}

思路二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;

        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && nums[j] >= i - j){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[nums.length - 1];
    }
}

45. 跳跃游戏 II

题目链接：https://leetcode.cn/problems/jump-game-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]。

解题思路

解题过程：

思路一：贪心

  1. 定义一个 end 表示当前覆盖的最远距离下标，end 最多到 倒数第二个数组
  2. 如果 i 走到 end，则更新到 下一步的最远距离下标 tmp
  3. 如果 end 走到了 nums.length - 2，则说明 再跳一次必能到达 nums[i - 1]，直接增加一次跳跃次数即可

思路二：贪心

  1. 最普遍的贪心写法
  2. 定义 当前能到达的最远距离 和 下一步能到达的最远距离
  3. 每当 i 走到 当前能到达的最远距离，就更新 下一步能到达的最远距离
  4. 直到 下一步能到达的最远距离 涵盖了 nums.length - 1 ，说明再跳一次即可到达，结束循环

详细代码

解法一：贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int jump(int[] nums) {
        int jumpCount = 0;
        int end = 0;	//当前覆盖的最远距离下标
        int tmp = 0;	//下一步覆盖的最远距离下标

        for(int i = 0; i <= end && end < nums.length - 1; ++i){
            tmp = Math.max(tmp, i + nums[i]);	//更新下一步的最远距离下标
            if(i == end){		// 遇到当前覆盖的最远距离下标
                end = tmp;		// 更新当前覆盖的最远距离下标
                jumpCount++;
            }
        }
        return jumpCount;
    }
}

解法二：贪心

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
class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length <= 1){
            return 0;
        }
        int resultCount = 0;
        int curDistance = 0;
        int maxDistance = 0;

        for(int i = 0; i < nums.length; i++){
            maxDistance = Math.max(maxDistance, i + nums[i]);

            if(maxDistance >= nums.length - 1){
                resultCount++;
                break;
            }

            if(i == curDistance){
                curDistance = maxDistance;
                resultCount++;
            }
        }
        return resultCount;
    }
}