LeetCode 129, 133, 136
文章目录
- 129. 求根节点到叶节点数字之和
- 题目链接
- 标签
- 思路
- 代码
- 133. 克隆图
- 题目链接
- 标签
- 思路
- 代码
- 136. 只出现一次的数字
- 题目链接
- 标签
- 思路
- 代码
129. 求根节点到叶节点数字之和
题目链接
129. 求根节点到叶节点数字之和
标签
树 深度优先搜索 二叉树
思路
由于本题需要 从 根节点 遍历到 叶子节点(无子节点的节点叫做叶子节点),所以可以使用 深度优先搜索 的思想:每次遍历一个节点就计算 当前的路径(从根节点到当前节点)所表示的数字,然后将其传递给它的两棵子树,对 在两棵子树求得的所有路径之和 求和 并 返回。
像这样从 根节点 向 叶子节点 遍历,如果遍历到叶子节点,则返回 从 根节点 到 此叶子节点 的路径所表示的数字。此外,可能会遇到一个当前节点为 null 的情况,此时返回 0 作为路径即可。
代码
class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}// curr 是当前遍历的节点,currNum 是从根节点到 curr 的路径所表示的数字private int dfs(TreeNode curr, int currNum) {if (curr == null) { // 如果 curr 为 nullreturn 0; // 则返回 0}int num = currNum * 10 + curr.val; // 计算从根节点到 curr 的路径所表示的数字if (curr.left == null && curr.right == null) { // 如果到叶子节点return num; // 则返回从根节点到这个叶子节点的路径所表示的数字}return dfs(curr.left, num) // 遍历左子树,求左子树中的所有路径之和+ dfs(curr.right, num); // 遍历右子树,求右子树的所有路径之和}
}
133. 克隆图
题目链接
133. 克隆图
标签
深度优先搜索 广度优先搜索 图 哈希表
思路
本题和 LeetCode 138. 随机链表的复制 类似,使用的方法完全一样,都是 建立旧节点与新节点的映射,不过与之不同的一点是:138 题中链表的结构没有这么复杂,而本题将基础链表中的 next 指针变成了一个 neighbors 指针集合,这就意味着本题无法像 138 题一样遍历链表来为新节点的属性赋值,而需要使用别的遍历方式——深度优先搜索(本方式复用了 cloneGraph() 方法,求旧节点所对应的新节点):
- 如果旧节点为
null,则返回null。 - 如果已经建立过 旧节点 和 新节点 的映射,则直接返回新节点。
- 如果没有建立 旧节点 和 新节点 的映射,则需要构建新节点,分为以下三步:
- 创建新节点:给新节点的
val属性赋值。 - 保存 旧节点 和 新节点 的映射。
- 给新节点的
neighbors属性赋值:构建新节点之间的neighbor关系。
- 创建新节点:给新节点的
注意:构建新节点的第二、三步不能调换顺序。因为本节点的 neighbor 的 neighbor 是本节点,这两个节点之间会 互相获取对方的新节点,而 要返回本节点的新节点就需要先获取对方节点的新节点,从而进入死循环。
代码
class Solution {// 给定一个旧节点,返回其对应的新节点public Node cloneGraph(Node oldNode) {if (oldNode == null) { // 如果 旧节点 为 nullreturn null; // 则返回 null}if (mapper.containsKey(oldNode)) { // 如果已经建立过 旧节点 和 新节点 的映射return mapper.get(oldNode); // 则直接返回 旧节点 对应的 新节点}// 构建 新节点,给新节点的 neighbors 链表初始化指定的大小,避免 后续扩容 浪费时间Node newNode = new Node(oldNode.val, new ArrayList<>(oldNode.neighbors.size()));mapper.put(oldNode, newNode); // 先保存 旧节点 和 新节点 的映射for (Node neighbor : oldNode.neighbors) { // 然后再构建新节点之间的 neighbor 关系// 按照顺序寻找 新节点 对应的 新 neighbornewNode.neighbors.add(cloneGraph(neighbor));}return newNode; // 返回新节点}// 映射 旧节点 和 新节点 的映射,key 为 旧节点,value 为 新节点private Map<Node, Node> mapper = new HashMap<>();
}
136. 只出现一次的数字
题目链接
136. 只出现一次的数字
标签
位运算 数组
思路
异或的定义是:相同为假,不同为假。例如对于两个二进制数 0101, 1001,它们异或的结果为 0101 ^ 1001 = 1100。
本题考查了一个位运算的知识:对两个数使用 异或 操作得到的结果如下:
- 如果两个数相等,则结果为
0。这是因为两个数相等代表其二进制数相等,而相同为假,所以异或的结果全是0,从而两个相等的数的异或结果为0。 - 如果是
0 ^ 某个数,则结果为某个数。这种情况举个例子更好理解:例如对于0000, 1101,它们异或的结果为1101,恰好与这个数相等。 - 对于其他情况,结果通常没有具体意义。
多个数进行异或操作 就是 复合了多个 两数异或 的结果,例如 0011 ^ 1100 ^ 0011 = 0 ^ 1100 = 1100。
所以可以遍历数组,对所有数使用异或操作,出现两次的数都抵消成 0 了,出现一次的数最终和 0 进行异或操作,得到它本身。
代码
class Solution {public int singleNumber(int[] nums) {int res = nums[0];for (int i = 1; i < nums.length; i++) {res ^= nums[i];}return res;}
}
相关文章:
LeetCode 129, 133, 136
文章目录 129. 求根节点到叶节点数字之和题目链接标签思路代码 133. 克隆图题目链接标签思路代码 136. 只出现一次的数字题目链接标签思路代码 129. 求根节点到叶节点数字之和 题目链接 129. 求根节点到叶节点数字之和 标签 树 深度优先搜索 二叉树 思路 由于本题需要 从…...
macOS 环境Qt Creator 快捷键
在 macOS 环境下,Qt Creator 是一个流行的集成开发环境(IDE),用于开发 Qt 项目。下面是一些常用的快捷键和操作技巧,帮助你更高效地使用 Qt Creator 进行项目开发和管理: 在 macOS 中,Cmd 键 四…...
【C# WInForm】将TextBox从输入框设置为文本框
1.需求情形: textbox作为最常用的控件之一,通常是用来输入文本信息或者显示文字,但是如果要在界面中显示大段文本,一个带有边框、可选中的文本样式似乎不合适。像这样: 我需要的是这段文字不仅能跨行,而且…...
minio 服务docker配置
用minio docker配置了一个服务,分享链接始终是127.0.01开始的, 改成docker的host的ip则提示签名不匹配, 好在这个文件主要是用来下载的,所以可以通过设置bucket的匿名访问权限来实现下载; 这样不需要后面的地址参数就…...
开源模型应用落地-LangChain高阶-智能体探究-自定义agent(五)
一、前言 大模型具有非常强大的功能,可以解答疑问、撰写报告和文档、总结内容、进行翻译等各种日常工作任务。然而,大模型还可以应用于更多的场景,发挥出更强大的作用。 通过智能体,我们可以实现许多有价值的事情,比如:在日常生活中,我们能借助智能体实现智能家居的自动化…...
16_网络IPC4-数据传输
send() 用于流式套接字 向SOCKET发送数据 。 Socket 只是通信节点,通信之前需要连接,即发送端发送之前 需要知道对端的地址,才能找到对端的socket节点,才能发送成功。而接收端不同,接收函数 如 recv () 不需要一定知道…...
怎样做好仓库管理工作?如何利用仓库管理系统进行有效管理?
我前前后后跑遍了十几家仓储设备公司,跟那些制造业的朋友们聊了个痛快,从他们那儿学到了不少仓库管理的实践方法。 回来自己整理了一套仓库管理更高效的实用方法,现在就来跟大家伙儿聊聊仓库管理中那些常见问题,以及我是怎么琢磨…...
PHP-显示所有错误信息
1 需求 2 接口 3 示例 要在 PHP 中显示所有错误信息,你可以通过修改 php.ini 配置文件或在你的 PHP 脚本中设置错误报告级别来实现。以下是两种常见的方法: 方法一:修改 php.ini 配置文件 找到你的 php.ini 文件。这个文件的位置取决于你的 P…...
js修改hash的方法
关键: window.onhashchange (event) > {// do something }hash变化包括 js修改hash手动修改url的hash浏览器前进、后退 js修改hash: location.href "#user";在vue-router等路由组件中如何实现history模式呢? 关键函数:hi…...
机械学习—零基础学习日志(高数10——函数图形)
零基础为了学人工智能,真的开始复习高数 函数图像,开始新的学习!本次就多做一做题目! 第一题: 这个解法是有点不太懂的了。以后再多研究一下。再出一道题目。 张宇老师,比较多提示了大家,一定…...
Godot游戏制作 03世界构建1.0版
在game场景,删除StaticBody2D节点,添加TileMap节点 添加TileSet图块集 添加TileSet源 拖动图片到图块,自动创建图块 使用橡皮擦擦除。取消橡皮擦后按住Shift创建大型图块。 进入选择模式,TileMap选择绘制,选中图块后在…...
MySql性能调优05-[sql实战演练]
sql实战演练 行列转换行列式转换第一题【列转行】第二题【列转行】 having的使用找到表中,名字重复的项有数据表employee,包含如下字段id、name、department、age,编写SQL,找到不与其他人同龄的年纪最大的员工的年龄有数据表emplo…...
go-kratos 学习笔记(1) 安装
简介: Kratos 一套轻量级 Go 微服务框架,包含大量微服务相关框架及工具。 使用步骤: 安装cli工具 go install github.com/go-kratos/kratos/cmd/kratos/v2latest 创建项目 通过 kratos 命令创建项目模板 # 国内拉取失败可使用gitee源 krat…...
蚂蚁集团推出EchoMimic:能通过音频和面部标志生成逼真的肖像动画视频
蚂蚁集团最近推出了一项名为EchoMimic的新技术。能通过音频和面部标志生成逼真的肖像动画视频,让你的声音和面部动作被完美复制到视频中,效果自然如照镜子。 EchoMimic不仅可以单独使用音频或面部标志点生成肖像视频,也可以将两者结合&#…...
量化机器人对市场趋势的反应速度
量化机器人对市场趋势的反应速度在当前金融市场中具有重要意义。随着算法和大数据技术的发展,量化机器人通过先进的计算能力和实时数据分析,能够迅速捕捉市场变化,做出及时的交易决策。这种快速反应能力,不仅提高了交易效率&#…...
深入指南:VitePress 如何自定义样式
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...
逃离的日常:自闭症孩子的课堂小插曲
自闭症孩子在课堂上突然离座,是一个复杂而多面的现象,背后往往隐藏着他们独特的情感表达与需求未被充分理解的现状。自闭症,作为一种神经发展性障碍,影响着孩子的社交互动、沟通能力及行为模式。在课堂上,这些差异可能…...
LLM模型与实践之基于MindSpore的GPT2文本摘要
前言 安装环境 !pip install tokenizers0.15.0 -i https://pypi.tuna.tsinghua.edu.cn/simple # 该案例在 mindnlp 0.3.1 版本完成适配,如果发现案例跑不通,可以指定mindnlp版本,执行!pip install mindnlp0.3.1 !pip install mindnlp 数据加…...
【Android】使用视图绑定ViewBinding来代替findViewById
文章目录 介绍作用用法开启ViewBinding功能自动生成绑定类在Activity中使用访问视图控件 区别 介绍 ViewBinding 是 Android 开发中的一个功能,它简化了访问视图的过程,避免了使用 findViewById 的繁琐步骤。它通过生成与布局文件相对应的绑定类…...
字符的统计——423、657、551、696、467、535
423. 从英文中重建数字 最初思路 首先要有一个指针,对于3/4/5为一组地跳跃。起初想的是后瞻性,如果符合0-9任意,则更换index、跳跃。此时写了一个函数,用来判断s的截取段和0-9中有无符合。这个思路并没有进行下去,虽然…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
