LeetCode - 最后一块石头的重量

四周以前的一道周赛题（Easy难度），慢慢发现这两三周已经没有连续刷题了，大概率是因为又变懒了吧...

原题地址： https://leetcode-cn.com/contest/weekly-contest-137/problems/last-stone-weight/

题目描述：

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

提示：

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

解题思路：

限于自己的实力，所以每次都是采用的最简单暴力的方式。

1. 如果只有一个石头，直接返回这个石头本身
2. 如果两个石头，返回这两个石头的重量
3. 对所有石头排序，找到最重的两块，按照计算逻辑去进行减法，其中重量为x的肯定粉碎，重量为y的石头肯定是y=y-x。
4. 计算之后，再次进行排序，重复至最多一个石头有重量或都没有重量。

当然有个更好的办法，就是用优先队列，每次取优先队列里面前两个元素，然后如果y!=0，则将y再放回优先队列中。比每次都用Arrays.sort快（虽然这个时候的Arrays.sort的效率由于数组近乎于正确排序，所以效率也很高）。

中文官网题解：

https://leetcode-cn.com/problems/last-stone-weight/solution/

个人题解：

class Solution {
    public int lastStoneWeight(int[] stones) {
         if (stones.length == 1) {
            return stones[0];
        }
        if (stones.length == 2) {
            return Math.abs(stones[1] - stones[0]);
        }
        int j = -1;
        while (j != 1 && j != 0) {
            j = 0;
            Arrays.sort(stones);
            stones[stones.length - 1] -= stones[stones.length - 2];
            stones[stones.length - 2] = 0;
            for (int i : stones) {
                if (i != 0) {
                    j++;
                }
            }
        }
        Arrays.sort(stones);
        return stones[stones.length - 1];
    }
}

结果：

周赛途中提交，只能看到自己是否通过，是看不到自己的代码执行效率的，当时只知道自己的代码又是采用了暴力法，所以没报太大期望。最后结果果然是意料之中的正常结果（50%）。