算法-堆/排序-最后一块石头的重量

浅浅的花香味﹌ 2022-12-31 15:18 151阅读 0赞

# 算法-堆/排序-最后一块石头的重量 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2.1 排序法 #

## 2.1 解题思路 ##

1.  先将数组排序
2.  然后每次取最后两个数字，  
    此时将最后一个数字更新为`last - last2`，倒数第二个数字设为0
3.  随后重新排序，排序后0排到了最前面，而最大和次大的石头又到了数组最后两位
4.  循环2和3的过程，直到倒数第二个数字为0，即已经合并完毕
5.  最后返回末尾数字即可，可能为0也可能为没销毁完的石头重量

## 2.2 代码 ##

class Solution { 
        public int lastStoneWeight(int[] stones) { 
            if(stones.length == 1){ 
                return stones[0];
            }
            Arrays.sort(stones);
            while(stones[stones.length - 2] != 0){ 
                int last = stones[stones.length - 1];
                int last2 = stones[stones.length - 2];
                stones[stones.length - 1] = last - last2;
                stones[stones.length - 2] = 0;
                Arrays.sort(stones);
            }
            return stones[stones.length - 1];
        }
    }

## 2.3 时间复杂度 ##

O(N^2logN)。

## 2.4 空间复杂度 ##

O(1)

# 3 堆-由优先级队列实现 #

## 3.1 解题思路 ##

1.  采用一个优先级队列模仿大顶堆
2.  每次从堆中取出两个元素，且如果值不同就将差值插入大顶堆并调整。
3.  循环2，直到堆大小不大于1
4.  最后如果堆大小为1，就返回堆顶元素；否则返回0

## 3.2 代码 ##

class Solution { 
        public int lastStoneWeight(int[] stones) { 
            if(stones.length == 1){ 
                return stones[0];
            }
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((a,b)->b - a);
            for(int stone : stones){ 
                maxHeap.offer(stone);
            }
            while(maxHeap.size() > 1){ 
                int last = maxHeap.poll();
                int last2 = maxHeap.poll();
                if(last > last2){ 
                    maxHeap.offer(last - last2);
                } 
            }
            if(maxHeap.size() > 0){ 
                return maxHeap.poll();
            } else{ 
                return 0;
            }
        }
    }

## 3.3 时间复杂度 ##

O(Nlogn)

*  堆插入和删除需要调整堆，O(logn)，
 *  查找中位数时直接从堆顶找出即可，O(1)

## 3.4 空间复杂度 ##

O(N)

# 4 自己实现的堆 #

## 4.1 解题思路 ##

面试时如果直接用`PriorityQueue`面试官可能会不满意，就是考察你写堆你特么给我个封装好的类？

所以这里自己实现。

## 4.2 代码 ##

class Solution { 
        public int lastStoneWeight(int[] stones) { 
            if(stones.length == 1){ 
                return stones[0];
            }
            // 先将数组数调整为大顶堆
            for(int i = 1; i < stones.length; i++){ 
                adjustMaxHeapUp(stones, i);
            }
            int length = stones.length;
            while(length > 1){ 
                // 开始从大顶堆取堆顶
                int last = stones[0];
                length--;
                // 调整大顶堆
                stones[0] = stones[length];
                stones[length] = 0;
                adjustMaxHeapDown(stones, length);
    
                int last2 = stones[0];
                length--;
                stones[0] = stones[length];
                stones[length] = 0;
                adjustMaxHeapDown(stones, length);
    
                if(last > last2){ 
                    int reside = last - last2;
                    length++;
                    stones[length - 1] = reside;
                    adjustMaxHeapUp(stones, length - 1); 
                } else{ 
                    // 直接粉碎了，继续循环
                }
            }
            if(length == 1){ 
                return stones[0];
            } else{ 
                return 0;
            }
        }
        // 自底向上调整大顶堆
        public void adjustMaxHeapUp(int[] stones, int index){ 
            if(stones.length < 2){ 
                return;
            }
            int tmp = stones[index];
            while(index > 0){ 
                int parent = (index - 1) / 2;
                if(stones[parent] < tmp){ 
                    stones[index] = stones[parent];
                    index = parent;
                } else{ 
                    break;
                }
            }
            stones[index] = tmp;
        }
    
        // 自顶向下调整大顶堆
        public void adjustMaxHeapDown(int[] stones, int length){ 
            if(stones.length < 2){ 
                return;
            }
            int tmp = stones[0];
            int index = 0;
            while(index * 2 + 1 < length){ 
                int child = index * 2 + 1;
                if(child + 1 < length && stones[child+1] > stones[child] ){ 
                    child = child + 1;
                }
                if(stones[child] <= tmp){ 
                    // 此时不需要调整了
                    break;
                } else{ 
                    // 此时需交换当前节点和孩子中较大的那个
                    stones[index] = stones[child];
                    index = child;
                }
            }
            
            stones[index] = tmp;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221120/e893ddf68b1440cfa44b66b2bd1c6cef.png