leetcode 1046. Last Stone Weight

以你之姓@ 2023-07-10 11:10 10阅读 0赞

**目录**

一、问题分析

二、代码实现

1、大顶堆

2、桶排序

--------------------

[https://leetcode.com/problems/last-stone-weight/][https_leetcode.com_problems_last-stone-weight]

给定一个石头的集合，每个石头的重量为正数，每次拿两个石头进行碰撞：若一样重，则不添加石头；若一轻一重，则添加两者重量之差的绝对值的石头。最终集合中最多只剩一个石头，如果剩余1个则返回其重量；如果没有石头则返回0

## 一、问题分析 ##

测试用例：

Example 1:
    
    Input: [2,7,4,1,8,1]
    Output: 1
    Explanation: 
    We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
    we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
    we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
    we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

思路一：使用大顶堆，每次拿两个最大元素，当只拿到一个时将其返回，当一个元素都没拿到时返回0。

这道题其实有贪心的思想在里面——每次拿两个最大的石头，这也启示我们贪心相关的题目可以考虑能否用堆这种数据结构。

思路二：使用桶排序，由于题目提示1<=石头个数<=30、1<=每个石头的重量<=1000，所以可以新建一个长度为1001的数组作为特定重量和该重量的石头个数的映射，下标表示重量，元素表示石头个数。从后往前遍历，如果石头个数大于一个，则通过对其取余使得该重量的石头两两碰撞。如果本来只有一个石头或者碰撞完只剩一个石头，则找到下一个存在石头的重量，添加一个重量为前者减去后者之差的石头，如果找不到下一个存在石头的重量（下标遍历到0），则将最后一个石头直接返回。

## 二、代码实现 ##

### 1、大顶堆 ###

class Solution {
        public int lastStoneWeight(int[] stones) {
            //大顶堆
            PriorityQueue<Integer> heap = new PriorityQueue<>((i1, i2) -> i2 - i1);        
            for (int e : stones) {
                heap.add(e);
            }
            
            int max1 = -1;
            int max2 = -1;
            boolean flag = false;        //如果最终为false，说明石堆中一个石头也没有，反之说明只有一个石头
            //当没有继续进入循环时，说明堆中所有元素已经取完了
            while (!heap.isEmpty()) {
                //System.out.println(heap);
                max1 = heap.poll();
                if (heap.isEmpty()) {
                    //只拿到一个元素
                    flag = true;
                    break;
                }
                max2 = heap.poll();
                
                //两个石头一样重
                if (max1 == max2) {
                    continue;
                }
                //一轻一重
                heap.add(Math.abs(max2 - max1));
            }
            
            return flag ? max1 : 0;
        }
    }

### 2、桶排序 ###

class Solution {
        
        //桶排序
        public int lastStoneWeight(int[] stones) {
            //数组下标表示重量，价值...
            int[] stoneWeightMap = new int[1001];   
            for (int stone: stones) {
                stoneWeightMap[stone]++;
            }
            
            int i = 1000, j;
            while(i > 0) {
                if(stoneWeightMap[i] == 0) {
                    //没有重量为i的石头
                    i--;
                    continue;
                } else {
                    stoneWeightMap[i] = stoneWeightMap[i] % 2;  //将重量为i的石头两两抵消之后，最多剩余一个重量为i的石头
                    //如果此重量i没有剩余的石头
                    if (stoneWeightMap[i] == 0) {
                        continue;
                    }
                    //如果只剩一个重量为i的石头，找到下一个有石头的重量
                    j = i - 1;
                    while(j > 0 && stoneWeightMap[j] == 0) {
                        j--;
                    }
                    if(j == 0) {    //如果找不到合法的重量，则此重量i为最后一个石头
                        return i;
                    }
                    stoneWeightMap[i - j]++;    //找到合法的重量，添加用较大的i减去较小的j的石头
                    stoneWeightMap[j]--; 
                    //i--;
                    //i = j;  //用这一句替代上一句可以直接跨越一些没有石头的重量
                    i = (i - j) > j ? (i - j) : j;
                }
            }
            
            return 0;
        }
        
    }

参考：

[https://leetcode.com/problems/last-stone-weight/discuss/295236/Java-Simple-O(N)-without-using-Priority-Queue][https_leetcode.com_problems_last-stone-weight_discuss_295236_Java-Simple-O_N_-without-using-Priority-Queue]

[https://leetcode.com/problems/last-stone-weight/discuss/354141/Java-or-Max-Heap-or-Short-and-Easy-or-Time-and-Memory-beats-100][https_leetcode.com_problems_last-stone-weight_discuss_354141_Java-or-Max-Heap-or-Short-and-Easy-or-Time-and-Memory-beats-100]

[https://leetcode.com/problems/last-stone-weight/discuss/294925/C%2B%2B-Multiset-and-Priority-Queue][https_leetcode.com_problems_last-stone-weight_discuss_294925_C_2B_2B-Multiset-and-Priority-Queue]

[https_leetcode.com_problems_last-stone-weight]: https://leetcode.com/problems/last-stone-weight/
[https_leetcode.com_problems_last-stone-weight_discuss_295236_Java-Simple-O_N_-without-using-Priority-Queue]: https://leetcode.com/problems/last-stone-weight/discuss/295236/Java-Simple-O%28N%29-without-using-Priority-Queue
[https_leetcode.com_problems_last-stone-weight_discuss_354141_Java-or-Max-Heap-or-Short-and-Easy-or-Time-and-Memory-beats-100]: https://leetcode.com/problems/last-stone-weight/discuss/354141/Java-or-Max-Heap-or-Short-and-Easy-or-Time-and-Memory-beats-100
[https_leetcode.com_problems_last-stone-weight_discuss_294925_C_2B_2B-Multiset-and-Priority-Queue]: https://leetcode.com/problems/last-stone-weight/discuss/294925/C%2B%2B-Multiset-and-Priority-Queue