当前位置: 首页 > news >正文

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
  • 如果已经建立过 旧节点 和 新节点 的映射,则直接返回新节点。
  • 如果没有建立 旧节点 和 新节点 的映射,则需要构建新节点,分为以下三步:
    1. 创建新节点:给新节点的 val 属性赋值。
    2. 保存 旧节点 和 新节点 的映射。
    3. 给新节点的 neighbors 属性赋值:构建新节点之间的 neighbor 关系。

注意:构建新节点的第二、三步不能调换顺序。因为本节点的 neighborneighbor 是本节点,这两个节点之间会 互相获取对方的新节点,而 要返回本节点的新节点就需要先获取对方节点的新节点,从而进入死循环。

代码

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 环境下&#xff0c;Qt Creator 是一个流行的集成开发环境&#xff08;IDE&#xff09;&#xff0c;用于开发 Qt 项目。下面是一些常用的快捷键和操作技巧&#xff0c;帮助你更高效地使用 Qt Creator 进行项目开发和管理&#xff1a; 在 macOS 中&#xff0c;Cmd 键 四…...

【C# WInForm】将TextBox从输入框设置为文本框

1.需求情形&#xff1a; textbox作为最常用的控件之一&#xff0c;通常是用来输入文本信息或者显示文字&#xff0c;但是如果要在界面中显示大段文本&#xff0c;一个带有边框、可选中的文本样式似乎不合适。像这样&#xff1a; 我需要的是这段文字不仅能跨行&#xff0c;而且…...

minio 服务docker配置

用minio docker配置了一个服务&#xff0c;分享链接始终是127.0.01开始的&#xff0c; 改成docker的host的ip则提示签名不匹配&#xff0c; 好在这个文件主要是用来下载的&#xff0c;所以可以通过设置bucket的匿名访问权限来实现下载&#xff1b; 这样不需要后面的地址参数就…...

开源模型应用落地-LangChain高阶-智能体探究-自定义agent(五)

一、前言 大模型具有非常强大的功能,可以解答疑问、撰写报告和文档、总结内容、进行翻译等各种日常工作任务。然而,大模型还可以应用于更多的场景,发挥出更强大的作用。 通过智能体,我们可以实现许多有价值的事情,比如:在日常生活中,我们能借助智能体实现智能家居的自动化…...

16_网络IPC4-数据传输

send() 用于流式套接字 向SOCKET发送数据 。 Socket 只是通信节点&#xff0c;通信之前需要连接&#xff0c;即发送端发送之前 需要知道对端的地址&#xff0c;才能找到对端的socket节点&#xff0c;才能发送成功。而接收端不同&#xff0c;接收函数 如 recv () 不需要一定知道…...

怎样做好仓库管理工作?如何利用仓库管理系统进行有效管理?

我前前后后跑遍了十几家仓储设备公司&#xff0c;跟那些制造业的朋友们聊了个痛快&#xff0c;从他们那儿学到了不少仓库管理的实践方法。 回来自己整理了一套仓库管理更高效的实用方法&#xff0c;现在就来跟大家伙儿聊聊仓库管理中那些常见问题&#xff0c;以及我是怎么琢磨…...

PHP-显示所有错误信息

1 需求 2 接口 3 示例 要在 PHP 中显示所有错误信息&#xff0c;你可以通过修改 php.ini 配置文件或在你的 PHP 脚本中设置错误报告级别来实现。以下是两种常见的方法&#xff1a; 方法一&#xff1a;修改 php.ini 配置文件 找到你的 php.ini 文件。这个文件的位置取决于你的 P…...

js修改hash的方法

关键&#xff1a; window.onhashchange (event) > {// do something }hash变化包括 js修改hash手动修改url的hash浏览器前进、后退 js修改hash: location.href "#user";在vue-router等路由组件中如何实现history模式呢&#xff1f; 关键函数&#xff1a;hi…...

机械学习—零基础学习日志(高数10——函数图形)

