贪心算法实战：三道经典 LeetCode 题解与思路分析

二、将数组和减半的最少操作次数

题目解析

题意很直观：每次选择一个数将其减半，目标是让总和减少一半所需的操作次数最少。

算法原理

为了让总和下降最快，每次操作都应该针对当前数组中的最大值进行减半。这提示我们使用大根堆（优先队列）来动态维护元素的最大值。

具体步骤如下：

1. 将所有元素放入最大堆中，并计算初始总和。
2. 每次取出堆顶最大值，将其减半后放回堆中，同时从总和中减去减半的数值。
3. 重复上述过程直到总和减少量达到目标值。

代码实现

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> pq = new PriorityQueue<>((a, b) -> Double.compare(b, a));
        double sum = 0;
        for (int num : nums) {
            double val = (double) num;
            sum += val;
            pq.offer(val);
        }
        
        double target = sum / 2.0;
        double reducedSum = 0;
        int operations = 0;
        
        while (reducedSum < target) {
            double maxVal = pq.poll();
            double half = maxVal / 2.0;
            reducedSum += half;
            pq.offer(half);
            operations++;
        }
        return operations;
    }
}

三、最大数

题目解析

给定一组非负整数，将它们排列成拼接后的最大整数字符串形式。

算法原理

关键在于自定义排序规则。对于两个数字字符串 a 和 b，如果 a + b > b + a，则 a 应该排在 b 前面。通过这种比较方式对数组排序，最后拼接即可得到结果。

需要注意边界情况：如果排序后第一个字符是 '0'，说明所有数字都是 0，直接返回 "0" 即可。

代码实现

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
        
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        
        if (sb.charAt(0) == '0') {
            return "0";
        }
        return sb.toString();
    }
}