LeetCode 637, 67, 399
文章目录
- 637. 二叉树的层平均值
- 题目链接
- 标签
- 思路
- 代码
- 67. 二进制求和
- 题目链接
- 标签
- 思路
- 代码
- 399. 除法求值
- 题目链接
- 标签
- 思路
- 导入
- value 属性
- find() 方法
- union() 方法
- query() 方法
- 代码
637. 二叉树的层平均值
题目链接
637. 二叉树的层平均值
标签
树 深度优先搜索 广度优先搜索 二叉树
思路
本题考查了二叉树的 层序遍历,层序遍历的思想是 广度优先搜索,广度优先搜索需要使用 队列,操作如下:
- 创建一个队列,用于保存每层节点。
- 先将根节点放入队列,代表遍历第一层。
- 只要队列不为空,就进行如下操作:
- 获取本层节点的个数。
- 遍历本层的所有节点,遍历操作如下:
- 取出当前节点。
- 如果当前节点的左子节点不为
null
,则将其放到队列中,等待下一层节点的遍历。 - 如果当前节点的右子节点不为
null
,则将其放到队列中,等待下一层节点的遍历。 - 针对当前节点进行某种操作:使用一个变量统计本层节点之和。
- 针对本层节点进行某种 统计 操作:计算本层节点的平均值,并将其放到结果链表中。
- 遍历完整个二叉树,返回结果。
代码
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>(); // 存储结果(每层节点的平均值)的链表LinkedList<TreeNode> queue = new LinkedList<>(); // 保存每层节点的队列queue.offer(root); // 先将根节点放入队列,即遍历第一层while (!queue.isEmpty()) { // 直到队列为空,才退出循环double sum = 0; // 计算本层节点的和int size = queue.size(); // 获取本层节点的数量for (int i = 0; i < size; i++) { // 遍历本层所有节点TreeNode curr = queue.poll(); // 取出 当前节点TreeNode left = curr.left; // 获取当前节点的 左子节点if (left != null) { // 如果 左子节点 不为 nullqueue.offer(left); // 则将其放到队列中,等待下一层遍历}TreeNode right = curr.right; // 获取当前节点的 右子节点if (right != null) { // 如果 右子节点 不为 nullqueue.offer(right); // 则将其放到队列中,等待下一层遍历}sum += curr.val; // 求和}res.add(sum / size); // 计算平均值}return res;}
}
67. 二进制求和
题目链接
67. 二进制求和
标签
位运算 数学 字符串 模拟
思路
本题是一道 模拟题,如果是十进制,则本题就是 高精度 问题,以下写出一种模版,只需要改变 base
进制,就可以使用不同的进制进行计算。
可以想一想小学一年级学的 列竖式计算两数之和,高精度的解决方案就是它:
- 将两个数的个位对齐,写出来。
- 对每一位,有如下操作:
- 将两个数的相同位加在一起。此外,还要加上 进位
carry
,进位是通过 满n
进一 得到的,这里的n
就是进制。如果有一个数的位数不够,则认为这个数的这一位为0
。 - 对于加起来的和,如果它大于进制,则进一,并将剩余的数(和 对 进制 取余)写在结果的这一位上;否则直接将和写在结果的这一位上。
- 将两个数的相同位加在一起。此外,还要加上 进位
- 最后,看是否还应该进位,如果需要,则再添加一位
1
。
由于 题目传入的字符串和要求返回的字符串都是从高位到低位的,而 在计算时是从低位到高位的,所以要注意在计算时颠倒字符串,并将计算结果反转之后再返回。
代码
class Solution {public String addBinary(String a, String b) {final int base = 2; // 进制,本题为 二进制StringBuilder builder = new StringBuilder(); // 拼接数字的拼接器char[] aC = a.toCharArray(), bC = b.toCharArray();int aLen = aC.length, bLen = bC.length;int len = Math.max(aLen, bLen); // 获取较长字符串的长度int carry = 0; // 是否要进一,如果要进一,则为 1;否则为 0for (int i = 0; i < len; i++) {// 注意 aC/bC[i] 是字符,需要通过 减去 '0' 来将其转化为 数字int operand1 = i < aLen ? (aC[aLen - i - 1] - '0') : 0;int operand2 = i < bLen ? (bC[bLen - i - 1] - '0') : 0;int sum = operand1 + operand2 + carry;carry = sum / base; // 查看是否需要进一sum %= base; // 获取剩余的数builder.append(sum);}if (carry > 0) { // 如果还需要进位builder.append(1); // 则再添加一位 1}builder.reverse(); // 先将结果反转return builder.toString(); // 再返回}
}
399. 除法求值
题目链接
399. 除法求值
标签
深度优先搜索 广度优先搜索 并查集 图 数组 字符串 最短路
思路
导入
本题不算中等题,理应为困难题,主要与 并查集、数学 有关,操作十分复杂。可以先看看 990. 等式方程的可满足性,990 题是本题的简单版本,尽量理解 990 题中的并查集的使用。此外,希望大家看一看并查集的 路径压缩,这在本题中很重要。
value 属性
如果能够理解 990 题,那么离解决本题就不远了。本题的并查集中每个节点都比 990 题多了一个值 value
,其保存了 本节点 与 其父节点 的比值,即有 v a l u e [ i ] = i p a r e n t [ i ] value[i] = \frac{i}{parent[i]} value[i]=parent[i]i 请记住这点,在 find()
和 union()
中很重要。注意:其中的 i, parent[i]
不是索引,没有实际意义,只是充当有逻辑意义的占位符,这个比值是从 values
数组中获得的。
find() 方法
在 find()
时需要 压缩路径,因为这样可以避免一些计算。例如下面的并查集,如果想要查询 x
与 rootX
的比值,就必须计算两次;但如果直接让 x
指向 rootX
,这时只需要获取 value[x]
即可。具体的操作为先保存父节点,再递归获取根节点,最后更新本节点的 value
,从 本节点与父节点的比值 变为 本节点与根节点的比值。等式如下: x r o o t X = x y ∗ y r o o t X \frac{x}{rootX} = \frac{x}{y} * \frac{y}{rootX} rootXx=yx∗rootXy ,即 value[x] = value[x] * value[y]
,其中的 y
为未变更之前 x
的父节点。
union() 方法
在 union()
方法中,不仅要传递 x, y
的索引,还要传递 value = x / y
的值。先获取 x
和 y
的根节点(获取根节点的时候就让 x, y
指向其根节点 rootX, rootY
了,如下图),如果根节点一样,则直接返回;否则就需要让 rootX
指向 rootY
,并更新 rootX
的 value
。等式如下: r o o t X r o o t Y = y r o o t Y x y r o o t X x \frac{rootX}{rootY} = \frac{y}{rootY} \frac{x}{y} \frac{rootX}{x} rootYrootX=rootYyyxxrootX ,即有 value[rootX] = value[y] * value / value[x]
。
本题还有一个比较麻烦的点:等式中的变量不一定只有一个小写字母。所以需要建立 等式中的变量(以下称作 操作元)与 其在并查集中的索引 的映射,具体请看代码。
query() 方法
由于需要查询某两个操作元之间的比值,还需要在并查集中实现一个方法 query()
,如果两个操作元对应的索引在并查集中不连通,则返回 -1
;否则返回比值 value[x] / value[y]
。等式如下(如果 x, y
连通,则其根节点相同,假设为 root
): x y = x r o o t r o o t y \frac{x}{y} =\frac{x}{root} \frac{root}{y} yx=rootxyroot ,即 x / y = value[x] / value[y]
。
代码
class Solution {public double[] calcEquation(List<List<String>> equations,double[] values, List<List<String>> queries) {// 先初始化并查集init(equations, values);// 再进行查询int queriesSize = queries.size();double[] res = new double[queriesSize];for (int i = 0; i < queriesSize; i++) {List<String> query = queries.get(i);String operand1 = query.get(0); // 操作元1String operand2 = query.get(1); // 操作元2Integer idx1 = indexMapper.get(operand1); // 操作元1的索引Integer idx2 = indexMapper.get(operand2); // 操作元2的索引if (idx1 == null || idx2 == null) { // 如果两个操作元有一个找不到res[i] = -1; // 则本此查询返回 -1} else { // 否则查询 value[idx1] / value[idx2] 的结果res[i] = uf.query(idx1, idx2);}}return res;}private UnionFind uf; // 并查集private Map<String, Integer> indexMapper; // 操作元 与 其在并查集中的索引 的映射// 初始化并查集private void init(List<List<String>> equations, double[] values) {int equationsSize = equations.size(); // 获取等式的数量uf = new UnionFind(2 * equationsSize); // 创建一个等式数量二倍大小的并查集indexMapper = new HashMap<>(2 * equationsSize);int idx = 0; // 操作元在并查集中的索引for (int i = 0; i < equationsSize; i++) {// 取出每个等式,建立 操作元 与 其在并查集中的索引 的关系List<String> equation = equations.get(i);String operand1 = equation.get(0); // 操作元1String operand2 = equation.get(1); // 操作元2if (!indexMapper.containsKey(operand1)) { // 如果 索引映射 中不存在 操作元indexMapper.put(operand1, idx++); // 则为其建立映射}if (!indexMapper.containsKey(operand2)) { // 如果 索引映射 中不存在 操作元indexMapper.put(operand2, idx++); // 则为其建立映射}uf.union(indexMapper.get(operand1), indexMapper.get(operand2), values[i]);}}private static class UnionFind {private final int[] parent; // parent[i] 表示 第 i 个元素的父节点private final double[] value; // value[i] 表示 第 i 个元素 / 其父节点 的商// 初始化并查集public UnionFind(int size) {parent = new int[size];value = new double[size];for (int i = 0; i < size; i++) {parent[i] = i; // 初始时,每个元素的父节点都是 自己value[i] = 1; // 初始时,每个元素与自己的商都是 1}}// 查找 x 的根节点,使用了路径压缩public int find(int x) {if (x != parent[x]) { // 如果 x 不是根节点int temp = parent[x]; // 保存 x 的父节点parent[x] = find(parent[x]); // 寻找 x 的根节点value[x] *= value[temp]; // 给 本节点与父节点的商 乘 父节点与父节点的父节点的商}return parent[x]; // 否则返回 parent[x]}// 合并两个节点所在的集合public void union(int x, int y, double value) {int rootX = find(x); // x 的根节点int rootY = find(y); // y 的根节点if (rootX == rootY) {return;}parent[rootX] = rootY; // 让 x 的根节点 指向 y 的根节点,y 的根节点 成为 父节点value[rootX] = value[y] * value / value[x];}// 查询 value[x] / value[y] 的结果public double query(int x, int y) {if (find(x) == find(y)) { // 如果连通return value[x] / value[y]; // 则返回比值} else { // 否则不连通return -1; // 返回 -1}}}
}
相关文章:

LeetCode 637, 67, 399
文章目录 637. 二叉树的层平均值题目链接标签思路代码 67. 二进制求和题目链接标签思路代码 399. 除法求值题目链接标签思路导入value 属性find() 方法union() 方法query() 方法 代码 637. 二叉树的层平均值 题目链接 637. 二叉树的层平均值 标签 树 深度优先搜索 广度优先…...

如何压缩视频大小不改变画质?这5个视频压缩免费软件超好用!
如何压缩视频大小不改变画质?随着生活的水平逐步提高,视频流媒体服务越来越受欢迎。提供简短而引人注目的视频来展示您的产品或服务已成为一种出色的营销手段。然而,当您要准备导出最终视频时,可能会面临一个常见问题:…...

深入理解 Java 虚拟机第三版(周志明)
这次社招选的这本作为 JVM 资料查阅,记录一些重点 1. 虚拟机历史 Sun Classic VM :已退休 HotSpot VM:主流虚拟机,热点代码探测技术 Mobile / Embedded VM :移动端、嵌入式使用的虚拟机 2.2 运行时数据区域 程序计…...

算法 定长按组翻转链表
一、题目 已知一个链表的头部head,每k个结点为一组,按组翻转。要求返回翻转后的头部 k是一个正整数,它的值小于等于链表长度。如果节点总数不是k的整数倍,则剩余的结点保留原来的顺序。示例如下: (要求不…...

安装nfs和rpcbind设置linux服务器共享磁盘
1、安装nfs和rpcbind 1.1 检查服务器是否安装nfs和rpcbind,执行下命令,检查服务器是否安装过。 rpm -qa|grep nfs rpm -qa|grep rpcbind 说明服务器以安装了,如果没有就需要自己安装 2、安装nfs和rpcbind 将rpm安装包: libtirpc-…...

物联网在电力行业的应用
作者主页: 知孤云出岫 这里写目录标题 作者主页:物联网在电力行业的应用简介主要应用领域代码案例分析1. 智能电表数据采集和分析2. 设备监控和预测性维护3. 能耗管理和优化4. 电力负载预测5. 分布式能源管理6. 电动汽车充电管理7. 电网安全与故障检测 物联网在电力行业的应用…...
Java 代码规范if嵌套
在Java编程中,过度的if嵌套会使代码难以阅读和维护。为了遵循良好的代码规范,我们应尽量减少嵌套的深度。这通常可以通过重新组织代码或使用其他结构(如switch语句,或者将逻辑封装到单独的方法中)来实现。 以下是一个…...
ASPICE如何确保汽车软件产品质量的稳固基石
ASPICE通过一系列的方法和原则来保障汽车软件产品的质量,以下是其保障产品质量的几个关键方面: 制定明确的质量方针和目标: ASPICE要求组织制定明确的质量方针和目标,这些方针和目标与客户需求和预期相一致。 开发团队需要定义软…...

【深度学习】yolov8-seg分割训练,拼接图的分割复原
文章目录 项目背景造数据训练 项目背景 在日常开发中,经常会遇到一些图片是由多个图片拼接来的,如下图就是三个图片横向拼接来的。是否可以利用yolov8-seg模型来识别出这张图片的三张子图区域呢,这是文本要做的事情。 造数据 假设拼接方式有…...

Python升级打怪—Django入门
目录 一、Django简介 二、安装Django 三、创建Dajngo项目 (一) 创建项目 (二) 项目结构介绍 (三) 运行项目 (四) 结果 一、Django简介 Django是一个高级Python web框架,鼓励快速开发和干净、实用的设计。由经验丰富的开发人员构建,它解决了web开…...
leetcode面试题17.最大子矩阵
sooooooo long没刷题了,汗颜 题目链接:leetcode面试题17 1.题目 给定一个正整数、负整数和 0 组成的 N M 矩阵,编写代码找出元素总和最大的子矩阵。 返回一个数组 [r1, c1, r2, c2],其中 r1, c1 分别代表子矩阵左上角的行号和…...

计算机网络:构建联结的基础
目录 1. 网络拓扑结构 1.1 星型拓扑 1.2 环型拓扑 1.3 总线型拓扑 1.4 网状拓扑 2. 传输介质 2.1 双绞线 2.2 同轴电缆 2.3 光纤 2.4 无线电波 3. 协议栈模型 3.1 OSI模型 3.2 TCP/IP模型 4. 网络设备 4.1 交换机 4.2 路由器 4.3 网关 4.4 防火墙 5. IP地址…...

node和npm安装;electron、 electron-builder安装
1、node和npm安装 参考: https://blog.csdn.net/sw150811426/article/details/137147783 下载: https://nodejs.org/dist/v20.15.1/ 安装: 点击下载msi直接运行安装 安装完直接cmd打开可以,默认安装就已经添加了环境变量&…...
操作系统概念(黑皮书)阅读笔记
操作系统概念(黑皮书)阅读笔记 进程和内存管理部分章节 导论: 操作系统类似于政府,其本身不能实现任何有用功能,而是提供一个方便其他程序执行有用工作的环境 个人理解:os是government的作用࿰…...

matlab gui下的tcp client客户端编程框架
GUI界面 函数外定义全局变量 %全局变量 global TcpClient; %matlab作为tcpip客户端 建立连接 在“连接”按钮的回调函数下添加以下代码: global TcpClient;%全局变量 TcpClient tcpip(‘192.168.1.10’, 7, ‘NetworkRole’,‘client’); %连接到服务器地址和端…...
Matplotlib : Python 的绘图库
Matplotlib 是一个 Python 的绘图库,广泛用于生成各种静态、动态、交互式的图表。它基于 NumPy,一个用于科学计算的 Python 库。Matplotlib 可以用于生成出版质量级别的图表,并且提供了丰富的定制选项,以适应不同用户的需求。以下…...

数据编织 VS 数据仓库 VS 数据湖
目录 1. 什么是数据编织?2. 数据编织的工作原理3. 代码示例4. 数据编织的优势5. 应用场景6. 数据编织 vs 数据仓库6.1 数据存储方式6.2 数据更新和实时性6.3 灵活性和可扩展性6.4 查询性能6.5 数据治理和一致性6.6 适用场景6.7 代码示例比较 7. 数据编织 vs 数据湖7.1 数据存储…...
CSS(十一)——CSS分组和嵌套,尺寸(Dimension)
CSS 分组 和 嵌套 选择器 分组选择器 举个例子,多个标签有同一个样式,就可以不一个一个分开写,使用分组选择器 比如: h1 {color:green; } h2 {color:green; } p {color:green; } 就可以写为: h1,h2,p {color…...

必备神器!三款优秀远程控制电脑软件推荐
嘿,各位职场小伙伴们,今儿个咱们来聊聊个挺实用又带点“科技范儿”的话题——电脑远程控制那点事儿。作为刚踏入职场不久的新人,我深刻体会到,在这信息爆炸的时代,掌握几招远程操作的技能,简直就是给自个儿…...
关于正运动学解机器人手臂算法
机器人正运动学是机器人学的一个分支,研究机器人的运动和位置之间的关系。它通过解析机器人的结构和关节参数,以及给定的关节角度,来计算机器人的末端执行器的位置和姿态。 机器人正运动学算法通常使用DH(Denavit-Hartenberg&…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...