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

Every day a Leetcode

题目来源:2246. 相邻字符不同的最长路径

解法1:树形 DP

如果没有相邻节点的限制,那么本题求的就是树的直径上的点的个数,见于Leetcode543. 二叉树的直径。

考虑用树形 DP 求直径。

枚举子树 x 的所有子树 y,维护从 x 出发的最长路径 maxLen,那么可以更新答案为从 y 出发的最长路径加上 maxLen,再加上 1(边 x−>y),即合并从 x 出发的两条路径。递归结束时返回 maxLen。

对于本题的限制,我们可以在从子树 y 转移过来时,仅考虑从满足 s[y]≠s[x] 的子树 y 转移过来,所以对上述做法加个 if 判断就行了。

由于本题求的是点的个数,所以答案为最长路径的长度加 1。

代码:

/** @lc app=leetcode.cn id=2246 lang=cpp** [2246] 相邻字符不同的最长路径*/// @lc code=start
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); // 根节点是节点 0return ans + 1;}
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n),其中 n 是数组 parent 的长度。

空间复杂度:O(n),其中 n 是数组 parent 的长度。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/186295.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何让群晖Audio Station公开共享的本地音频公网可访问?

文章目录 1. 本教程使用环境&#xff1a;2. 制作音频分享链接3. 制作永久固定音频分享链接&#xff1a; 之前文章我详细介绍了如何在公网环境下使用pc和移动端访问群晖Audio Station&#xff1a; 公网访问群晖audiostation听歌 - cpolar 极点云 群晖套件不仅能读写本地文件&a…

Go基础知识全面总结

文章目录 go基本数据类型bool类型数值型字符字符串 数据类型的转换运算符和表达式1. 算数运算符2.关系运算符3. 逻辑运算符4. 位运算符5. 赋值运算符6. 其他运算符运算符优先级转义符 go基本数据类型 bool类型 布尔型的值只可以是常量 true 或者 false。⼀个简单的例⼦&#…

竞赛选题 深度学习猫狗分类 - python opencv cnn

文章目录 0 前言1 课题背景2 使用CNN进行猫狗分类3 数据集处理4 神经网络的编写5 Tensorflow计算图的构建6 模型的训练和测试7 预测效果8 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习猫狗分类 ** 该项目较为新颖&a…

Python基础教程之十六:Python multidict示例–将单个键映射到字典中的多个值

1.什么是multidict词典> 在python中&#xff0c;“ multidict ”一词用于指代字典&#xff0c;在字典中可以将单个键映射到多个值。例如 多重结构 multidictWithList {key1 : [1, 2, 3],key2 : [4, 5]}multidictWithSet {key1 : {1, 2, 3},key2 : {4, 5}}1. list如果要…

内核移植笔记 Cortex-M移植

常用寄存器 PRIMASK寄存器 为1位宽的中断屏蔽寄存器。在置位时&#xff0c;它会阻止不可屏蔽中断&#xff08;NMI&#xff09;和HardFault异常之外的所有异常&#xff08;包括中断&#xff09;。 实际上&#xff0c;它是将当前异常优先级提升为0&#xff0c;这也是可编程异常/…

uniapp使用vue3和ts开发小程序自定义tab栏,实现自定义凸出tabbar效果

要实现自定义的tabbar效果&#xff0c;可以使用自定义tab覆盖主tab来实现&#xff0c;当程序启动或者从后台显示在前台时隐藏自带的tab来实现。自定义一个tab组件&#xff0c;然后在里面实现自定义的逻辑。 组件中所使用的组件api可以看&#xff1a;Tabbar 底部导航栏 | uView…

Centos7下搭建H3C log服务器

rsyslogH3C 安装rsyslog服务器 关闭防火墙 systemctl stop firewalld && systemctl disable firewalld关闭selinux sed -i s/enforcing/disabled/ /etc/selinux/config && setenforce 0centos7服务器&#xff0c;通过yum安装rsyslog yum -y install rsysl…

【uniapp】六格验证码输入框实现

效果图 代码实现 <view><view class"tips">已发送验证码至<text class"tips-phone">{{ phoneNumber }}</text></view><view class"code-input-wrap"><input class"code-input" v-model"…

AI:75-基于生成对抗网络的虚拟现实场景增强

🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌在这个漫长的过程,中途遇到了不少问题,但是…

