lc1483_树节点的第K个祖先 TED演讲：不那么混蛋地对自己，有什么好处 openui 注意网络故障的时候，不要让管理服务和关键的 raft 组都在临界状态
Algorithm
lc1483_树节点的第K个祖先
思路:
感觉就是k次获取parent[node]:
- 第一次
res = parent[node]
- 第2..i次
res = parent[res]
但是这样会超时，还是要预处理然后查询。
直接用 dp[node][k] 存取 2.5e8 的int数据量, 也就是 1GB…申请不到…
但是把dp数组改小，还是能通过几个case的，证明思路是对的，但是需要更高效的存储手段。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class TreeAncestor {
int dp[50010][50010];
public:
TreeAncestor(int n, vector<int>& parent) {
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++) {
int j = 1;
dp[i][j] = parent[i];
while (dp[i][j] != -1) {
dp[i][j+1] = parent[dp[i][j]];
j++;
}
}
}
int getKthAncestor(int node, int k) {
return dp[node][k];
}
};
/**
* Your TreeAncestor object will be instantiated and called as such:
* TreeAncestor* obj = new TreeAncestor(n, parent);
* int param_1 = obj->getKthAncestor(node,k);
*/
|
看下答案吧。
题解用的是倍增，直接2倍的粒度向上判断，然后k也用二进制拆解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class TreeAncestor {
public:
constexpr static int Log = 16;
vector<vector<int>> ancestors;
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) {
ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
}
}
}
}
int getKthAncestor(int node, int k) {
for (int j = 0; j < Log; j++) {
if ((k >> j) & 1) {
node = ancestors[node][j];
if (node == -1) {
return -1;
}
}
}
return node;
}
};
|
Review
TED演讲：不那么混蛋地对自己，有什么好处
冥想缓解焦虑，接纳自己。
Tips
openui
Share
注意网络故障的时候，不要让管理服务和关键的 raft 组都在临界状态。
比如管理服务刚重启，但是关键 raft 组在选举，这样就会导致关键 raft 被管理服务重置导致映射信息丢失。