LeetCode Day 贪心算法 第 4 部分

贪心算法是一种在优化问题中很常用的算法设计策略。这个策略的核心理念是：在每一步选择中都采取当前认为最优的选择，从而希望能够达到全局最优解。LeetCode上的许多问题都能够用贪心算法来解决。在这篇文章中，我们将关注贪心算法的一些常见应用和解题技巧，帮助大家在LeetCode上打磨自己的技能。

贪心算法的基本思想

贪心算法的基本思想是局部最优解的选择会导向全局最优解。这种选择机制对于某些类型的问题有效，但并不适用于所有情况。因此，在应用贪心算法之前，我们需要仔细分析问题特性。适合使用贪心算法的问题通常具有以下特征：

最优子结构：问题的最优解能由其子问题的最优解构成。

无后效性：当前的选择不会影响未来的选择。

在理解了贪心算法的基本特性后，我们接下来就可以来看一些经典的贪心算法问题及其解法了。

经典的贪心算法问题

活动选择问题

活动选择问题是许多贪心算法的经典范例。给定一系列活动，每个活动都有一个起始时间和结束时间，我们的目标是选择尽可能多的活动，使得活动之间没有时间冲突。贪心策略是选择结束时间最早的活动。

以下是处理这个问题的Java代码：

import java.util.Arrays;
import java.util.Comparator;
public class ActivitySelection {
    static class Activity {
        int start;
        int end;
        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 6),
            new Activity(6, 8),
        };
        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));
        int lastEndTime = -1;
        int count = 0;
        for (Activity activity : activities) {
            if (activity.start >= lastEndTime) {
                lastEndTime = activity.end;
                count++;
            }
        }
        System.out.println("Maximum number of activities: " + count);
    }
}

最小生成树

最小生成树问题要求我们找到一个加权无向图的子集，使得这个子集连接了所有的顶点，并且总权重最小。经典的贪心算法有克鲁斯克尔算法和普里姆算法。这里将展示普里姆算法的简单实现。

import java.util.*;
public class MinimumSpanningTree {
    static class Edge {
        int source, dest, weight;
        Edge(int source, int dest, int weight) {
            this.source = source;
            this.dest = dest;
            this.weight = weight;
        }
    }
    public static void main(String[] args) {
        int V = 5;
        List edges = Arrays.asList(
            new Edge(0, 1, 2),
            new Edge(0, 2, 3),
            new Edge(1, 2, 1),
            new Edge(1, 3, 5),
            new Edge(2, 3, 4)
        );
        // Use Prim's algorithm to find MST
        boolean[] inMST = new boolean[V];
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(-1, 0, 0)); // Start with vertex 0
        int totalWeight = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (inMST[edge.dest]) continue;
            inMST[edge.dest] = true;
            totalWeight += edge.weight;
            for (Edge e : edges) {
                if (e.source == edge.dest && !inMST[e.dest]) {
                    pq.add(e);
                }
            }
        }
        System.out.println("Weight of Minimum Spanning Tree: " + totalWeight);
    }
}

贪心算法的优缺点

贪心算法的优点在于其直观性和实现的简单性。与其他算法相比，贪心算法通常具有较低的时间复杂度。然而，它也有缺点：很难证明贪心算法得到的解是全局最优，适用性有限。在使用贪心算法时，需要仔细分析问题的性质，确保可以使用该策略。

总结

贪心算法是一种强大的工具，在解决特定类型的问题时尤其有效。通过理解贪心算法的基本原则以及经典问题的解法，开发者能够快速而高效地找到许多问题的解决方案。建议大家在练习LeetCode题目时，多尝试使用贪心算法，提升自己的算法能力。