树形 DP:树的直径
leetCode 104.二叉树的最大深度104. 二叉树的最大深度 - 力扣(LeetCode)

class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr) return 0;int lDepth = maxDepth(root->left);int rDepth = maxDepth(root->right);return max(lDepth,rDepth)+1;}
};
leetCode 543.二叉树的直径 543. 二叉树的直径 - 力扣(LeetCode)
换个角度看直径:从一个叶子出发向上,在某个节点“拐弯”,向下到达另一个叶子,得到了由两条链拼起来的路径。(也可能只有一条链)

算法:遍历二叉树,在计算最长链的同时,顺带把直径算出来
- 在当前节点“拐弯”的直径长度 = 左子树的最长链 + 右子树的最长链 + 2
- 返回给父节点的是以当前节点为根的子树的最长链 = max(左子树的最长链,右子树的最长链)+1
class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int ans=0;function<int(TreeNode*)>dfs =[&](TreeNode* node) -> int {if(node == nullptr) return -1;// 下面+1后,对于叶子节点就刚好是 0int left = dfs(node->left);int right = dfs(node->right);ans = max(ans,left+right+2);return max(left,right)+1; //当前子树最大链长};dfs(root);return ans;}
};
leetCode 124.二叉树中的最大路径和 124. 二叉树中的最大路径和 - 力扣(LeetCode)

算法:遍历二叉树,在计算最大链和的同时,顺带更新答案的最大值
- 在当前节点 "拐弯" 的最大路径和 = 左子树最大链和 + 右子树最大链和 + 当前节点值
- 返回给父节点的是max(左子树最大链和,右子树最大链和)+当前节点值。如果这个值是负数,则返回 0
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:ans = -infdef dfs(node):if node is None:return 0l_val = dfs(node.left)r_val = dfs(node.right)nonlocal ansans = max(ans,l_val+r_val+node.val)return max(max(l_val,r_val) + node.val,0)dfs(root)return ans
2246.相邻字符不同的最长路径(1245.树的直径)2246. 相邻字符不同的最长路径 - 力扣(LeetCode)


