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中有无符合。这个思路并没有进行下去,虽然…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
离线语音识别方案分析
随着人工智能技术的不断发展,语音识别技术也得到了广泛的应用,从智能家居到车载系统,语音识别正在改变我们与设备的交互方式。尤其是离线语音识别,由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力,广…...
DAY 45 超大力王爱学Python
来自超大力王的友情提示:在用tensordoard的时候一定一定要用绝对位置,例如:tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾: tensorboard的发展历史和原理tens…...
