使用 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
函数的返回值有大于零、等于零和小于零三种。若其返回值小于零,则参与其计算的两个参数,将按前后顺序排列;若其返回值等于零,则两参数位置不变;若其返回值大于零,则后位参数将排在前位参数前。