[量化投资-学习笔记008]Python+TDengine从零开始搭建量化分析平台-CCI和ATR

目录 1. 指标简介CCIATR 2. 程序编写题外话 1. 指标简介 将这两个指标放在一起&#xff0c;一方面是因为这两个指标都属于摆动指数&#xff0c;可以反应市场的活跃度。 另一方面是因为CCI和ATR与之前提到的EMA,MACD,布林带的三个指标的计算基础不同。之前的三个指标都是以收盘…

坐标系转换(仅作记载)

一.极坐标转换为普通坐标系 参考&#xff1a;极坐标方程与直角坐标方程的互化 - 知乎 (zhihu.com) 公式&#xff1a;&#xff08;无需考虑象限引起的正负问题&#xff09; 普通坐标系转换为极坐标系 参考&#xff1a; 极坐标怎么与直角坐标系相互转化&#xff1f; - 知乎 (zh…

Docker本地镜像发布到阿里云或私有库

本地镜像发布到阿里云流程 &#xff1a; 1.自己生成个要传的镜像 2.将本地镜像推送到阿里云: 阿里云开发者平台:开放云原生应用-云原生&#xff08;Cloud Native&#xff09;-云原生介绍 - 阿里云 2.1.创建仓库镜像&#xff1a; 2.1.1 选择控制台&#xff0c;进入容器镜像服…

如何在Linux上部署1Panel运维管理面板并远程访问内网进行操作

文章目录 前言1. Linux 安装1Panel2. 安装cpolar内网穿透3. 配置1Panel公网访问地址4. 公网远程访问1Panel管理界面5. 固定1Panel公网地址 前言 1Panel 是一个现代化、开源的 Linux 服务器运维管理面板。高效管理,通过 Web 端轻松管理 Linux 服务器&#xff0c;包括主机监控、…

广和通5G模组FM650助力阿里云打造无影魔方Pro

随着云基础设施的完善及云电脑体验的不断优化&#xff0c;越来越多的个人和企业选择无影云电脑进行办公。基于云原生的云网端技术架构&#xff0c;无影云电脑相比传统PC&#xff0c;具有弹性、安全、保障个人数据等产品优势。 10月31日&#xff0c;阿里云在杭州云栖大会上宣布…

RSA 2048位算法的主要参数N,E,P,Q,DP,DQ,Qinv,D分别是什么意思 哪个是通常所说的公钥与私钥 -安全行业基础篇5

非对称加密算法RSA 在RSA 2048位算法中&#xff0c;常见的参数N、E、P、Q、DP、DQ、Qinv和D代表以下含义&#xff1a; N&#xff08;Modulus&#xff09;&#xff1a;模数&#xff0c;是两个大素数P和Q的乘积。N的长度决定了RSA算法的安全性。 E&#xff08;Public Exponent&a…

原神游戏干货分享:探索璃月的宝箱秘密,提高游戏资源获取效率!

《原神》是一款备受玩家喜爱的开放世界冒险游戏&#xff0c;而在游戏中获取资源是提升角色实力的重要途径。在这篇实用干货分享中&#xff0c;我们将介绍一些探索璃月地区的宝箱秘密&#xff0c;帮助你提高游戏资源获取的效率。 首先&#xff0c;璃月地区的宝箱分为普通宝箱和精…

本地部署企业邮箱,让企业办公更安全高效

随着信息化时代的到来&#xff0c;企业邮箱几乎成了企业办公的标配&#xff0c;承载着企业业务往来和办公协同的重要职能。基于安全性、个性化需求、系统集成等方面的需要&#xff0c;许多企业选择本地部署企业邮箱&#xff0c;本地化部署不仅能有效保障企业信息安全的同时&…

家用工作站方案:ThinkBook 14 2023 版

本篇文章聊聊今年双十一&#xff0c;我新购置的家用工作站设备&#xff1a;ThinkBook 14 2023&#xff0c;一台五千元价位&#xff0c;没有显卡的笔记本。我为什么选择它&#xff0c;它又能做些什么。 写在前面 2021 年年中的时候&#xff0c;我写过一篇《廉价的家用工作站方…

React向组件内部动态传入带内容的结构--props

children props&#xff1a;通过组件标签体传入结构 <A><B>xxx</B> </A> {this.props.children}render props&#xff1a;通过组件标签属性传入结构&#xff0c;一般用render函数属性 <A render{data> <C data{data}></C>}></…