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

力扣题目汇总分析 利用树形DP解决问题

树里 任意两个节点之间的问题。而不是根节点到叶子节点的问题或者是父节点到子节点的问题。通通一个套路,即利用543的解题思路。

543.二叉树的直径

分析

明确:二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。两个节点之间的最长路径是他们之间的边数。
任意两个节点之间的路径,这个路必然会在一个根节点拐弯(拐弯之后可能继续往下,也可能不继续往下)
所以我们可以遍历每个节点,求出在这个节点拐弯的最长路径,显然,某节点处拐弯的最长路径=左子树的深度+右子树的深度(根节点深度为1)。
利用dfs遍历节点,递归得到子树的深度,原问题与子问题的关系是:子树的深度=max(左子树的深度,右子树的深度)+1。递归终止条件是,当前要遍历的节点是空节点,则返回深度为0。在递归函数中,得到左右子树的深度后,即可以求出当前节点处拐弯的最长路径,定义一个全局变量mm存最长路径,比较当前节点处拐弯的最长路径和全局变量,看看是否要替换。
所以在dfs遍历二叉树的基础上,返回值是当前树的深度,在递归函数体中取得左右子树的深度,算出当前节点处拐弯的最长路径与全局变量mm进行比较。

代码实现
class Solution {int maxDiameter=0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return maxDiameter;}public int dfs(TreeNode root){if (root==null) return 0;//在当前拐弯的最长直径路径=左子树深度+右子树深度int l=dfs(root.left);int r=dfs(root.right);maxDiameter=l+r>maxDiameter?l+r:maxDiameter;return l>r?l+1:r+1;}
}

class Solution {int maxDiameter=0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return maxDiameter;}public int dfs(TreeNode root){if (root==null) return -1;//在当前拐弯的最长直径路径=左子树最长链长度+1+右子树最长链长度+1int l=dfs(root.left)+1;int r=dfs(root.right)+1;maxDiameter=l+r>maxDiameter?l+r:maxDiameter;return l>r?l:r;}
}

687.最长同值路径

分析

这题也是求任意两个节点之间的最长路径,但是加了个条件,路径上的每个节点的值一样。
本来,当前节点处拐弯的最长路径=左子树最长同值路径长度+1+右子树最长同值路径长度+1。
但是,如果左节点的值和当前节点的值不一样,就不考虑左子树(也就相当于让 左子树最长同值路径长度=0),右节点同样操作。

代码实现
class Solution {int mm=0;public int longestUnivaluePath(TreeNode root) {dfs(root);return mm;}public int dfs(TreeNode root){if (root==null) return -1;int l=dfs(root.left)+1;if (root.left!=null && root.left.val!=root.val){l=0;}int r=dfs(root.right)+1;if (root.right!=null && root.right.val!=root.val){r=0;}mm=l+r>mm?l+r:mm;return l>r?l:r;}
}

124.二叉树中的最大路径和

分析

找一条节点序列,序列里每个节点值之和最大。序列里至少有一个节点,序列的起始节点任意。
问题本质和前面的两个题都一样。只是这次找最大的路径上的节点值之和。
当前节点处拐弯的路径上节点之和的最大值=左子树最大路径之和+右子树最大路径之和+当前节点值。
和找同值路径类似,本题中,如果左子树的最大路径之和带来的是负增益,就不考虑(也就是让 左子树最大路径之和=0)。右子树同样操作。

代码实现
class Solution {int mm=-2147483648;public int maxPathSum(TreeNode root) {dfs(root);return mm;}public int dfs(TreeNode root){if (root==null) return 0;int l=dfs(root.left);l=l>0?l:0;int r=dfs(root.right);r=r>0?r:0;mm=l+r+root.val>mm?l+r+root.val:mm;return l>r?l+root.val:r+root.val;}
}

2246.相邻字符不同的最长路径

分析

这题要求找一条最长路径,这个路径上任意一对相邻节点都没有分配到相同字符(最长相邻不同值路径),与前面有所不同的是,这题针对一般的树,而不是二叉树。

所以我们需要取出当前节点的子节点列表,循环遍历,递归处理每个子节点,递归完一个子节点后,如果这个子节点的值和当前节点的值相同,则不考虑(即不参与更新maxNum,mm的操作,当然也可以把值置为0,但是置为0后参与了后续比较操作,属于多余操作)。

当前节点处拐弯的最长不同值路径=子节点中的最大不同值路径长度+1+子节点中不同值路径长度第二大的值+1。

