java LeetCode刷题稍有难度的贪心构造算法

Java LeetCode刷题稍有难度的贪心构造算法攻略

在LeetCode刷题过程中，贪心算法在构造类问题中经常发挥着非常强大的作用。本篇文章将介绍贪心构造算法的基本思想和常见的实现模式，并给出两个例题作为说明。

概述

贪心构造算法指的是在求解最优解的过程中，每一步都采取当前状态下最优的选择。该算法通常适用于满足贪心选择性质的问题中，即问题能够分解成若干个子问题且每个子问题都能够用贪心策略来解决，从而达到最终最优解。

基本思想

贪心构造算法的基本思想是通过贪心策略和数学归纳的思想构造解，具体分为两步：

1. 选择策略： 根据问题的特点选择可能能够获得最优解的贪心策略。
2. 验证策略： 采用归纳证明的思想，证明贪心策略的正确性。

实现模式

常见的贪心构造算法实现模式有两种：

1. 优先队列模式： 从初始状态开始，将所有可能的解方案按照其某个指标（如利润或者权重）降序排列，并按照指定的顺序进行操作，直到达到最终状态。
2. 双指针模式： 在某些问题中，双指针能够快速的定位问题的最优解。通过指针的移动，计算出以当前状态作为开头或结尾时的最优解，从而实现问题的最优解。

示例

下面给出两个示例，说明贪心构造算法的基本实现模式。

例1：买卖股票的最佳时机II

题目描述：

给定一个数组，其中第 i 个元素代表股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

示例：

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第2天以1的价格买入，在第3天以5的价格卖出，收益4；在第4天以3的价格买入，在第5天以6的价格卖出，收益3。总共收益=4+3=7

解法：

这题的解法就是使用贪心策略。我们假设股票价格数组为prices，则在第i天可选择买进，第i+1天可选择卖出，这样可以获得价格差（此创建议传递一个二维dp数组记录下标i对应天数的最优解）。最终的最优解就是所有差值大于零的数字元素之和。

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                result += prices[i] - prices[i - 1];
            }
        }
        return result;
    }
}

例2：按摩师

题目描述：

假设你受雇于一家按摩店，店里面有一些按摩师傅。你可以接受预约，但不能接受相邻的预约，即如果你在第 i 天接受了预约，那么你就不能再在第 i+1 天接受预约。

示例：

输入: [1,2,3,1]
输出: 4
解释: 接受奇数信号和预约。

解法：

这道题的解法是采用双指针模式。我们使用dp[i]数组记录第i天可以接受的最大预约时间。根据该数组的规则，最优解其实就是dp[i+1]和dp[i+2]+a[i]的最大值。我们使用两个变量p1和p2作为指针，分别记录上一个dp[i+2]和当前dp[i+1]的结果，最后计算得出dp[i]的值。

class Solution {
    public int massage(int[] nums) {
        int p1 = 0;
        int p2 = 0;
        for (int i = 0; i < nums.length; i++) {
            int temp = p2;
            p2 = Math.max(p2, p1 + nums[i]);
            p1 = temp;
        }
        return p2;
    }
}

结语

通过上面的例题，我们可以看出，贪心算法在求解最优解问题中具有非常重要的作用。不过，在实现过程中，需要理清思路，正确选择策略，验证策略的正确性。