letcode每日一题-最后一块石头的重量

比眉伴天荒 2022-12-31 14:23 134阅读 0赞

临近年底，工作增多了，少了好几天的，元旦补一下吧，先记录一下今天的:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70][]

首先看到选出两块最重的石头，这种排前几的问题，使用堆排序是最好的，所以这里我们只需要每次用堆排序排除前两大 的石头，如果体积

相等就跳过，如果不相等就把剩余的继续放入数组中即可，代码 实现如下：

public int lastStoneWeight(int[] stones) {
            if(stones.length==1){
                return stones[0];
            }
            int live=0;
            for (int i=0;i<stones.length-1;i++){
                for(int j=0;j<2;j++){
                    heap_down(stones,stones.length-j-i);
                    swap(stones,0,stones.length-j-1-i);
                }
                live=Math.abs(stones[stones.length-1-i]-stones[stones.length-2-i]);
                if(live==0){
                    if(++i==(stones.length-2)){
                        return Math.abs(live-stones[0]);
                    }
                }else{
                    stones[stones.length-i-2]=live;
                }
            }
            return live;
        }
    
        /**
         * 构造大顶堆
         * @param datas
         */
        public static void heap_down(int[] datas,int size){
            for(int end=size-1;end>0;end-=2){
                int index=end;
                if(datas[end]<datas[end-1]){
                    index=end-1;
                }
                int parentIndex=(end-2)/2;
                if(datas[parentIndex]<datas[index]){
                    swap(datas,index,parentIndex);
                }
            }
        }
    
        public static void swap(int[] datas,int p1,int p2){
            int temp=datas[p1];
            datas[p1]=datas[p2];
            datas[p2]=temp;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/60ffa5071d1544e6ae538127be8ae5bd.png