跳到主要内容

贪心算法

问题​

Java 中贪心算法的常见面试题有哪些？

答案​

贪心的核心：每一步选择局部最优，最终达到全局最优。关键在于证明贪心选择的正确性。

跳跃游戏（LeetCode 55）​

贪心：维护最远可达位置
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;  // 当前位置超过最远可达
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

跳跃游戏 II（LeetCode 45）​

贪心：最少跳跃次数
public int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {  // 到达当前跳跃的边界，必须再跳一次
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

分发糖果（LeetCode 135）​

两次遍历：先左到右，再右到左
public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);
    
    // 从左到右：右边比左边大，糖果+1
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    }
    // 从右到左：左边比右边大，取较大值
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
    return Arrays.stream(candies).sum();
}

合并区间（LeetCode 56）​

按起点排序后贪心合并
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1)[1] = 
                Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[0][]);
}

无重叠区间（LeetCode 435）​

按结束时间排序，贪心选不重叠的
public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // 按结束时间排序
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= end) {
            end = interval[1];  // 不重叠，保留
        } else {
            count++;  // 重叠，移除
        }
    }
    return count;
}

常见面试问题​

Q1: 贪心和动态规划的区别？​

答案：

对比贪心DP
决策方式每步局部最优，不回头考虑所有子问题
时间复杂度通常更低通常更高
正确性需要证明贪心有效状态转移保证正确
典型题区间调度、跳跃游戏背包、最长子序列

Q2: 怎么判断一道题能不能用贪心？​

答案：

  • 看是否满足贪心选择性质：局部最优能推导出全局最优
  • 看是否满足最优子结构
  • 先试贪心，找不到反例就行；有反例就考虑 DP

相关链接​