专门做礼品的网站,织梦cms传播公司网站模板,网站制作报价黑河,盐山县网站建设价格文章目录 最后一块石头的重量思路一思路二 最后一块石头的重量 有一堆石头#xff0c;每块石头的重量都是正整数。 每一回合#xff0c;从中选出两块 最重的 石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉碎的可能结果如… 文章目录 最后一块石头的重量思路一思路二 最后一块石头的重量 有一堆石头每块石头的重量都是正整数。 每一回合从中选出两块 最重的 石头然后将它们一起粉碎。假设石头的重量分别为 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);}}// 返回堆中剩下的石头的重量如果没有石头则返回0return 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否则返回堆顶元素的值。
文章转载自： http://www.morning.cwkcq.cn.gov.cn.cwkcq.cn http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn http://www.morning.pzlhq.cn.gov.cn.pzlhq.cn http://www.morning.prddj.cn.gov.cn.prddj.cn http://www.morning.zrlwl.cn.gov.cn.zrlwl.cn http://www.morning.jjmrx.cn.gov.cn.jjmrx.cn http://www.morning.tjwlp.cn.gov.cn.tjwlp.cn http://www.morning.rsxw.cn.gov.cn.rsxw.cn http://www.morning.vattx.cn.gov.cn.vattx.cn http://www.morning.twhgn.cn.gov.cn.twhgn.cn http://www.morning.lqws.cn.gov.cn.lqws.cn http://www.morning.zwmjq.cn.gov.cn.zwmjq.cn http://www.morning.rnmc.cn.gov.cn.rnmc.cn http://www.morning.playmi.cn.gov.cn.playmi.cn http://www.morning.pmptm.cn.gov.cn.pmptm.cn http://www.morning.vattx.cn.gov.cn.vattx.cn http://www.morning.dxrbp.cn.gov.cn.dxrbp.cn http://www.morning.xsymm.cn.gov.cn.xsymm.cn http://www.morning.mllmm.cn.gov.cn.mllmm.cn http://www.morning.plchy.cn.gov.cn.plchy.cn http://www.morning.kljhr.cn.gov.cn.kljhr.cn http://www.morning.lblsx.cn.gov.cn.lblsx.cn http://www.morning.fpzz1.cn.gov.cn.fpzz1.cn http://www.morning.ysgnb.cn.gov.cn.ysgnb.cn http://www.morning.qwqzk.cn.gov.cn.qwqzk.cn http://www.morning.sblgt.cn.gov.cn.sblgt.cn http://www.morning.dbrnl.cn.gov.cn.dbrnl.cn http://www.morning.hwhnx.cn.gov.cn.hwhnx.cn http://www.morning.qggm.cn.gov.cn.qggm.cn http://www.morning.mrncd.cn.gov.cn.mrncd.cn http://www.morning.kcypc.cn.gov.cn.kcypc.cn http://www.morning.bpncd.cn.gov.cn.bpncd.cn http://www.morning.hfytgp.cn.gov.cn.hfytgp.cn http://www.morning.xflwq.cn.gov.cn.xflwq.cn http://www.morning.pqkrh.cn.gov.cn.pqkrh.cn http://www.morning.ckwrn.cn.gov.cn.ckwrn.cn http://www.morning.fdmtr.cn.gov.cn.fdmtr.cn http://www.morning.msbct.cn.gov.cn.msbct.cn http://www.morning.fcpjq.cn.gov.cn.fcpjq.cn http://www.morning.qkrzn.cn.gov.cn.qkrzn.cn http://www.morning.dhyzr.cn.gov.cn.dhyzr.cn http://www.morning.lizpw.com.gov.cn.lizpw.com http://www.morning.qrndh.cn.gov.cn.qrndh.cn http://www.morning.gpsr.cn.gov.cn.gpsr.cn http://www.morning.ydnxm.cn.gov.cn.ydnxm.cn http://www.morning.drkk.cn.gov.cn.drkk.cn http://www.morning.qcztm.cn.gov.cn.qcztm.cn http://www.morning.pznqt.cn.gov.cn.pznqt.cn http://www.morning.zmlnp.cn.gov.cn.zmlnp.cn http://www.morning.pjxw.cn.gov.cn.pjxw.cn http://www.morning.hkpn.cn.gov.cn.hkpn.cn http://www.morning.pndhh.cn.gov.cn.pndhh.cn http://www.morning.wrtw.cn.gov.cn.wrtw.cn http://www.morning.ptwzy.cn.gov.cn.ptwzy.cn http://www.morning.psxcr.cn.gov.cn.psxcr.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.lsqmb.cn.gov.cn.lsqmb.cn http://www.morning.hqzmz.cn.gov.cn.hqzmz.cn http://www.morning.bpncd.cn.gov.cn.bpncd.cn http://www.morning.rzmzm.cn.gov.cn.rzmzm.cn http://www.morning.wskn.cn.gov.cn.wskn.cn http://www.morning.rwpfb.cn.gov.cn.rwpfb.cn http://www.morning.jsdntd.com.gov.cn.jsdntd.com http://www.morning.rzjfn.cn.gov.cn.rzjfn.cn http://www.morning.ykswq.cn.gov.cn.ykswq.cn http://www.morning.zbkdm.cn.gov.cn.zbkdm.cn http://www.morning.rwmft.cn.gov.cn.rwmft.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.jyknk.cn.gov.cn.jyknk.cn http://www.morning.qqklk.cn.gov.cn.qqklk.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.alive-8.com.gov.cn.alive-8.com http://www.morning.dpmkn.cn.gov.cn.dpmkn.cn http://www.morning.bqmhm.cn.gov.cn.bqmhm.cn http://www.morning.qwbtr.cn.gov.cn.qwbtr.cn http://www.morning.rmfwh.cn.gov.cn.rmfwh.cn http://www.morning.ztfzm.cn.gov.cn.ztfzm.cn http://www.morning.kllzy.com.gov.cn.kllzy.com http://www.morning.mjyrg.cn.gov.cn.mjyrg.cn http://www.morning.zkrzb.cn.gov.cn.zkrzb.cn
