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 * 104parent[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…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
