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

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 个祖先 题目描述&#xff1a; 实现代码与解析&#xff1a; 倍增 原理思路&#xff1a; 1483. 树节点的第 K 个祖先 题目描述&#xff1a; 给你一棵树&#xff0c;树上有 n 个节点&#xff0c;按从 0 到 n-1 编号。树以父节点数组的形式给出&#…...

ConstraintLayout在复杂布局中,出现卡顿问题解决记录

ConstraintLayout在画界面的过程中&#xff0c;确实带来了不少的方便&#xff0c;随着使用的越来越多&#xff0c;也发现了一些问题&#xff0c;特此记录一下问题和解决方案。 在背景为图片&#xff0c;而背景图片宽度固定高度自适应的情况下&#xff0c;布局显示在图片固定位…...

责任链模式详解+代码案例

责任链设计模式 定义&#xff1a; 又名职责链模式&#xff0c;为了避免请求发送者与多个请求处理者耦合在一起&#xff0c;将所有请求的处理者通过前一对象记住其下一个对象的引用而连成一条链&#xff1b;当有请求发生时&#xff0c;可将请求沿着这条链传递&#xff0c;直到…...

如何让Webots支持C#语言开发的控制器

Webots支持C、C、Java、Python、Matlab这五种语言开发控制器&#xff0c;没有直接支持C#&#xff0c;但有个同事已经用C#写了大量的机器人控制代码&#xff0c;想在不把C#代码改写成C的情况下&#xff0c;直接用webots仿真&#xff0c;那就得想想办法。(不过&#xff0c;让Chat…...

如何将本地仓库放到远程仓库中

在我们仓库创建好之后&#xff0c;我们复制好ssh 接着我们需要使用git remote add<shortname><url>这个命令 shortname就是我们远程仓库的别名 接着使用git remote -v这个命令查看一下目前远程仓库的别名和地址 原本还有一个指令git branch -M main 指定分支的名…...

Jedis-事务

一&#xff0c;Jedis 我们要使用Java来操作Redis Jedis是Redis官方推荐的java连接工具。使用Java操作Redis的中间件。如果你要使用Java操作redis&#xff0c;那么一定要对jedis十分的熟悉 二&#xff0c;idea 连接jedis 1&#xff0c;导入jar包 <dependencies><depen…...

智慧安防监控EasyCVR视频调阅和设备录像回看无法自动播放的原因排查与解决

智慧安防监控EasyCVR视频管理平台能在复杂的网络环境中&#xff0c;将前端设备统一集中接入与汇聚管理。国标GB28181协议视频监控/视频汇聚EasyCVR平台可以提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联、磁盘阵列存储、视频集中存储、…...

百元不入耳蓝牙耳机哪个好?必入五款高性价比产品

喜欢听歌的朋友都会遇到一个常见问题&#xff0c;长时间戴耳机容易导致耳朵不适&#xff0c;甚至疼痛难忍。这种情况下&#xff0c;要是不听音乐反而感到不舒服&#xff0c;真是让人苦恼&#xff0c;仿佛音乐与耳机无法和谐共存。但是&#xff0c;难道就没有一款既舒适又让人心…...

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即时通讯平台的开发过程中&#xff0c;我们面临了选择最佳缓存系统的关键技术决策。经过细致的考量&#xff0c;我们选择了depcache作为IMBoy的核心缓存机制。本文将阐述IMBoy缓存系统的选型理由&#xff0c;并对比分析depcache与纯ETS方案及Redis方案的不同优势。 1. …...

Twitter Api查询用户粉丝列表

如果大家为了获取实现方式代码的话可能要让大家失望了&#xff0c;这边文章主要是为了节省大家开发时间&#xff0c;少点坑。https://api.twitter.com/2/users/:id/followers &#xff0c;这个接口很熟悉吧&#xff0c;他是推特提供的获取用户关注者&#xff08;粉丝&#xff0…...

深入理解计算机系统 家庭作业 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中&#xff0c;主函数通常指的是脚本的入口点&#xff0c;也就是当你直接运行一个Python脚本时&#xff0c;会首先执行的函数。在大多数Python脚本中&#xff0c;主函数并不是通过main()这样的函数名来定义的&#xff0c;而是通过检查脚本是作为模块导入还是被直接运行…...

34.Python从入门到精通—Python3 正则表达式检索和替换

34.从入门到精通&#xff1a;Python3 正则表达式检索和替换 repl 参数是一个函数 正则表达式对象 正则表达式修饰符 - 可选标志 正则表达式模式* 正则表达式实例 检索和替换repl 参数是一个函数正则表达式对象正则表达式修饰符 - 可选标志正则表达式模式*正则表达式实例 检索和…...

springboot 反射调用ServiceImpl时报错:java.lang.NullPointerExceptio、,mapper为null【解决方法】

springboot 反射调用ServiceImpl时报错&#xff1a;java.lang.NullPointerException、mapper为null【解决方法】 问题描述问题分析解决方案创建SpringBootBeanUtil编写调用方法 executeMethod调用 总结 问题描述 在使用Spring Boot时&#xff0c;我们希望能够通过反射动态调用…...

内网安全之域内密码喷洒

域内密码喷洒一般和域内用户名枚举一起使用&#xff0c;可以在无域内凭据的情况下&#xff0c;通过枚举出域内存在的用户名&#xff0c;进而对域内存在的用户名进行密码喷洒&#xff0c;以此来获得域内有效凭据。 在Kerberos协议认证的AS-REQ阶段&#xff0c;请求包cname对应的…...

何为HTTP状态码?一文清楚基本概念。

在客户端与服务器之间的信息传输过程中&#xff0c;我们可以将其比喻为客户与快递员之间的包裹传递。那么服务器是如何通知客户端&#xff0c;操作是成功还是失败&#xff1f;或者有其他的一些情况呢&#xff1f;&#xff08;就像客户可以查询快递的状态&#xff09; 而这背后…...

