LeetCode:1483. 树节点的第 K 个祖先(倍增 Java)
目录
1483. 树节点的第 K 个祖先
题目描述:
实现代码与解析:
倍增
原理思路:
1483. 树节点的第 K 个祖先
题目描述:
给你一棵树,树上有 n
个节点,按从 0
到 n-1
编号。树以父节点数组的形式给出,其中 parent[i]
是节点 i
的父节点。树的根节点是编号为 0
的节点。
树节点的第 k
个祖先节点是从该节点到根节点路径上的第 k
个节点。
实现 TreeAncestor
类:
TreeAncestor(int n, int[] parent)
对树和父数组中的节点数初始化对象。getKthAncestor
(int node, int k)
返回节点node
的第k
个祖先节点。如果不存在这样的祖先节点,返回-1
。
示例 1:
输入: ["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"] [[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]输出: [null,1,0,-1]解释: TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);treeAncestor.getKthAncestor(3, 1); // 返回 1 ,它是 3 的父节点 treeAncestor.getKthAncestor(5, 2); // 返回 0 ,它是 5 的祖父节点 treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点
提示:
1 <= k <= n <= 5 * 104
parent[0] == -1
表示编号为0
的节点是根节点。- 对于所有的
0 < i < n
,0 <= parent[i] < n
总成立 0 <= node < n
- 至多查询
5 * 104
次
实现代码与解析:
倍增
class TreeAncestor {int M = 17;int[][] an;public TreeAncestor(int n, int[] parent) {an = new int[n][M];// 初始化for (int i = 0; i < n; i++) {Arrays.fill(an[i], -1);}for (int i = 0; i < n; i++) {an[i][0] = parent[i];}for (int j = 1; j < M; j++) {for (int i = 0; i < n; i++) {if (an[i][j - 1] != -1) {an[i][j] = an[an[i][j - 1]][j - 1];}}}}public int getKthAncestor(int node, int k) {for (int j = 0; j < M; j++) {if (((k >> j) & 1) != 0) {node = an[node][j];if (node == -1) return -1;}}return node;}
}
原理思路:
倍增 + dp。
dp数组含义:f[i][j] 表示第 i 个节点的 2^j 的祖先节点。
转移方程:2 ^ j =2^(j - 1) + 2^(j - 1) 也就是f[i][j] = f[ f[ i ][ j - 1 ] ] [ j - 1 ]。
将 k 二进制例如:13 = 1101 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0;
假设我们要找x的第13个祖节点,可以先向上找到最近的第8个节点(t),在找的 t 的最近的第4个祖宗节点...........直到找到目标节点。
用公式就是:x = f[x][3], x = f[x][2], x = f[x][1];
顺序无所谓,可以8,4,1也可以1, 4, 8。
相关文章:
LeetCode:1483. 树节点的第 K 个祖先(倍增 Java)
目录 1483. 树节点的第 K 个祖先 题目描述: 实现代码与解析: 倍增 原理思路: 1483. 树节点的第 K 个祖先 题目描述: 给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出&#…...
ConstraintLayout在复杂布局中,出现卡顿问题解决记录
ConstraintLayout在画界面的过程中,确实带来了不少的方便,随着使用的越来越多,也发现了一些问题,特此记录一下问题和解决方案。 在背景为图片,而背景图片宽度固定高度自适应的情况下,布局显示在图片固定位…...
责任链模式详解+代码案例
责任链设计模式 定义: 又名职责链模式,为了避免请求发送者与多个请求处理者耦合在一起,将所有请求的处理者通过前一对象记住其下一个对象的引用而连成一条链;当有请求发生时,可将请求沿着这条链传递,直到…...
如何让Webots支持C#语言开发的控制器
Webots支持C、C、Java、Python、Matlab这五种语言开发控制器,没有直接支持C#,但有个同事已经用C#写了大量的机器人控制代码,想在不把C#代码改写成C的情况下,直接用webots仿真,那就得想想办法。(不过,让Chat…...
如何将本地仓库放到远程仓库中
在我们仓库创建好之后,我们复制好ssh 接着我们需要使用git remote add<shortname><url>这个命令 shortname就是我们远程仓库的别名 接着使用git remote -v这个命令查看一下目前远程仓库的别名和地址 原本还有一个指令git branch -M main 指定分支的名…...
Jedis-事务
一,Jedis 我们要使用Java来操作Redis Jedis是Redis官方推荐的java连接工具。使用Java操作Redis的中间件。如果你要使用Java操作redis,那么一定要对jedis十分的熟悉 二,idea 连接jedis 1,导入jar包 <dependencies><depen…...
智慧安防监控EasyCVR视频调阅和设备录像回看无法自动播放的原因排查与解决
智慧安防监控EasyCVR视频管理平台能在复杂的网络环境中,将前端设备统一集中接入与汇聚管理。国标GB28181协议视频监控/视频汇聚EasyCVR平台可以提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联、磁盘阵列存储、视频集中存储、…...
百元不入耳蓝牙耳机哪个好?必入五款高性价比产品
喜欢听歌的朋友都会遇到一个常见问题,长时间戴耳机容易导致耳朵不适,甚至疼痛难忍。这种情况下,要是不听音乐反而感到不舒服,真是让人苦恼,仿佛音乐与耳机无法和谐共存。但是,难道就没有一款既舒适又让人心…...
android APP monkey 测试
monkey 测试 一、电脑ADB安装及使用详解1、什么是 Monkey 测试2、什么是ADB3、ADB的作用4、安装前提条件5、ADB下载6、ADB安装与配置 二、连接安卓手机检查是否连接上安卓手机windows端安装ADB驱动 三、 monkey测试操作指令演示指令APP包名查看方式测试效果 一、电脑ADB安装及使…...
IMBoy缓存系统深度解析:为何选择depcache而非ETS或Redis
在IMBoy即时通讯平台的开发过程中,我们面临了选择最佳缓存系统的关键技术决策。经过细致的考量,我们选择了depcache作为IMBoy的核心缓存机制。本文将阐述IMBoy缓存系统的选型理由,并对比分析depcache与纯ETS方案及Redis方案的不同优势。 1. …...
Twitter Api查询用户粉丝列表
如果大家为了获取实现方式代码的话可能要让大家失望了,这边文章主要是为了节省大家开发时间,少点坑。https://api.twitter.com/2/users/:id/followers ,这个接口很熟悉吧,他是推特提供的获取用户关注者(粉丝࿰…...
深入理解计算机系统 家庭作业 2.96
题目出的很不好,感觉没有标准. #include <stdio.h>typedef unsigned float_bits;int float_f2i(float_bits f) {unsigned sign f >> (31);unsigned exp (f >> 23) & 0xff;unsigned frac f & 0x7fffff;unsigned add (frac & 0x3) 0x3;unsig…...
主函数if __name__ == ‘__main__‘:
在Python中,主函数通常指的是脚本的入口点,也就是当你直接运行一个Python脚本时,会首先执行的函数。在大多数Python脚本中,主函数并不是通过main()这样的函数名来定义的,而是通过检查脚本是作为模块导入还是被直接运行…...
34.Python从入门到精通—Python3 正则表达式检索和替换
34.从入门到精通:Python3 正则表达式检索和替换 repl 参数是一个函数 正则表达式对象 正则表达式修饰符 - 可选标志 正则表达式模式* 正则表达式实例 检索和替换repl 参数是一个函数正则表达式对象正则表达式修饰符 - 可选标志正则表达式模式*正则表达式实例 检索和…...
springboot 反射调用ServiceImpl时报错:java.lang.NullPointerExceptio、,mapper为null【解决方法】
springboot 反射调用ServiceImpl时报错:java.lang.NullPointerException、mapper为null【解决方法】 问题描述问题分析解决方案创建SpringBootBeanUtil编写调用方法 executeMethod调用 总结 问题描述 在使用Spring Boot时,我们希望能够通过反射动态调用…...
内网安全之域内密码喷洒
域内密码喷洒一般和域内用户名枚举一起使用,可以在无域内凭据的情况下,通过枚举出域内存在的用户名,进而对域内存在的用户名进行密码喷洒,以此来获得域内有效凭据。 在Kerberos协议认证的AS-REQ阶段,请求包cname对应的…...
何为HTTP状态码?一文清楚基本概念。
在客户端与服务器之间的信息传输过程中,我们可以将其比喻为客户与快递员之间的包裹传递。那么服务器是如何通知客户端,操作是成功还是失败?或者有其他的一些情况呢?(就像客户可以查询快递的状态) 而这背后…...
SV学习笔记(七)
文章目录 类型转换写在前面动态转换子类句柄赋值于父类句柄父类句柄转换为子类句柄 虚方法写在前面非虚函数的调用虚函数的调用虚方法的建议为什么使用虚方法 对象拷贝写在前面赋值和拷贝总结 回调函数写在前面实例完成回调函数功能需要三步: 参数化类写在前面实现一…...
Windows SDK(五)按钮静态文本与编辑框控件
我们首先应该知道,所谓按钮静态文本等等控件都是窗口,他们都是隶属于父窗口下的子窗口,所 以在创建控件前,我们要首先创建一个父窗口,此处我们直接使用Windows桌面程序创建时,程 序自动为我们创建的一个窗…...
基于SSM框架实现的在线心理评测与咨询系统(技术栈 spring+springmvc+mybatis+jsp+jquery+css)
一、项目简介 本项目是一套基于SSM框架实现的在线心理评测与咨询系统,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试&am…...
GD32F470_ DS18B20温度传感器模块移植
DS18B20温度传感器 DS18B20数字温度传感器提供9位至12位精度的温度测量,并具有非易失性用户可编程上下触发点报警功能。DS18B20通过单总线通信,根据定义,只需要一条数据线(和地线)即可与单片机通信。此外,DS18B20可以直接从数据线…...
【JAVASE】带你了解instanceof和equals的魅力
✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:再无B~U~G-CSDN博客 1.instanceof instanceof 是 Java 的保留关键字。它的作用是测试…...
【Linux】进程控制详解
目录 前言 进程创建 认识fork 写时拷贝 再谈fork 进程终止 进程退出码 用代码来终止进程 常见的进程终止的方式 exit _exit 进程等待 进程等待的必要性 进程等待的方式 wait waitpid 详解status参数 详解option参数 前言 本文适合有一点基础的人看的&#…...
Mysql 高性能的sql优化方案和建议
优化MySQL的性能是一项复杂而关键的任务,它可以通过多种方式来实现。下面是一些SQL优化的方案和建议: 索引优化: 确保经常查询的列都有索引。但不要过度索引,因为它可能会增加写入操作的开销。使用组合索引来覆盖多个查询条件。…...
鸿蒙实战开发:【实现应用悬浮窗】
如果你要做的是系统级别的悬浮窗,就需要判断是否具备悬浮窗权限。然而这又不是一个标准的动态权限,你需要兼容各种奇葩机型的悬浮窗权限判断。 fun checkPermission(context: Context): Boolean if (Build.VERSION.SDK_INT < Build.VERSION_CODES.M)…...
应用开发:python解析斗鱼弹幕
解决问题 互动弹幕,关注提问 ,ai回答 技术 python playwright 调用接口 https://github.com/broven/DouYudanmu/blob/master/douyu.py 演示 放弃 这个根本不是研究方向 定位错误 你浪费下午时间,定位错误 这个跟本不是你的方向。 4个小时看斗…...
【面试经典150 | 动态规划】交错字符串
文章目录 写在前面Tag题目来源解题思路方法一:动态规划 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行…...
设计模式(17):中介者模式
核心: 如果一个系统中对象之间的联系呈现网状结构,对象之间存在大量多对多关系,导致关系及其复杂,这些对象称为“同事对象”。我们可以引入一个中介者对象,使各个同事对象只跟中介者对象打交道,将复杂的网…...
echart 折线图或散点图当横坐标为小数位时,若想显示整数该如何处理?
如图当前是这样的: 横坐标刻度目前是小数位,如果直接将小数位取整则会失去精度,所以我们要做的是刻度即是整数,又能显示小数位对应的数值; 思路就是直接手动设置刻度:设置xAxis的min,max,splitNumber,同时不…...
一套C#自主版权+应用案例的手麻系统源码
手术麻醉信息管理系统源码,自主版权应用案例的手麻系统源码 手术麻醉信息管理系统包含了患者从预约申请手术到术前、术中、术后的流程控制。手术麻醉信息管理系统主要是由监护设备数据采集子系统和麻醉临床系统两个子部分组成。包括从手术申请到手术分配,…...
嘉兴市做外贸网站/宁波seo外包服务商
本文介绍了微信小程序仿微信运动步数排行(交互),分享给大家,也给自己留个笔记,废话不多说了,具体如下:效果图如下:wxml:{{item.name}}{{item.steps}}wxss:/* pages/leftSwiperDel/index.wxss */…...
怎么自制软件/优化关键词软件
#include<signal.h>int sigemptyset(sigset_t *set); 信号集设置为空int sigfillset(sigset_t *set);int sigfilladdset(sigset_t *set,int signo); 加入到信号集int sigfilldelset(sigset_t *set,int signo);删除信号集int sigismember(sigset_t *set int signo);查询是…...
网站建设 北京/如何快速搭建网站
BigDecimal 解决double精度丢失问题(加减乘除)参考文章: (1)BigDecimal 解决double精度丢失问题(加减乘除) (2)https://www.cnblogs.com/ChiRain/p/6211412.html &…...
网站建设项目风险管理的主要内容/网络营销的方法有哪些?举例说明
观后笔记2.0——一些深入的思考 1.情绪大约在两千万年前,哺乳脑统治期间诞生。 2.情绪分为积极情绪和负面情绪。决定某种情绪的出现取决于安全感等级。 自媒体制造负面情绪,想尽办法挑起情绪,吸引流量 安全感充足时,由积极情绪…...
ui设计的发展趋势/网站优化排名软件
写于2019年1月10日天添书香阁开更前的历史记录1今年开始的读书笔记,准备从构建多元思维模型的角度,分析每本书在各自思维模型领域赋予的价值,探索每个思维模型在现实生活中的用法以及与其他思维模型的结合。目标通过5-10年时间,架…...
网站建设公司首选华网天下/设计一个公司网站多少钱
文档坐标和视口坐标 概念 元素的位置是以像素来度量的,向右代表X坐标的增加,向下代表Y坐标的增加。但是,有两个不同的点作为坐标系的原点:元素的X和Y坐标可以相对于文档的左上角或者相对于其中显示文档的视口的左上角。在顶级窗口…...