class Solution {
public:int longestPath(vector<int>& parent, string s) {int n = parent.size();vector<vector<int>> g(n);for(int i=1;i<n;i++) {g[parent[i]].push_back(i);}int ans = 0;function<int(int)> dfs = [&](int x) -> int {int maxLen = 0;for (int y : g[x]) {int len = dfs(y) + 1;if (s[y] != s[x]) {ans = max(ans, maxLen + len);maxLen = max(maxLen, len);}}return maxLen;};dfs(0);return ans+1;}
};// -1 0 0 1 1 2
// 0 1 2 3 4 5// 0:[1,2]
// 1:[3,4]
// 2:[5]
推荐文章和参考视频:
树形 DP:树的直径【基础算法精讲 23】_哔哩哔哩_bilibili
543. 二叉树的直径 https://leetcode.cn/problems/diameter-of-binary-tree/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-taqma/
124. 二叉树中的最大路径和 https://leetcode.cn/problems/binary-tree-maximum-path-sum/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-n9s91/
2246. 相邻字符不同的最长路径 https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/solution/by-endlesscheng-92fw/
相关文章:
树形 DP:树的直径
leetCode 104.二叉树的最大深度104. 二叉树的最大深度 - 力扣(LeetCode) class Solution { public:int maxDepth(TreeNode* root) {if(root nullptr) return 0;int lDepth maxDepth(root->left);int rDepth maxDepth(root->right);return max(l…...
【Python百宝箱】第三维度的魔法:探索Python游戏世界
Python在游戏开发中的魔力 前言 游戏开发一直是计算机科学中最引人入胜和具有挑战性的领域之一。随着技术的不断进步,开发者们寻找着更快、更灵活的工具来实现他们的创意。在这个探索的过程中,Python以其简洁、易学和强大的特性成为了游戏开发的热门选…...
3ds Max 电脑配置建议 | 建模+渲染选专业显卡or游戏显卡?
使用3ds Max进行建模和渲染时,选择合适的电脑配置非常重要。比如在硬件选择上,究竟选购游戏显卡还是专业显卡呢?本文将为你详细介绍游戏显卡和专业显卡的区别,并提供配置建议,助你作出明智的决策。 &#…...
水淹七军(递归,又是递归)
北大2023级最强新生问我的,最后他的问题说是重写了一遍就解决了 乐死了,有的时候根本看不出源代码漏了哪里 我的思路是: 一个数组记录本次放水所经过的格子,经过的不再递归 一个数组记录地图上各地点的高度 一个数组记录地图…...
Stable Video Diffusion重磅发布,快来看看哪些功能
本周,有关 OpenAI 宫斗的报道占据了Ai圈版面的主导地位,吃够了奥特曼的大瓜。我们来看看Stability AI刚发布的Stable Video Diffusion,这是一种通过对现有图像进行动画处理来生成视频的 AI 模型。基于 Stability 现有的Stable Diffusion文本到…...
城市NOA到来时刻,车企密集上车NVIDIA
作者 |张祥威 编辑 |德新 基于双NVIDIA DRIVE Orin实现城市NOA,已是今天国内汽车行业的主流做法。 这款芯片获得广泛的市场认同,用时仅一年多。去年3月, NVIDIA DRIVE Orin正式投产,此后从造车新势力一路来到更多自主品牌的车内&…...
Linux后台运行Python的py文件,如何使ssh工具退出后仍能运行
常规运行 python3 mysqlbak.py ssh工具退出后,或ctrlc中断后,程序将不在运行 后台运行 nohup python3 mysqlbak.py > mysqlbak.log & > mysqlbak.log为可选项,输出日志到指定文件,如果不写,输出日志到nohup…...
Excel中出现“#NAME?”怎么办?(文本原因)
excel 单元格出现 #NAME? 错误的原因有二: 函数公式输入不对导致 #NAME? 错误。 在单元格中字符串的前面加了号,如下图中的--GoJG7sEe6RqgTnlUcitA,本身我们想要的是--GoJG7sEe6RqgTnlUcitA,但因为某些不当的操作在前面加了号&…...
superset 后端增加注册接口
好烦啊-- :< 1.先定义modes: superset\superset\models\user.py # Licensed to the Apache Software Foundation (ASF) under one # or more contributor license agreements. See the NOTICE file # distributed with this work for additional information…...
利用 React 和 Bootstrap 进行强大的前端开发
文章目录 介绍React 和 Bootstrap设置环境使用 Bootstrap 创建 React 组件React-Bootstrap 组件结论 介绍 创建响应式、交互式和外观引人入胜的 Web 界面是现代前端开发人员的基本技能。幸运的是,借助 React 和 Bootstrap 等工具的出现,制作这些 UI 变得…...
深度学习之基于Pytorch照片图像转漫画风格网络系统
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 以下是一个基本的设计介绍: 数据准备:收集足够的真实照片和漫画图像,用于训练模…...
解决No Feign Client for loadBalancing defined,修改Maven依赖
Spring微服务报错: java.lang.IllegalStateException:FactoryBean threw exception on object creation; nested exception is java.lang.IllegalStateException: No Feign Client for loadBalancing defined. Did you forget to include spring-cloud-starter-netf…...
友思特分享 | Neuro-T:零代码自动深度学习训练平台
来源:友思特 智能感知 友思特分享 | Neuro-T:零代码自动深度学习训练平台 欢迎关注虹科,为您提供最新资讯! 工业自动化、智能化浪潮涌进,视觉技术在其中扮演了至关重要的角色。在汽车、制造业、医药、芯片、食品等行业…...
基于动量的梯度下降
丹尼尔林肯 (Daniel Lincoln)在Unsplash上拍摄的照片 一、说明 基于动量的梯度下降是一种梯度下降优化算法变体,它在更新规则中添加了动量项。动量项计算为过去梯度的移动平均值,过去梯度的权重由称为 Beta 的超参数控制。 这有助于解决与普通梯度下降相…...
ELK+kafka+filebeat企业内部日志分析系统
1、组件介绍 1、Elasticsearch: 是一个基于Lucene的搜索服务器。提供搜集、分析、存储数据三大功能。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。Elasticsearch是用Java开发的,并作为Apache许可条款下的开放源码发布…...
MyBatis-Plus: 简化你的MyBatis应用
MyBatis-Plus: 简化你的MyBatis应用 在Java开发中,MyBatis一直是一个受欢迎的持久层框架,提供了灵活的数据访问方式。然而,MyBatis的使用往往涉及许多样板代码,这在一定程度上增加了开发的复杂性。这里,MyBatis-Plus&…...
在 go 的项目中使用验证器
1:使用validate 包验证: 安装包: go get github.com/go-playground/validator/v10 package controllerimport ("fmt""github.com/gin-gonic/gin""github.com/go-playground/validator/v10""net/http&quo…...
Handler系列-sendMessage和post的区别
sendMessage和post基本一样,区别在于post的Runnable会被赋值给Message的callback,在最后调用dispatchMessage的时候,callback会被触发执行。 1.sendMessage 调用sendMessageDelayed发送消息 public class Handler {public final boolean s…...
java中 自动装箱与拆箱,基本数据类型,java堆与栈,面向对象与面向过程
文章目录 自动装箱与拆箱基本数据类型与包装类的区别(int 和 Integer 有什么区别)应用场景的区别: 堆和栈的区别重点来说一下堆和栈:那么堆和栈是怎么联系起来的呢? 堆与栈的区别 很明显:延伸:关于Integer…...
C语言第二十八弹--输入一个非负整数,返回组成它的数字之和
C语言求输入一个非负整数,返回组成它的数字之和 方法一、递归法 思路:设计一个初始条件,通过递归获取非负整数的个位,不断接近递归条件即可。 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h>int DigitSum(int n) {…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
