算法之最后一块石头重量

1046. 最后一块石头的重量 #

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

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

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

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

实现：

1.非递归

排序后比较最后面两个

不同差放数组，递归直至边界数组长度 <= 1

1
/**
2
 * @param {number[]} stones
3
 * @return {number}
4
 */
5
var lastStoneWeight = function (stones) {
6
  if (stones.length <= 1) {
7
    return stones;
8
  }
9
  stones.sort((a, b) => a - b);
10
  while (stones.length > 1) {
11
    const pre = stones.pop();
12
    const next = stones.pop();
13
    if (pre !== next) {
14
      const temp = pre - next;
15
      let i = 0;
16
      while (stones[i] < temp) {
17
        i++;
18
      }
19
      stones.splice(i, 0, temp);
20
    }
21
  }
22
  return stones.length ? stones[0] : 0;
23
};

1046. 最后一块石头的重量#

1046. 最后一块石头的重量 #