LeetCode 1483.树节点的第 K 个祖先:树上倍增

【LetMeFly】1483.树节点的第 K 个祖先:树上倍增

力扣题目链接:https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/

给你一棵树,树上有 n 个节点,按从 0n-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 < n0 <= parent[i] < n 总成立
  • 0 <= node < n
  • 至多查询 5 * 104

解题方法:树上倍增

预处理并创建一个anc数组,令anc[i][j]为节点i的第 2 j 2^j 2j个祖先。(其中ancancestors的缩写)

这样就剩下了两个问题:

问题一、如何创建anc数组

首先anc[i][0] = parent[i] 2 0 = 1 2^0=1 20=1,节点i的第1个祖先为其父节点)

其次j > 1anc[i][j] = anc[ anc[i][j-1] ][j-1](例如节点i的第8祖先节点 等于 节点i的第4祖先节点的第4祖先节点)

并且有anc[-1][*] = -1(已经无祖先节点了,再往上跳还是-1

由于 2 16 = 65536 > 50000 2^{16}=65536\gt 50000 216=65536>50000,因此最多 log ⁡ n = 16 \log n=16 logn=16次就能完成一个节点的所有 2 j 2^j 2j祖先数组。

问题二、如何依据anc数组快速求得节点node的第k祖先

假设要求节点node的第 k = 5 = 10 1 2 = 4 + 1 k=5=101_2=4+1 k=5=1012=4+1祖先节点,那么可以求node的第1父节点的第4父节点,也就是说anc[ anc[node][0] ][2]即为答案。

因此,我们可以从低到高(从高到低也一样)遍历k的二进制位,如果第j位为1,则令node = anc[node][j],即求node 2 j 2^j 2j祖先节点。

特别的,若node已经为-1则可直接返回。

时空复杂度

  • 时间复杂度:初始化 O ( n log ⁡ n ) O(n\log n) O(nlogn),单次查询 O ( log ⁡ n ) O(\log n) O(logn)
  • 空间复杂度:初始化 O ( n log ⁡ n ) O(n\log n) O(nlogn),单次查询 O ( 1 ) O(1) O(1)

AC代码

C++
class TreeAncestor {
private:
    const static int Log = 16;  // 2 ^ 16 = 65536
    vector<vector<int>> ancestors;
public:
    TreeAncestor(int n, vector<int>& parent) {
        ancestors = vector<vector<int>>(n, vector<int>(Log, -1));
        for (int i = 0; i < n; i++) {
            ancestors[i][0] = parent[i];
        }
        for (int j = 1; j < Log; j++) {
            for (int i = 0; i < n; i++) {
                if (ancestors[i][j - 1] != -1) {  // don't forget
                    ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
                }
            }
        }
    }
    
    int getKthAncestor(int node, int k) {
        for (int j = 0; j < Log && node != -1; j++) {
            if ((k >> j) & 1) {
                node = ancestors[node][j];
            }
        }
        return node;
    }
};
Python
# from typing import List


Log = 16

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.ancestors = [[parent[i]] + [-1] * (Log - 1) for i in range(n)]
        for j in range(1, Log):
            for i in range(n):
                if self.ancestors[i][j - 1] != -1:
                    self.ancestors[i][j] = self.ancestors[self.ancestors[i][j - 1]][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:
        for j in range(Log):
            if (k >> j) & 1:
                node = self.ancestors[node][j]
            if node == -1:
                break
        return node

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/137426434

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

redis主从复制与哨兵模式

redis主从复制 Redis主从复制&#xff08;Redis replication&#xff09;是Redis提供的一种数据备份和故障转移机制。通过主从复制&#xff0c;可以将一个Redis服务器&#xff08;主节点&#xff09;的数据复制到一个或多个Redis服务器&#xff08;从节点&#xff09;。这样做…

【面经】interrupt()、interrupted()和isInterrupted()的区别与使用

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;面经 ⛺️稳中求进&#xff0c;晒太阳 interrupt方法 如果打断线程正在sleep&#xff0c;wait&#xff0c;join会导致被打断的线程抛出InterruptedException&#xff0c;并清除打断标记。如…

FebHost:什么是土耳其.TR域名?

当前互联网高速发展,一个国家的顶级域名已成为其网络形象的重要标识。近期,土耳其国家顶级域名”.TR”引起了广泛关注,成为业界热议的话题。 作为代表土耳其共和国的国家顶级域名(ccTLD),.TR域名于1991年首次引入,由土耳其科技和信息技术部负责管理。除了常见的”.com.tr”、”…

画图理解JVM相关内容

文章目录 1. JVM视角下&#xff0c;内存划分2. 类内存分布硬核详解1. 获取堆内存参数2. 扫描堆内存&#xff0c;定位实例3. 查看实例所在地址的数据4. 找到实例所指向的类信息的地址5. 查看class信息6. 结论 3. Java的对象创建流程4. 垃圾判别算法4.1 引用计数法4.2 可达性分析…

GD32F470_光敏电阻光照传感器模块移植手册

2.3 光敏电阻光照传感器 光敏电阻是用硫化隔或硒化隔等半导体材料制成的特殊电阻器&#xff0c;其工作原理是基于内光电效应。随着光照强度的升高&#xff0c;电阻值迅速降低&#xff0c;由于光照产生的载流子都参与导电&#xff0c;在外加电场的作用下作漂移运动&#xff0c;电…

如何从文本数据中提取子列表

提取文本数据中的子列表可以通过各种方式实现&#xff0c;具体取决于文本数据的结构和提取子列表的条件。例如&#xff1a;使用字符串操作和条件判断、使用正则表达式、使用自然语言处理工具、使用自定义解析器等几种模式&#xff0c;那么对于在日常使用中会有那些问题呢 &…

ssm基于HTML5的出租车管理系统论文

摘 要 网络技术和计算机技术发展至今&#xff0c;已经拥有了深厚的理论基础&#xff0c;并在现实中进行了充分运用&#xff0c;尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代&#xff0c;所以对于信息的宣传和管理就很关键。因此出租车信息的管…

知识融合:知识图谱构建的关键技术

目录 一、引言二、知识图谱基础2.1 知识表示三元组属性图 2.2 知识抽取实体抽取关系抽取属性抽取 三、知识融合的核心问题3.1 实体识别与链接实体识别实体链接 3.2 重复实体合并方法示例 3.3 关系融合挑战方法示例 四、知识融合技术深度解析4.1 基于规则的方法规则设计原则规则…

13 - 关于存储器读写的问题

---- 整理自B站UP主 踌躇月光 的视频 1. 存储器存在的问题 前面章节存储器存在问题&#xff0c;读取和写入分开&#xff0c;会造成读写冲突&#xff0c;所以设计要改成写时没法读。 1.1 单字节存储器 片选 CS1&#xff0c;WE1 时&#xff0c;EN0&#xff0c;写入 片选 CS1&am…

CLoVe:在对比视觉语言模型中编码组合语言

CLoVe:在对比视觉语言模型中编码组合语言 摘要引言相关工作CLoVe: A Framework to Increase Compositionality in Contrastive VLMsSynthetic CaptionsHard NegativesModel Patching CLoVe: Encoding Compositional Language inContrastive Vision-Language Models 摘要 近年来…

MySQL-排序与分页

1. 排序 如果没有使用排序操作&#xff0c;默认情况下查询返回的数据是按照添加数据的顺序显示的。 SELECT * FROM employees;1.1 基本使用 1&#xff09;使用 ORDER BY 对查询到的数据进行排序操作。 升序&#xff1a;ASC(ascend)降序&#xff1a;DESC (descend) 练习&am…

ARM汇编与逆向工程:揭秘程序背后的神秘世界

文章目录 一、ARM汇编语言&#xff1a;底层世界的密码二、逆向工程&#xff1a;软件世界的侦探工作三、ARM汇编与逆向工程的完美结合四、ARM汇编逆向工程的风险与挑战五、ARM汇编逆向工程的未来展望《ARM汇编与逆向工程 蓝狐卷 基础知识》内容简介作者简介译者简介ChaMd5安全团…

商标“五分法”,如何起名显著性更强通过率更高!

1976年在Abercrombie一案美国判例中提出的商标五分法&#xff0c; 基本上在全球范围内得到认可和共识&#xff0c;普推知产老杨平常检索时&#xff0c;我国一些专家相关的论文及专著和判例中也会经常涉及到。 商标五分法主要是把商标分成个五种类型&#xff0c; 通用的&#xf…

Linux 常用命令(持续更新中...)

1. ls 查看文件列表命令 语法&#xff1a; ls [-a -l -h] [Linux路径] -a -l -h 是可选的选项 &#xff08;-h需配合-l命令一起使用&#xff09;Linux路径是此命令可选的参数 ls #查看当前目录所有非隐藏文件(平铺方式显示) ls -a #查看当前目录下所有文件 …

多线程+互斥+条件变量题目

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;题目解析 目录 &#x1f449;&#x1f3fb; 完成两个线程通过条件变量实现交替打印错误代码加优化(c线程库版本)版本2&#xff08;使用phtread.h库&#xff…

leetcode代码记录(买卖股票的最佳时机 IV

目录 1. 题目&#xff1a;2. 我的代码&#xff1a;小结&#xff1a; 1. 题目&#xff1a; 给你一个整数数组 prices 和一个整数 k &#xff0c;其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说…

【stm32】I2C通信外设

【stm32】I2C通信外设 概念部分 如果简单应用&#xff0c;选择软件I2C。如果对性能指标要求比较高 选择硬件I2C 有硬件电路自动反转引脚电平&#xff0c;软件只需要写入控制寄存器CR和数据寄存器DR 为了实时监控时序的状态&#xff0c;还要读取状态寄存器SR 写入控制寄存器CR…

LC 226.翻转二叉树

226. 翻转二叉树 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a; root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1] 示例 2&#xff1a; 输入&#xff1a; root [2,1,3] 输出&#xff1a…

【Linux】进程控制之进程程序替换

目录 前言 替换的原理 替换函数 记忆技巧 函数使用 execl execlp execv execvp execle execvpe 调用其它语言的程序 模拟实现一个shell 前言 关于本文可以先去看看上一篇【Linux】进程控制详解-CSDN博客可以更好的理解这里的内容 学完本篇文章&#xff0c;你就…

【Linux操作系统】,Linux运维面试自我介绍

16、右击创建好的虚拟机&#xff0c;打开设置 17、添加自己的CentOS系统文件 18、开启虚拟机 19、使用方向键选择&#xff0c;enter键确定 20、选择中文 21、设置好系统时间以及语言&#xff0c;点击“安装位置” 22、选择自定义分区 23、点击“”&#xff0c;定义分区 24、设置…