使用 JavaScript 解决 LeetCode 第 1046 题,最后一块石头的重量,简单难度。

题目

原题链接

本题目是 LeetCode 题库第 1046 题,由此访问。

题目描述

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

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

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

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

提示:

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

解题

AC 样例

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
  // 排除边界条件
  if(stones.length == 0) return 0;
  if(stones.length == 1) return stones[0];
  // 数据升序排序
  stones = stones.sort((a, b) => a - b);
  const h = stones.pop(), l = stones.pop();
  if(l < h) {
    stones.push(h - l)
    return lastStoneWeight(stones);
  } else return lastStoneWeight(stones);
};

解题思路

根据题目要求,明确计算边界值,即若数据规模为 0,则直接返回 0;若数据规模为 1,则直接返回这个唯一的数据作为答案。

其功能部分,每次计算需要选取数据集中最大的两个数值进行比较,其如两数大小不同,将差值存入重新计算,直至最后一个或零个数值,即为答案。按照上述要求,选用递归函数可以快速解决问题。

在递归函数内部,先对数据集进行一次升序排序,确保最大的值在数组末尾。将最末端的两个数据依次取出(采用破坏操作)进行对比,前数与后数的关系可能是相等或大于,若前数大于后数,计算其差值并插入数组。后将剩余数据进行递归操作,重复这一计算流程。

若递归进入最后一轮,则触发边界条件,返回答案。

语法点

对数组内部进行排序时,使用排序函数。该函数使用原地算法对数组的元素进行排序,并返回数组。

// Array 原型提供的排序函数
Array.prototype.sort();

// sort() 语法
arr.sort([compareFunction])

若对数组直接采用排序函数,而没有设置比较函数compareFunction)时,数组数据按其 Unicode 位点排序。

compareFunction 用于自定义排序规则,接受两个参数,其返回值将影响排序函数计算。

compareFunction 函数的返回值有大于零、等于零和小于零三种。若其返回值小于零,则参与其计算的两个参数,将按前后顺序排列;若其返回值等于零,则两参数位置不变;若其返回值大于零,则后位参数将排在前位参数前。