leetcode
leetcode 1751 ~ 1800
移除石子使总数最小

移除石子使总数最小

难度:

标签:

题目描述

代码结果

运行时间: 116 ms, 内存: 26.8 MB


/*
题目思路:
1. 使用Java Stream处理。首先对数组进行排序,从最大值开始,进行k次减半操作。
2. 每次操作后,将新的石子数重新排序并继续处理。
3. 由于需要高效处理,使用Stream在排序后限制为前k个元素,并对剩余的元素总和进行计算。
*/
import java.util.Arrays;

public class MinStoneSumStream {
    public int minStoneSum(int[] piles, int k) {
        for (int i = 0; i < k; i++) {
            // 对数组排序
            Arrays.sort(piles);
            // 减去最大堆的一半石子数
            piles[piles.length - 1] -= piles[piles.length - 1] / 2;
        }
        // 返回数组总和
        return Arrays.stream(piles).sum();
    }
}

解释

方法:

题解采用了计数排序的方法来处理问题,以达到较高的效率。首先,算法通过遍历石子堆数组 'piles' 来统计每种石子数量的堆数,同时计算所有石子的总数。接着,从石子数量最大的堆开始,尽可能多地执行移除操作,直到操作次数 'k' 耗尽或没有可以移除的石子堆为止。具体来说,每次从最大的石子堆中减去 'floor(i / 2)' 的石子,更新总数,并递减操作次数 'k'。该方法通过优先移除最多的石子来确保剩余石子总数最小。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
算法中的`计数数组cnt`的大小固定为10001,这是基于什么假设或数据限制?
该算法假设石子的最大数量不超过10000。这种假设可能基于题目的数据限制或实际应用场景中石子数量的常见范围。固定计数数组的大小为10001(从0到10000)是为了直接使用石子数量作为索引,便于快速访问和更新对应石子堆的数量。如果石子数量能超过10000,这种方法就会导致数组越界错误。
🦆
在执行移除操作时,为什么选择从最大的石子数量开始减少而不是其他方式?
从最大的石子数量开始减少是为了尽可能效率地减少总石子数量。每次操作都会移除堆中石子数量的一半(向下取整),因此从较大的堆开始移除可以更快地减少总石子数。这种策略是贪心算法的一种表现,旨在每步操作中取得最大的减少效果。
🦆
如果在减少石子过程中,`reduce`的计算结果为0(例如i为1时),这种情况如何处理,是否会影响算法的效率?
当`reduce`的计算结果为0时(例如`i`为1时),该次操作实际上没有减少任何石子,这确实会影响算法的效率。在实际执行中,如果`reduce`为0,应该跳过该步操作,因为它不会改变石子的总数。这种情况可以通过在操作前检查`reduce`是否为0来优化,避免无效操作,从而提高算法的整体效率。
🦆
在更新计数数组时,`cnt[i - reduce] += mul`能否保证`i - reduce`不会产生负索引?如果有可能,该如何防止?
在原算法中,`i - reduce`可能会产生负索引,尤其是当`i`较小时。例如,如果`i`为1且`reduce`同样为1,则`i - reduce`为0,不会产生负索引,但接近边界。为确保不产生负索引,应在更新计数数组前检查`i - reduce`是否大于等于0。在实际实现中,可以通过设置`reduce = min(i // 2, i)`来确保`i - reduce`始终非负。这样的修改不仅防止了负索引的出现,也确保了算法的安全和稳定。

相关问题