专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近浙江杭州一位35岁程序员因长期熬夜，导致脑干出血，昏迷了15天，经过紧急治疗后，他在接受媒体采访时说：自己每天早上 7 点起床，到凌晨一两点睡。
这简直是拿生命当儿戏，说实话凌晨一两点睡，20多岁的时候我也遇到过，不过一年也不会超过5次，如果真的睡那么晚，第二天基本上要9点之后起床了。35岁之后就更不能这样搞了，长期下去早晚有出事。
当事人称自己在ICU一共待了28天，后来又去康复医院待了70多天，回家之后也一直在康复和锻炼，现在已经恢复了大约70%，但可能没有办法完全康复了。
他还说：“现在的我看待生活，觉得让自己开心很重要，活得自由一点。之前想着我要挣钱，会在很多方面压制自己，现在的话我觉得更多的可能要去好好体验生活，让自己过得快乐。也希望大家如果觉得累了，就歇一歇，我是前车之鉴。”
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第1483题：树节点的第 K 个祖先，难度是困难。
给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类：
1，TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
2，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 * 10^4
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5 * 10^4 次
问题分析
这题让返回某个节点的第 k 个祖先节点，并且查询次数高达 5 * 10^4 ，如果每次查询的时候都要重新找，肯定是不行的。因为这题没有对树修改的函数，所以这棵树是固定的，我们可以先计算所有节点的第 x 个祖先节点，查询的时候就会更加方便。
我们这里使用倍增的思想，定义数组dp[i][j]表示节点 i 的第 2^j 个祖先。很明显当 j 等于 0 的时候，dp[i][0]表示的是节点 i 的父节点。
找到每个节点的父节点了，那么肯定也能找到每个节点父节点的父节点，也就是dp[i][1]=dp[dp[i][0]][0]，也就是说节点 i 的第 2^1 个祖先是节点 i 的第 2^0 个祖先的第 2^0 个祖先。
更进一步我们可以得出节点 i 的第 2^j 个祖先是节点 i 的第 2^(j-1) 个祖先的第 2^(j-1) 个祖先。举个例子，节点 i 的第 8 个祖先节点是它的第 4 个祖先节点的第 4 个祖先节点。
所以我们可以得到：dp[i][j]=dp[dp[i][j-1]][j-1]，但这样计算的结果是不完整的，比如计算 i 的第 13 个祖先节点，我们可能最多只能计算它的第 8 个祖先节点，但这不影响查询。
在进行查询的时候我们是根据这个数字的二进制进行查询的。比如 13 的二进制是 1101，我们只需要往上先查询 i 的第 1 个，然后第 4 个，最后第 8 个，最终结果就是 i 的第 13 个祖先节点。
JAVA：
class TreeAncestor { int bits;// n 的最大位数 // dp[i][j] 表示节点 i 的第 2^j 个祖先 int[][] dp; public TreeAncestor(int n, int[] parent) { bits = (int) (Math.log(n) / Math.log(2)) + 1; dp = newint[n][bits]; for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);// 全部默认为 -1 。 // 所有节点的第一个祖先是它的父节点。 for (int i = 0; i < n; i++) dp[i][0] = parent[i]; // 节点 i 的第 2^j 个祖先也是节点 i 的第2^(j-1)个祖先的第2^(j-1)个祖先。 for (int j = 1; j < bits; j++) { for (int i = 0; i < n; i++) { // i 的第2^(j-1)个祖先就是dp[i][j - 1]。 if (dp[i][j - 1] != -1) dp[i][j] = dp[dp[i][j - 1]][j - 1]; } } } // 利用二进制的特性使用倍增查询。 public int getKthAncestor(int node, int k) { for (int j = 0; j < bits; j++) { // 比如 k 是13，它的二进制是1101，只有二进制中是 1 的时候才需要查询， // 先往上查 1 个，在往上查 4 个，最后在往上查 8 个，正好查找第 13 个。 if (((k >> j) & 1) == 1) { // 从node开始往上查询第 2^j 个。 node = dp[node][j]; if (node == -1)// 如果为 -1 ，说明不存在第 k 个祖先。 return -1; } } return node; } }C++：
class TreeAncestor { private: int bits; // n 的最大位数 vector
> dp; // dp[i][j] 表示节点 i 的第 2^j 个祖先 public: TreeAncestor(int n, vector
&parent) { bits = (int) (log(n) / log(2)) + 1; dp = vector
>(n, vector
(bits, -1)); // 初始化为 -1 // 所有节点的第一个祖先是它的父节点。 for (int i = 0; i < n; i++) dp[i][0] = parent[i]; // 节点 i 的第 2^j 个祖先也是节点 i 的第2^(j-1)个祖先的第2^(j-1)个祖先。 for (int j = 1; j < bits; j++) { for (int i = 0; i < n; i++) { // i 的第2^(j-1)个祖先就是dp[i][j - 1]。 if (dp[i][j - 1] != -1) dp[i][j] = dp[dp[i][j - 1]][j - 1]; } } } // 利用二进制的特性使用倍增查询。 int getKthAncestor(int node, int k) { for (int j = 0; j < bits; j++) { // 比如 k 是13，它的二进制是1101，只有二进制中是 1 的时候才需要查询， // 先往上查 1 个，在往上查 4 个，最后在往上查 8 个，正好查找第 13 个。 if (((k >> j) & 1) == 1) { // 从node开始往上查询第 2^j 个。 node = dp[node][j]; if (node == -1)// 如果为 -1 ，说明不存在第 k 个祖先。 return-1; } } return node; } };
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