【Leetcode Daily】2208将数组和减半的最少操作次数

发表于2025-12-19|更新于2025-12-19|力扣日常 | LeetcodeDaily

|总字数:249|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个数组，现在需要你对这个数组做操作，即取一个数减半，求整个数组之和不大于原来一半的最少操作数。

思路分享

想要每次操作尽可能多减少数值，就每次都要取其中的最大值，这里就可以用大顶堆来辅助了。
不过灵神指出，为了尽可能准确，应该尽量避免浮点数的产生，通过看不懂的每个数字除不超过 20 次，所以就把每个数乘 2^20。

https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/solutions/1353455/by-endlesscheng-xzk2/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        s = sum(nums) / 2
        cur_s = 0
        for i in range(len(nums)):
            nums[i] = -nums[i]
        heapq.heapify(nums)
        ans = 0
        while(cur_s < s):
            ans += 1
            new_num = nums[0]/2
            cur_s -= new_num
            heapq.heapreplace(nums, new_num)
            # print(cur_s)
            # print(nums)
        return ans

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/9bfc0eb1.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

相关推荐

【Leetcode Daily】2558从数量最多的堆取走礼物

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组，并重复 k 次找其中最大的数字平方再放回去，返回最后数组的数值和。思路分享对于这种找最大/最小的情况，可以考虑堆。堆会自然维护堆顶为所有元素的最小或者最大，并且在去除这个最值后，也能很方便地提取出下一个最值。那有人可能就问了，之前学的单调栈和单调队列不也能方便地取最值吗，为什么不用？原因是单调栈和单调队列的维护效率不及堆，在本题，提取的最值处理后又要放回去，提取是方便，但放回去的最坏情况是O(n)，即从最大值变最小值。 https://leetcode.cn/problems/take-gifts-from-the-richest-pile/solutions/2501655/yuan-di-dui-hua-o1-kong-jian-fu-ti-dan-p-fzdh/ 代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def pickGifts(self, gifts: List[int], k: int) ->...

【Leetcode Daily】295数据流的中位数

题目浅析想查看原题可以点击题目链接。简单地说，就是在给数组增添数字的过程中，可能需要随时输出当前的中位数。思路分享构建大小堆，也就是一个大顶堆和一个小顶堆，前者相当于当前数字的左侧，后者相当于右侧，这样就能随时得到左边最大和右边最小的数值，也就方便计算中位数了。 https://leetcode.cn/problems/find-median-from-data-stream/solutions/3015873/ru-he-zi-ran-yin-ru-da-xiao-dui-jian-ji-4v22k/ 具体而言，需要保证两点，第一是优先把数字放左侧，随后如果左侧的数字更多，再放右边；第二保证左侧的所有数字都小于右侧，所以如果要加到左侧的数字，可以先加到右侧，再从右侧获取最小的数字加到左侧。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617181920212223class MedianFinder: def __init__(self): self.left = [] ...

【Leetcode Daily】480滑动窗口中位数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组和一个窗口大小 k，现在规定这个窗口从数组最左侧移到最右侧，求每个窗口的中位数。思路分享比起【Leetcode Daily】295数据流的中位数，本题多加了需要删除的功能，但是对于堆而言，想要找到其中的值再删除，相当于重建，复杂度比较高。这里就可以引入“懒删除堆”，顾名思义，这个堆删除值不会立刻删除，而是先记录下来，在做入堆，取堆顶等操作的同时，检查堆顶是否为需要删除的值，是则直接弹出堆顶，不是则照常操作。 https://leetcode.cn/problems/sliding-window-median/solutions/3628827/295-ti-lan-shan-chu-dui-pythonjavacgojsr-66ch/ 注意，对于大小堆这种写法引入删除后，注意保持 left 的 size 与 right 相等或者多...

【Leetcode Daily】1046最后一块石头的重量

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个一维数组，当作一堆石头重量，每次选两个最重的碰，将两个石头之差放回去，求最后剩下的一个石头重量（没有就0）思路分享这种多次求最值的，用堆，只是要记得，python的 heapify 默认最小堆，所以数字先做负数处理再堆化。 https://leetcode.cn/problems/last-stone-weight/solutions/540130/zui-hou-yi-kuai-shi-tou-de-zhong-liang-b-xgsx/ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213class Solution: def lastStoneWeight(self, stones: List[int]) -> int: for i in range(len(stones)): stones[i] = -stones[i] heapify(stones) while stones and...

【Leetcode Daily】3264K次乘运算后的最终数组I

题目浅析想查看原题可以点击题目链接。简单地说，就是给一维数组，k 和 m，k 次从数组中找到最小的值，原地乘 m，求最终的数组。思路分享本题比较重要的一点是，题目要求是在原地进行乘法操作，所以如果要用堆处理，需要同时保存下标信息。接下来就好说了，先做出保存下标信息的堆，然后不断取出小值乘 m 放回，直到达到 k 次。代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: rec = [(x, i) for i, x in enumerate(nums)] heapify(rec) for _ in range(k): new_num = rec[0][0] * multiplier new_index = rec[0][1] ...

【Leetcode Daily】2336无限集中的最小数字

题目浅析想查看原题可以点击题目链接。简单地说，就是要实现一个数据结构，这个结构初始是一个正整数集合，要求能返回集合中的最小值，并随时往集合里加正整数。思路分享返回最小值，可以用堆来维护，至于堆是维护新加的，还是已有的，就看具体实现方式。但都需要思考如何去重，避免重复添加。官方题解提到了 SortedSet，可以在完成堆的任务的同时，高效去重。就不需要像参考题解这样，又用堆，也用 Set 了。 https://leetcode.cn/problems/smallest-number-in-infinite-set/solutions/2542156/wu-xian-ji-zhong-de-zui-xiao-shu-zi-by-l-5mfr/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718192021222324252627282930class SmallestInfiniteSet: def __init__(self): self.heap = [1] ...

数据加载中