gpt4 book ai didi

algorithm - 给定一个二叉树和一个 LCA ,找到具有这个 LCA 的节点对的数量?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:01:48 25 4
gpt4 key购买 nike

考虑如下定义的无限二叉树。

For a node labelled v, let its left child be denoted 2*v and its right child 2*v+1. The root of the tree is labelled 1.

For a given n ranges [a_1, b_1], [a_2, b_2], ... [a_n, b_n] for which (a_i <= b_i) for all i, each range [a_i,b_i] denotes a set of all integers not less than a_i and not greater than b_i. For example, [5,9] would represent the set {5,6,7,8,9}.

For some integer T, let S represent the union [a_i, b_i] for all i up to n. I need to find the number of unique pairs (irrespective of order) of elements x,y in S such that the lca(x,y) = T

(维基百科对两个节点的 LCA 有很好的解释。)


例如,对于输入:

A = {2, 12, 11}
B = {3, 13, 12}
T = 1

输出应该是6。(范围是[2,3]、[12,13]和[11,12],它们的并集是集合{2,3,11,12,13}。在所有 20 个可能的对中,正好有 6 个((2,3)、(2,13)​​、(3,11)、(3,12)、(11,13) 和 (12,13)​​)具有1.) 的 LCA

对于输入:

A = {1,7}
B = {2,15}
T = 3

输出应该是6。(给定的范围是[1,2]和[7,15],它们的联合是集合{1,2,7,8,9,10,11,12,13 ,14,15}。在 110 个可能的对中,恰好有 6 个 ((7,12), (7,13), (12,14), (12, 15), (13,14) 和 (13, 15)) 的 LCA 为 3.)

最佳答案

好吧,使用这种递归方法计算符号中两个节点的 LCA 相当简单:

int lca(int a, int b) {
if(a == b) return a;
if(a < b) return lca(b, a);
return lca(a/2, b);
}

现在要找到集合的并集,我们首先需要能够找到特定范围代表的集合。让我们为此引入一个工厂方法:

Set<Integer> rangeSet(int a, int b){
Set<Integer> result = new HashSet<Integer>(b-a);
for(int n = a; n <= b; n++) result.add(n);
return result;
}

这将返回 Set<Integer>包含范围内的所有整数。

要找到这些集合的并集,只需 addAll他们的元素为一组:

Set<Integer> unionSet(Set<Integer> ... sets){
Set<Integer> result = new HashSet<Integer>();
for(Set<Integer> s: sets)
result.addAll(s);
return result;
}

现在,我们需要迭代集合中所有可能的对:

pairLcaCount(int t, Set<Integer> nodes){
int result = 0;
for(int x: nodes)
for(int y: nodes)
if(x > y && lca(x,y) == t) result++;
return result;
}

其他一切都只是胶合逻辑,将您的输入要求转换为此处采用的要求的方法。例如,像这样的东西:

Set<Integer> unionSetFromBoundsLists(int[] a, int[] b){
Set<Integer> [] ranges = new Set<Integer>[a.length];
for(int idx = 0; idx < ranges.length; idx++)
ranges[idx] = rangeSet(a[idx], b[idx]);
return unionSet(ranges);
}

关于algorithm - 给定一个二叉树和一个 LCA ,找到具有这个 LCA 的节点对的数量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22149847/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com