定义一个变量maxNum,存已经遍历的子节点里最大的不同值路径长度,定义一个变量mm,当前节点处拐弯的最长不同值路径的长度,mm每次与 新遍历子节点的最大的不同值路径长度+maxNum进行比较,看看是否替换。如果不可以替换,说明次大的值还是在已经遍历的节点中出现。(通过这种方式,无需创建一个列表存每个子节点的最大不同值路径长度)

代码实现
class Solution {int mm=0;Map<Integer,List<Integer>> map=new HashMap<>();String ss;public int longestPath(int[] parent, String s) {ss=s;for (int i=0;i<parent.length;i++){List<Integer> l=map.getOrDefault(parent[i],new ArrayList<Integer>());l.add(i);map.put(parent[i],l);}dfs(0);return mm+1;}public int dfs(int i){int maxNum=0;if (!map.containsKey(i)){return 0;}for (int c:map.get(i)){int num = dfs(c)+1;if (ss.charAt(c)!=ss.charAt(i)){mm = maxNum+num>mm?maxNum+num:mm;maxNum = num>maxNum?num:maxNum;}}return maxNum;}
}

相关文章:

力扣题目汇总分析 利用树形DP解决问题

树里 任意两个节点之间的问题。而不是根节点到叶子节点的问题或者是父节点到子节点的问题。通通一个套路&#xff0c;即利用543的解题思路。 543.二叉树的直径 分析 明确&#xff1a;二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。两个节点之间的最长路径是他们之…...

GO语言核心30讲 实战与应用 (第二部分)

原站地址&#xff1a;Go语言核心36讲_Golang_Go语言-极客时间 一、sync.WaitGroup和sync.Once 1. sync.WaitGroup 比通道更加适合实现一对多的 goroutine 协作流程。 2. WaitGroup类型有三个指针方法&#xff1a;Wait、Add和Done&#xff0c;以及内部有一个计数器。 (1) Wa…...

linux设置挂载指定的usb,自动挂载

一、设置指定的USB 在Linux系统中&#xff0c;如果您只想让系统挂载特定的USB设备&#xff0c;而忽略其他的USB设备&#xff0c;可以通过创建自定义的udev规则来实现。以下是设置系统只能挂载指定USB设备的基本步骤&#xff1a; 确定USB设备的属性&#xff1a; 首先&#xff0…...

简站WordPress主题

简站WordPress主题是一种专为建立网站而设计的WordPress模板&#xff0c;它旨在简化网站建设过程&#xff0c;使得用户能够更容易地创建和管理自己的网站。简站WordPress主题具有以下特点&#xff1a; 易用性&#xff1a;简站WordPress主题被设计为简单易用&#xff0c;适合各…...

is和==的关系

Python中is和的关系 is判断两个变量是不是指的是同一个内存地址&#xff0c;也就是通过id()函数判断 判断两个变量的值是不是相同 a [1, 2, 3, 4] b [1, 2, 3, 4] print(id(a)) # 2298268712768 print(id(b)) # 2298269716992 print(a is b) # False print(a b) # Tr…...

璩静是为了薅百度羊毛

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 百度副总裁璩静离职了&#xff0c;网传她的年薪是1500万&#xff0c;而璩静在4月24日注册了一个文化传媒公司&#xff0c;大家都认为璩静是在为离职做准备。但松松我认为不是。 我认为&#xff1a;璩静成立新公司是…...

Element ui input 限制只能输入数字,且只能有两位小数

<el-form-item label"整体进度&#xff1a;" prop"number"> <el-input v-model"formInline.number" input"handleInput" placeholder"百分比" clearable></el-input>% </el-form-item&g…...

吃掉 N 个橘子的最少天数

代码实现&#xff1a; 方法一&#xff1a;递归——超时 #define min(a, b) ((a) > (b) ? (b) : (a))int minDays(int n) {if (n 1 || n 2) {return n;}if (n % 3 0) {if (n % 2 0) {return min(min(minDays(n - 1), minDays(n / 2)), minDays(n - 2 * (n / 3))) 1;} e…...

JavaScript 之 toString()方法详解

一、前言&#xff1a; ​ 在 JavaScript 中&#xff0c;toString() 方法是很多数据类型内置的方法&#xff0c;它被用于将特定的数据类型转换为字符串。但是在不同的数据类型中的作用并非完全相同&#xff0c;下面就来详细讲解一下 toString() 方法在各种数据类型中的使用和作用…...

PPMP_char3