零基础为了学人工智能&#xff0c;真的开始复习高数 函数图像&#xff0c;开始新的学习&#xff01;本次就多做一做题目&#xff01; 第一题&#xff1a; 这个解法是有点不太懂的了。以后再多研究一下。再出一道题目。 张宇老师&#xff0c;比较多提示了大家&#xff0c;一定…...

Godot游戏制作 03世界构建1.0版

在game场景&#xff0c;删除StaticBody2D节点&#xff0c;添加TileMap节点 添加TileSet图块集 添加TileSet源 拖动图片到图块&#xff0c;自动创建图块 使用橡皮擦擦除。取消橡皮擦后按住Shift创建大型图块。 进入选择模式&#xff0c;TileMap选择绘制&#xff0c;选中图块后在…...

MySql性能调优05-[sql实战演练]

sql实战演练 行列转换行列式转换第一题【列转行】第二题【列转行】 having的使用找到表中&#xff0c;名字重复的项有数据表employee&#xff0c;包含如下字段id、name、department、age&#xff0c;编写SQL&#xff0c;找到不与其他人同龄的年纪最大的员工的年龄有数据表emplo…...

go-kratos 学习笔记(1) 安装

简介&#xff1a; Kratos 一套轻量级 Go 微服务框架&#xff0c;包含大量微服务相关框架及工具。 使用步骤&#xff1a; 安装cli工具 go install github.com/go-kratos/kratos/cmd/kratos/v2latest 创建项目 通过 kratos 命令创建项目模板 # 国内拉取失败可使用gitee源 krat…...

蚂蚁集团推出EchoMimic:能通过音频和面部标志生成逼真的肖像动画视频

蚂蚁集团最近推出了一项名为EchoMimic的新技术。能通过音频和面部标志生成逼真的肖像动画视频&#xff0c;让你的声音和面部动作被完美复制到视频中&#xff0c;效果自然如照镜子。 EchoMimic不仅可以单独使用音频或面部标志点生成肖像视频&#xff0c;也可以将两者结合&#…...

量化机器人对市场趋势的反应速度

量化机器人对市场趋势的反应速度在当前金融市场中具有重要意义。随着算法和大数据技术的发展&#xff0c;量化机器人通过先进的计算能力和实时数据分析&#xff0c;能够迅速捕捉市场变化&#xff0c;做出及时的交易决策。这种快速反应能力&#xff0c;不仅提高了交易效率&#…...

深入指南:VitePress 如何自定义样式

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...

逃离的日常:自闭症孩子的课堂小插曲

自闭症孩子在课堂上突然离座&#xff0c;是一个复杂而多面的现象&#xff0c;背后往往隐藏着他们独特的情感表达与需求未被充分理解的现状。自闭症&#xff0c;作为一种神经发展性障碍&#xff0c;影响着孩子的社交互动、沟通能力及行为模式。在课堂上&#xff0c;这些差异可能…...

LLM模型与实践之基于MindSpore的GPT2文本摘要

前言 安装环境 !pip install tokenizers0.15.0 -i https://pypi.tuna.tsinghua.edu.cn/simple # 该案例在 mindnlp 0.3.1 版本完成适配&#xff0c;如果发现案例跑不通&#xff0c;可以指定mindnlp版本&#xff0c;执行!pip install mindnlp0.3.1 !pip install mindnlp 数据加…...

【Android】使用视图绑定ViewBinding来代替findViewById

文章目录 介绍作用用法开启ViewBinding功能自动生成绑定类在Activity中使用访问视图控件 区别 介绍 ViewBinding 是 Android 开发中的一个功能&#xff0c;它简化了访问视图的过程&#xff0c;避免了使用 findViewById 的繁琐步骤。它通过生成与布局文件相对应的绑定类&#xf…...

字符的统计——423、657、551、696、467、535

423. 从英文中重建数字 最初思路 首先要有一个指针&#xff0c;对于3/4/5为一组地跳跃。起初想的是后瞻性&#xff0c;如果符合0-9任意&#xff0c;则更换index、跳跃。此时写了一个函数&#xff0c;用来判断s的截取段和0-9中有无符合。这个思路并没有进行下去&#xff0c;虽然…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...