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中有无符合。这个思路并没有进行下去,虽然…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
