记录每日LeetCode 1962.移除石子使总数最小 Java实现
2023-12-24 00:45:30
题目描述:
给你一个整数数组
piles
,数组 下标从 0 开始 ,其中piles[i]
表示第i
堆石子中的石子数量。另给你一个整数k
,请你执行下述操作 恰好k
次:
- 选出任一石子堆
piles[i]
,并从中 移除floor(piles[i] / 2)
颗石子。注意:你可以对 同一堆 石子多次执行此操作。
返回执行
k
次操作后,剩下石子的 最小 总数。
floor(x)
为 小于 或 等于x
的 最大 整数。(即,对x
向下取整)。
初始代码:
class Solution {
public int minStoneSum(int[] piles, int k) {
}
}
示例1:
输入:piles = [5,4,9], k = 2 输出:12 解释:可能的执行情景如下: - 对第 2 堆石子执行移除操作,石子分布情况变成 [5,4,5] 。 - 对第 0 堆石子执行移除操作,石子分布情况变成 [3,4,5] 。 剩下石子的总数为 12 。
示例2:
输入:piles = [4,3,6,7], k = 3 输出:12 解释:可能的执行情景如下: - 对第 2 堆石子执行移除操作,石子分布情况变成 [4,3,3,7] 。 - 对第 3 堆石子执行移除操作,石子分布情况变成 [4,3,3,4] 。 - 对第 0 堆石子执行移除操作,石子分布情况变成 [2,3,3,4] 。 剩下石子的总数为 12 。
参考答案:
// 有猜到会执行超时 毕竟每变更一个元素就重新排序
// 这里吃了不懂堆(优先队列)的亏 其实思想差不多
class Solution {
public int minStoneSum(int[] piles, int k) {
int i = piles.length - 1;
int sum = 0;
// 当操作次数大于0的情况进行操作
while (k-- > 0) {
Arrays.sort(piles);
piles[i] -= piles[i] / 2;
}
// 操作完后对元素进行累加
for (int p : piles) {
sum += p;
}
return sum;
}
}
class Solution {
public int minStoneSum(int[] piles, int k) {
// 1、定义降序排序的优先队列并将数组元素放入
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (b - a));
Arrays.stream(piles).forEach(p -> queue.offer(p));
// 2、弹出第一个元素做处理并重新放入优先队列中
while (k-- > 0) {
int p = queue.poll();
p -= p >> 1;
queue.offer(p);
}
// 3、最后对处理完的队列进行累加返回
int sum = 0;
while (!queue.isEmpty()) {
sum += queue.poll();
}
return sum;
}
}
文章来源:https://blog.csdn.net/m0_65563175/article/details/135166458
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!