学习记录: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);}}// 返回堆中剩下的石头的重量,如果没有石头则返回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;否则返回堆顶元素的值。
相关文章:
学习记录:js算法(六十四):最后一块石头的重量
文章目录 最后一块石头的重量思路一思路二 最后一块石头的重量 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果如…...
单片机探秘:从理论到应用
单片机探秘:从理论到应用 在这个科技飞速发展的时代,单片机的应用如同一颗璀璨的星星,照亮了我们生活的方方面面。今天,让我们一同深入探讨单片机的原理与应用,揭开这个技术领域的神秘面纱。 1. 单片机概述 1.1 什么…...
options妙用
options妙用 设置默认浏览器为 Chrome options(browser “chrome”) 再次尝试运行 igsva() res <- igsva() 加载 BiocManager library(BiocManager) 设置超时时间 options(timeout 3600) 安装包 BiocManager::install(c(“org.Hs.eg.db”, “org.Mm.eg.db”)) …...
UE5 圆周运动、贝塞尔曲线运动、贝塞尔曲线点
圆周运动 贝塞尔曲线路径运动 蓝图函数库创建贝塞尔曲线点 // Fill out your copyright notice in the Description page of Project Settings.#pragma once#include "CoreMinimal.h" #include "Kismet/BlueprintFunctionLibrary.h" #include "MyB…...
线程局部存储(TLS)
很多时候,我们可能想存储一些线程的私有数据,属于线程的私有变量有局部变量,函数的参数,假如我们要在线程中存储全局变量,多个线程访问都对这个变量有自己的一个副本。 一、隐式实现 __thread int a; //linux __dec…...
JavaSE——集合7:Set接口实现类—TreeSet
目录 一、TreeSet基本介绍 二、TreeSet核心方法 三、TreeSet排序方法 四、TreeSet源码解析 1.无参构造时,底层是创建TreeMap对象 2.有参构造时,底层也创建TreeMap对象 3.执行add方法 4.执行put方法 一、TreeSet基本介绍 TreeSet是 Java 集合框架…...
【idea技巧篇】idea的类注释和方法注释模版自定义设置
这块idea技巧虽然常用,谁没事会经常修改模版设置呢,一般是搭建开发环境的时候或者开发规范要求等设置一次就行了。用的虽然少,但几乎每次搭建环境都会用到,这里记录下并分享设置的过程已经发现的更高级的一些使用技巧。 注释模版…...
【Kubernetes① 基础】一、容器基础
目录 一、进程二、隔离与限制三、容器镜像总结参考书籍 一、进程 容器技术的兴起源于PaaS技术(平台即服务)的普及;Docker公司发布的Docker项目具有里程碑式的意义;Docker项目通过“容器镜像”解决了应用打包这个根本性难题(CloudFoundry)。 容器本身的价…...
计算机网络第1章(概述)万字笔记详细版
1.1、计算机网络在信息时代的作用 计算机网络已由一种通信基础设施发展成为一种重要的信息服务基础设施计算机网络已经像水,电,煤气这些基础设施一样,成为我们生活中不可或缺的一部分 我国互联网发展状况 中国互联网络信息中心CNNIC 1.2、…...
每日一练算法题(堆串的基本操作StrReplace(S, T, V))
6-2 堆串的基本操作StrReplace(S, T, V) 编写算法,实现堆串的基本操作StrReplace(S, T, V)。 初始条件: 串S, T和 V 均已存在,且 V 是非空串。 操作结果: 用V替换主串S中出现的所有与(模式串)T相等的不重叠的子串。输入格式: 第一行:S 第二行&#…...
IRP默认最小流程
IRP是Windows内核中的一种非常重要的数据结构。上层应用程序与底层驱动程序通信时,应用程序会发出I/O请求,操作系统将相应的I/O请求转换成相应的IRP,不同的IRP会根据类型被分派到不同的派遣例程中进行处理。 irp相当于R3下的消息,…...
【全网最全】AI产品经理面试高频100题答案解析
详细的目录如下,需要的小伙伴可以详细看一下~ 第一章:机器学习和深度学习的关系 第二章:机器学习7大经典算法 算法一:K近邻算法【分类算法】 1.1 KNN 算法的实现原理 1.2 KNN应用场景举例:预测候选人能不能拿到 O…...
VLLM实现大模型服务的部署
文章目录 安装离线推理适配openAI-API的API服务使用python命令行部署使用docker部署调用启动成功的API 安装 # (Recommended) Create a new conda environment. conda create -n myenv python3.9 -y conda activate myenv# Install vLLM with CUDA 12.1. pip install vllm -i …...
Java 基数排序
基数排序(Radix Sort)是一种非比较型整数排序算法,通常用于对数字进行排序。它按照数字的每一位(从最低有效位到最高有效位或从最高有效位到最低有效位)进行排序,每次使用一个稳定的排序算法(如…...
红帽发送邮件操作
一.将/mnt挂在至/run/media mount /dev/sr0 /mnt 二.查看下载时间 ll /etc/yum.repos.d/ 三.下载安装包 dnf install s-nail -y 四.配置邮件服务 在最下面一行输入######################### 接着输入邮件 set from18013844913163.com set smtpsmtp.163.com set smt…...
学习记录:js算法(六十一):添加与搜索单词 - 数据结构设计
文章目录 添加与搜索单词 - 数据结构设计思路一思路二 添加与搜索单词 - 数据结构设计 请你设计一个数据结构,支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary : ● WordDictionary() 初始化词典对象 ● voi…...
Jetpack-ObservableField实现双向绑定
ObservableField是Android Data Binding库中的一个类,用于实现双向绑定。双向绑定意味着当数据模型中的数据发生变化时,UI会自动更新;同时,当用户在UI上进行操作时,数据模型也会相应地更新。 1.在你的项目中添加Data …...
STARnak, LTR 模型笔记
未完成. 1. 简述 CIKM 23 的一篇论文, 任务为 Learning To Rank, 输入为 候选集合, 输出为 有序列表, 用于 top-n 推荐场景. 思考: 它是要替代 ctr 预估么?它跟 mind 这种召回, 有啥大的不一样么? 2. 网络结构 u u u: 将用户(或 query) 记为 u H q d X , d Y , . . . H…...
【数据结构】:破译排序算法--数字世界的秩序密码(二)
文章目录 前言一.比较排序算法1.Bubble Sort冒泡排序1.1.冒泡排序原理1.2.冒泡排序过程1.3.代码实现1.4.复杂度和稳定性 2.Quick Sort快速排序2.1递归快速排序2.1.1.递归快速排序原理2.1.2.递归快速排序过程2.1.3.代码实现 2.2.非递归快速排序2.2.1.非递归快速排序原理2.2.2.非…...
2024年《生成式ai大模型》都学什么内容呢?
近期大家都在关注的2024 2024年10月25日 — 2024年10月29日 在成都举办的第八期《新质技术之生成式AI、大模型、多模态技术开发与应用研修班》都学什么内容呢?下面我们来看看: 1.了解AIGC发展现状与核心技术。 2.掌握Transformer核心开发技术。 3.掌握…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