SV学习笔记(七)

文章目录 类型转换写在前面动态转换子类句柄赋值于父类句柄父类句柄转换为子类句柄 虚方法写在前面非虚函数的调用虚函数的调用虚方法的建议为什么使用虚方法 对象拷贝写在前面赋值和拷贝总结 回调函数写在前面实例完成回调函数功能需要三步&#xff1a; 参数化类写在前面实现一…...

Windows SDK(五)按钮静态文本与编辑框控件

我们首先应该知道&#xff0c;所谓按钮静态文本等等控件都是窗口&#xff0c;他们都是隶属于父窗口下的子窗口&#xff0c;所 以在创建控件前&#xff0c;我们要首先创建一个父窗口&#xff0c;此处我们直接使用Windows桌面程序创建时&#xff0c;程 序自动为我们创建的一个窗…...

基于SSM框架实现的在线心理评测与咨询系统(技术栈 spring+springmvc+mybatis+jsp+jquery+css)

一、项目简介 本项目是一套基于SSM框架实现的在线心理评测与咨询系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&am…...

政务大模型微调全攻略,打造高效智能政务AI系统!

在数字化、智能化成为新质生产力核心驱动力&#xff0c;十五五政务数字化转型加速推进的背景下&#xff0c;智慧政务建设成为各地政府提升治理能力的关键。但当前政务领域普遍面临数据处理效率低、AI 模型适配性差、服务自动化水平不足、敏感数据管理难等痛点&#xff0c;通用大…...

Axure隐藏技巧大公开:动态面板与热区的高级用法(含常见问题解决方案)

Axure隐藏技巧大公开&#xff1a;动态面板与热区的高级用法&#xff08;含常见问题解决方案&#xff09; 在原型设计领域&#xff0c;Axure RP早已超越了基础线框工具的角色&#xff0c;成为交互设计师手中的瑞士军刀。但许多用户在使用动态面板和热区时&#xff0c;往往只停留…...

MCP服务器本地数据库连接器接入实战:从零到稳定连接仅需17分钟,附完整CLI脚本与避坑清单

第一章&#xff1a;MCP服务器本地数据库连接器接入实战&#xff1a;从零到稳定连接仅需17分钟&#xff0c;附完整CLI脚本与避坑清单环境准备与依赖确认 确保目标服务器已安装 PostgreSQL 14 或 MySQL 8.0&#xff0c;并启用本地 socket 连接。验证 psql 或 mysql CLI 工具可执行…...

弹性伸缩与高可用:重力科技智能投放平台的云原生架构实践

一、 出海营销平台&#xff1a;流量洪峰与全球化部署的挑战 重力科技的AI智能投放平台&#xff0c;作为全球出海品牌的营销利器&#xff0c;面临着严峻的架构挑战&#xff1a; 流量洪峰&#xff1a; 面对全球不同时区的营销活动、节假日促销、突发热点等&#xff0c;请求量可能…...

智能体记忆:结构化索引优化上下文效率

在之前的文章中&#xff0c;我探讨了在与AI智能体协作时&#xff0c;角色设定为何仍然重要。不同的视角能以原始上下文无法复制的方式影响输出。但我也提出了一个需要正面解决的局限&#xff1a;每一个全新的上下文窗口都是从零开始的。角色设定每次都需要从头重建对你代码库的…...

LaTeX多行大括号公式速成指南:5分钟搞定不等式排版(附常见错误排查)

LaTeX多行大括号公式速成指南&#xff1a;5分钟搞定不等式排版&#xff08;附常见错误排查&#xff09; 在学术写作中&#xff0c;数学公式的排版质量直接影响论文的专业性。对于不等式组、分段函数等需要多行对齐的场景&#xff0c;LaTeX的大括号语法是每个研究者必须掌握的技…...

工业上位机开发实战:基于.NET 6和CIP协议,5分钟搞定与ControlLogix PLC的数据对接

工业上位机开发实战&#xff1a;基于.NET 6和CIP协议快速对接ControlLogix PLC 在工业自动化领域&#xff0c;高效可靠的数据采集系统是智能制造的核心枢纽。本文将带您探索如何利用最新的.NET 6技术栈&#xff0c;在5分钟内构建与罗克韦尔ControlLogix系列PLC的通信桥梁。不同…...

云边端一体化核心技术:数据同步与边缘智能实现

云边端一体化核心技术&#xff1a;数据同步与边缘智能实现&#x1f4da; 本章学习目标&#xff1a;深入理解数据同步与边缘智能实现的核心概念与实践方法&#xff0c;掌握关键技术要点&#xff0c;了解实际应用场景与最佳实践。本文属于《云原生、云边端一体化与算力基建&#…...

别再手动P图了!用Python+OpenCV给图片批量加Logo水印,5分钟搞定

PythonOpenCV批量水印自动化&#xff1a;电商与自媒体工作流效率革命 每次处理上百张产品图时&#xff0c;最痛苦的不是修图调色&#xff0c;而是机械重复地拖动Logo到每个角落——这几乎是所有电商美工的日常噩梦。我曾用3小时完成200张新品上架图的品牌标识添加&#xff0c;直…...

神经网络计算量那些事:FLOPs/MACs/MACCs到底怎么算?从公式到代码的完整对照

神经网络计算量全解析&#xff1a;从FLOPs到MACs的实战指南 在深度学习模型优化过程中&#xff0c;计算量评估是每个开发者必须掌握的核心技能。面对FLOPs、MACs、MACCs这些专业术语&#xff0c;新手往往一头雾水——它们究竟代表什么&#xff1f;如何准确计算&#xff1f;更重…...