leetcode 1962. 移除石子使总数最小

题目描述:

给你一个整数数组 piles ,数组 下标从 0 开始 ,其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ,请你执行下述操作 恰好 k 次:

选出任一石子堆 piles[i] ,并从中 移除 floor(piles[i] / 2) 颗石子。
注意:你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后,剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。(即,对 x 向下取整)。

 

示例 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 。
 

提示:

1 <= piles.length <= 105
1 <= piles[i] <= 104
1 <= k <= 105

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

 

public class RemoveStone {
    //元素可以改变顺序!!超时!!
    public int minStoneSum(int[] piles, int k) {
        for(int i = 0; i < k; i++){
            int max_number = 0;//当前轮最大的数值
            int max_number_index = 0;//当前值最大的下标
            for(int j = 0; j < piles.length; j++ ){
                if(piles[j] > max_number){
                    max_number_index = j;
                    max_number = piles[j];
                }
            }
            //去除当前值最的number的一半
            piles[max_number_index] -= (int) Math.floor(piles[max_number_index]/2);
        }
        int sum = 0;
        for(int i = 0; i < piles.length; i++){
            sum += piles[i];
        }
        return sum;
    }

    public int minStoneSum1(int[] piles, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);//构建大顶堆
        //将piles中元素入队
        for(int i = 0; i < piles.length; i++){
            pq.add(piles[i]);
        }
        //取堆顶元素减少一半并且重新放会堆中,循环k次
        //堆添加元素时间复杂度O(log N)
        for(int j = 0; j < k; j++){
            int top_que = pq.poll();
            top_que -= Math.floor(top_que/2.0);
            pq.add(top_que);
        }
        //计算和
        int sum = 0;
        for(Integer q: pq){
            sum += q;
        }
        return sum;
    }
    public int minStoneSum2(int[] piles, int k) {
        List<Integer> piles_list = new ArrayList<>();
        //将数组转换为list  超时!!
        for(int i = 0; i< piles.length;i++){
            piles_list.add(piles[i]);
        }

        //Collection.sort()采用的排序算法是一种改进的归并排序,归并算法的时间复杂度是O(nlog n)
        for(int j = 0; j < k; j++){
            piles_list.sort((a,b)->b-a);//先对list进行倒序排序
            piles_list.set(0, piles_list.get(0)-(int) Math.floor(piles_list.get(0)/2.0));//设置第一个值减少原来的一半
        }
        int sum =0;
        for(Integer q : piles_list){
            sum += q;
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] piles = new int[]{4,3,6,7};
        int k = 3;
        RemoveStone rs = new RemoveStone();
        int result = rs.minStoneSum2(piles, k);
        System.out.println(result);
    }
}

 

上一篇:【中等】爱吃香蕉的珂珂(抽象二分问题)


下一篇:PyQt5-tools 、PyQt Designer 安装遇到的问题解决