上海嘉定网站设计,wordpress导航怎么弄,贵州省城乡与住房建设厅网站,做企业网站设计价格是多少一、题目
1、题目描述 给你一个整数数组 piles #xff0c;数组 下标从 0 开始 #xff0c;其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k #xff0c;请你执行下述操作 恰好 k 次#xff1a; 选出任一石子堆 piles[i] #xff0c;并从中 移除 floor(pil…一、题目
1、题目描述 给你一个整数数组 piles 数组 下标从 0 开始 其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k 请你执行下述操作 恰好 k 次 选出任一石子堆 piles[i] 并从中 移除 floor(piles[i] / 2) 颗石子。 注意你可以对 同一堆 石子多次执行此操作。 返回执行 k 次操作后剩下石子的 最小 总数。 floor(x) 为 小于 或 等于 x 的 最大 整数。即对 x 向下取整。 2、接口描述
class Solution {
public:int minStoneSum(vectorint piles, int k) {}
}; 3、原题链接
1962. 移除石子使总数最小 二、解题报告
1、思路分析
显然我们每次都移除数目最多的那一堆最后一定能够满足剩下的最小每次找到最大数目的石子堆我们可以选择使用大根堆来实现。
我们如果将数组元素都插入堆中那么需要O(nlogn)的时间复杂度和O(n)的空间复杂度我们可以选择直接原地建堆即在原数组上建堆采用向下调整算法自下而上建堆可以达到O(n)的时间复杂度建堆关于堆的两种构建算法以及时间复杂度证明见堆/二叉堆详解[C/C]-CSDN博客
然后执行k次操作如果堆顶元素为1那么此时无法再拿出元素我们直接退出循环即可
2、复杂度 时间复杂度O(n klogn) 空间复杂度O(1) 3、代码详解
C版本
class Solution {
public:int minStoneSum(vectorint piles, int k) {//原地堆化默认大根堆make_heap(piles.begin() , piles.end());while(k-- (piles[0] ^ 1)){pop_heap(piles.begin() , piles.end());//弹出堆顶到末尾piles.back() - piles.back() / 2;push_heap(piles.begin() , piles.end());//向上调整插入末尾元素到堆}return accumulate(piles.begin() , piles.end() , 0);}
};
python3版本
class Solution:def minStoneSum(self, piles: List[int], k: int) - int:for i in range(len(piles)):piles[i] * -1heapify(piles)while k and (piles[0] ^ 1):heapreplace(piles , piles[0] // 2) # 负数向下取整的绝对值和正数向上取整绝对值一样k - 1return -sum(piles)
