学习记录：js算法（六十四）：最后一块石头的重量
最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 加粗样式x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
思路一
var lastStoneWeight = function(stones) {
while (stones.length > 1) {
stones.sort((a, b) => b - a); // 降序排序
let y = stones.shift(); // 取出最大值
let x = stones.shift(); // 取出第二大的值
if (y !== x) {
stones.push(y - x); // 如果不相等，将差值放回数组
}
}
return stones.length ? stones[0] : 0; // 返回最后一个元素或0
};
讲解
解题思路是通过持续找出并处理数组中两个最大的元素，直到数组中只剩下一个元素或没有元素为止
- 循环处理:
○ 创建一个循环，只要stones数组中元素的个数大于1，就进入循环。
○ 每次循环的目的是找出并处理两个最大的石头。- 排序:
○ 在循环内，首先对stones数组进行排序，使用降序排序，即较大的元素排在前面。这样做的目的是确保数组的第一个元素是最大的，第二个元素是次大的。- 取出最大值:
○ 使用 shift() 方法从排序后的 stones 数组中依次取出第一个和第二个元素，这两个元素分别是当前数组中最大的和次大的石头的重量。- 粉碎石头:
○ 检查取出的两个元素是否相等。如果不相等，根据题目规则，较大的石头将减去较小石头的重量，得到新的石头重量。
○ 如果两个石头的重量相等，它们都将被完全粉碎，不产生新的石头。- 更新数组:
○ 如果产生了新的石头重量（即两个石头的重量不相等），将这个新的石头重量添加回stones数组中。
○ 注意，由于我们在每次循环开始时都会对数组进行排序，所以在添加新石头后，数组的状态将被用于下一次循环的排序。- 终止条件:
○ 当stones数组中只剩下不到两个元素时，循环结束。这意味着要么数组为空，要么只包含一个元素。- 返回结果:
○ 最后，检查stones数组的长度。如果数组长度为0，返回0，表示没有石头剩下。如果数组长度为1，返回数组中唯一的元素，即最后剩下的石头的重量。
思路二
var lastStoneWeight = function(stones) {
// 创建一个最大堆
const maxHeap = new MaxHeap();
// 将所有石头的重量插入堆中
stones.forEach(stone => maxHeap.insert(stone));
// 只要堆中还有至少两块石头
while (maxHeap.size() > 1) {
// 从堆中取出两块最大的石头
const first = maxHeap.extractMax();
const second = maxHeap.extractMax();
// 根据题目规则处理石头
if (first !== second) {
// 将粉碎后的新石头重新插入堆中
maxHeap.insert(first - second);
}
}
// 返回堆中剩下的石头的重量，如果没有石头则返回0
return maxHeap.isEmpty() ? 0 : maxHeap.extractMax();
};
// MaxHeap类定义
class MaxHeap {
constructor() {
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.bubbleUp();
}
extractMax() {
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown();
}
return max;
}
bubbleUp() {
let idx = this.heap.length - 1;
const element = this.heap[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.heap[parentIdx];
if (element <= parent) break;
this.heap[idx] = parent;
this.heap[parentIdx] = element;
idx = parentIdx;
}
}
sinkDown() {
let idx = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.heap[leftChildIdx];
if (leftChild > element) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.heap[rightChildIdx];
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.heap[idx] = this.heap[swap];
this.heap[swap] = element;
idx = swap;
}
}
size() {
return this.heap.length;
}
isEmpty() {
return this.heap.length === 0;
}
};
讲解
利用最大堆（MaxHeap）数据结构来高效地找到并处理数组中的最大元素
- 创建最大堆：
○ 定义一个MaxHeap类，用于创建和管理最大堆。最大堆的性质是每个父节点的值都不小于其子节点的值，这样堆的根节点始终是堆中最大的元素。- 插入石头重量：
○ 使用forEach循环，将stones数组中的所有石头重量插入到最大堆中。插入时，调用insert方法，该方法将元素添加到堆的末尾，并通过bubbleUp方法保持堆的性质。- 处理石头：
○ 当堆中元素个数大于1时，进入循环。
○ 通过extractMax方法从堆中移除并返回最大的石头重量，此操作会保持堆的性质。
○ 重复extractMax，移除并返回堆中当前最大的石头重量，这是第二次最大的石头。
○ 如果两次移除的石头重量不相等，计算差值（较大石头减去较小石头），并将这个差值重新插入堆中。- 返回结果：
○ 循环结束后，堆中最多只剩下一个元素，即最后一块石头的重量。如果堆为空，说明所有石头都已完全粉碎，返回0；否则返回堆顶元素的值。
原文地址：https://blog.csdn.net/weixin_48677331/article/details/142931768
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！