贪心算法学习

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。然而，要注意的是贪心算法并不总是能产生全局最优解，对于某些问题，贪心算法所得的结果可能只是局部最优解。

贪心算法的基本思路：

建立数学模型来描述问题：首先，我们需要把问题抽象化，用数学模型来描述。这通常涉及到定义问题的状态、目标函数以及约束条件。
证明贪心选择性质：这是使用贪心算法的关键。我们需要证明问题具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优选择（贪心选择）来达到。
设计贪心算法：根据贪心选择性质，设计出一个逐步构造最优解的贪心算法。
分析算法的正确性：证明贪心算法能够得出全局最优解，或者在某些情况下至少能得到近似最优解。
贪心算法的特点：
贪心性：每一步都选择当前状态下的最好或最优解。
局部最优解：通过一系列局部最优选择来构造全局最优解。
不能保证全局最优：在某些问题中，贪心算法可能只能得到局部最优解，而不是全局最优解。
背包问题（Knapsack Problem）
给定一组物品，每个物品都有一定的重量和价值，要求在不超过背包承重的情况下，使得背包内物品的总价值最大。
贪心策略：每次选择单位重量价值最高的物品。
注意：这种贪心策略并不总是能得到全局最优解。在某些情况下，可能需要选择单位重量价值不是最高的物品以达到全局最优。因此，背包问题通常使用动态规划来解决。

贪心算法与动态规划的区别：

动态规划：通常用于求解具有重叠子问题和最优子结构特性的问题。它通过保存子问题的解来避免重复计算，从而提高了算法的效率。
贪心算法：每一步都做出在当前状态下最好或最优的选择，希望通过这些局部最优选择来达到全局最优。它不保存子问题的解，因此空间复杂度通常较低。然而，它不能保证总是得到全局最优解。
总之，贪心算法是一种简单而有效的算法设计技术，特别适用于具有贪心选择性质的问题。但在使用时需要注意其局限性，避免在不适用的情况下使用贪心算法导致得到错误的解。

附上两道比较好的题目
最短无序连续子数组

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int maxn = Integer.MIN_VALUE, right = -1;
        int minn = Integer.MAX_VALUE, left = -1;
        for (int i = 0; i < n; i++) {
            if (maxn > nums[i]) {
                right = i;
            } else {
                maxn = nums[i];
            }
            if (minn < nums[n - i - 1]) {
                left = n - i - 1;
            } else {
                minn = nums[n - i - 1];
            }
        }
        return right == -1 ? 0 : right - left + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最大数

class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (y + x).compareTo(x + y));
        if (strs[0].equals("0"))
            return "0";
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15