PMPP char3 – Multidimensional grids and data ​ 五一过后&#xff0c;有些工作要赶&#xff0c;抽出时间更新一下。这一章基本都熟练掌握&#xff0c;在做习题过程中有一些思考。这里涉及到了一点点GEMM&#xff08;矩阵乘&#xff09;&#xff0c;GEMM有太多可深挖的了&a…...

VulkanSDK Demos vkcube 编译失败

操作系统: Windows 11 23H2 Vulkan 版本: 1.3.2.280.0 Visual Studio 版本: 2022 在VulkanSDK/Demos目录下存在一个demo solution,其中包含两个project, vkcube和vkcubepp,两个分别为C语言和C写的示例程序, 但是直接编译这两个project时会编译失败,报了以下错误: fatal err…...

(二)Jetpack Compose 布局模型

前文回顾 &#xff08;一&#xff09;Jetpack Compose 从入门到会写-CSDN博客 首先让我们回顾一下上一篇文章中里提到过几个问题&#xff1a; ComposeView的层级关系&#xff0c;互相嵌套存在的问题&#xff1f; 为什么Compose可以实现只测量一次&#xff1f; ComposeView和…...

【Oracle impdp导入dmp文件(windows)】

Oracle impdp导入dmp文件&#xff08;windows&#xff09; 1、连接数据库2、创建与导出的模式相同名称的用户WIRELESS2&#xff0c;并赋予权限3、创建directory 的物理目录f:\radio\dmp&#xff0c;并把.dmp文件放进去4、连接新用户WIRELESS25、创建表空间的物理目录F:\radio\t…...

代数结构:5、格与布尔代数

16.1 偏序与格 偏序集&#xff1a;设P是集合&#xff0c;P上的二元关系“≤”满足以下三个条件&#xff0c;则称“≤”是P上的偏序关系&#xff08;或部分序关系&#xff09; &#xff08;1&#xff09;自反性&#xff1a;a≤a&#xff0c;∀a∈P&#xff1b; &#xff08;2…...

如何使用DEEPL免费翻译PDF

如何使用DEEPL免费翻译PDF 安装DEEPL取消PDF限制 安装DEEPL 安装教程比较多&#xff0c;这里不重复。 把英文pdf拖进去&#xff0c;点翻译&#xff0c;在下面的框中有已经翻译完毕的文档。 但是存在两个问题 问题1&#xff1a;这些文档是加密的。 问题2&#xff1a;带有DeepL标…...

Spring-全面详解

Spring&#xff0c;就像是软件开发界的一个超级英雄&#xff0c;它让编写Java程序变得更简单、更灵活。想象一下&#xff0c;如果你要盖一栋大楼&#xff0c;Spring就是那个提供各种工具、框架和最佳实践的建筑大师&#xff0c;帮助你高效、优雅地搭建起整个项目。 Spring是啥&…...

QT自适应界面 处理高DPI 缩放比界面乱问题

1.pro文件添加 必须添加要不找不到 QT版本需要 5。4 以上才支持 QT widgets 2.main界面提前处理 // 1. 全局缩放使能QApplication::setAttribute(Qt::AA_EnableHighDpiScaling, true);// 2. 适配非整数倍缩放QGuiApplication::setHighDpiScaleFactorRoundingPolicy(Qt::High…...

序列到序列模型在语言识别Speech Applications中的应用 Transformer应用于TTS Transformer应用于ASR 端到端RNN

序列到序列模型在语言识别Speech Applications中的应用 A Comparative Study on Transformer vs RNN in Speech Applications 序列到序列(Seq2Seq)模型在语音识别(Speech Applications)中有重要的应用。虽然Seq2Seq模型最初是为了解决自然语言处理中的序列生成问题而设计的…...

【Linux】- Linux环境变量[8]

目录 环境变量 $符号 自行设置环境变量 环境变量 环境变量是操作系统&#xff08;Windows、Linux、Mac&#xff09;在运行的时候&#xff0c;记录的一些关键性信息&#xff0c;用以辅助系统运行。在Linux系统中执行&#xff1a;env命令即可查看当前系统中记录的环境变量。 …...

前端笔记-day04

文章目录 01-后代选择器02-子代选择器03-并集选择器04-交集选择器05-伪类选择器06-拓展-超链接伪类07-CSS特性-继承性08-CSS特性-层叠性09-CSS特性-优先级11-Emmet写法12-背景图13-背景图平铺方式14-背景图位置15-背景图缩放16-背景图固定17-background属性18-显示模式19-显示模…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...