查询树中环的长度

2509. 查询树中环的长度

给你一个整数 n ，表示你有一棵含有 2ⁿ - 1 个节点的 完全二叉树 。根节点的编号是 1 ，树中编号在[1, 2^{n - 1} - 1] 之间，编号为 val 的节点都有两个子节点，满足：

左子节点的编号为 2 * val
右子节点的编号为 2 * val + 1

给你一个长度为 m 的查询数组 queries ，它是一个二维整数数组，其中 queries[i] = [a_i, b_i] 。对于每个查询，求出以下问题的解：

在节点编号为 a_i 和 b_i 之间添加一条边。
求出图中环的长度。
删除节点编号为 a_i 和 b_i 之间新添加的边。

注意：

环是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。
环的长度是环中边的数目。
在树中添加额外的边后，两个点之间可能会有多条边。

请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。

示例 1：

输入：n = 3, queries = [[5,3],[4,7],[2,3]]
输出：[4,5,3]
解释：上图是一棵有 2³ - 1 个节点的树。红色节点表示添加额外边后形成环的节点。
- 在节点 3 和节点 5 之间添加边后，环为 [5,2,1,3] ，所以第一个查询的结果是 4 。删掉添加的边后处理下一个查询。
- 在节点 4 和节点 7 之间添加边后，环为 [4,2,1,3,7] ，所以第二个查询的结果是 5 。删掉添加的边后处理下一个查询。
- 在节点 2 和节点 3 之间添加边后，环为 [2,1,3] ，所以第三个查询的结果是 3 。删掉添加的边。

示例 2：

输入：n = 2, queries = [[1,2]]
输出：[2]
解释：上图是一棵有 2² - 1 个节点的树。红色节点表示添加额外边后形成环的节点。
- 在节点 1 和节点 2 之间添加边后，环为 [2,1] ，所以第一个查询的结果是 2 。删掉添加的边。

提示：

2 <= n <= 30
m == queries.length
1 <= m <= 10⁵
queries[i].length == 2
1 <= a_i, b_i <= 2ⁿ - 1
a_i != b_i

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) { } };

python3 解法, 执行用时: 516 ms, 内存消耗: 29.9 MB, 提交时间: 2022-12-20 09:47:39

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        for i, (a, b) in enumerate(queries):
            res = 1
            while a != b:
                if a > b: a //= 2
                else: b //= 2
                res += 1
            queries[i] = res
        return queries

golang 解法, 执行用时: 116 ms, 内存消耗: 13.9 MB, 提交时间: 2022-12-20 09:47:07

func cycleLengthQueries(_ int, queries [][]int) []int {
	ans := make([]int, len(queries))
	for i, q := range queries {
		res := 1
		for a, b := q[0], q[1]; a != b; res++ {
			if a > b {
				a /= 2
			} else {
				b /= 2
			}
		}
		ans[i] = res
	}
	return ans
}

java 解法, 执行用时: 20 ms, 内存消耗: 78.1 MB, 提交时间: 2022-12-20 09:46:53

class Solution {
    public int[] cycleLengthQueries(int n, int[][] queries) {
        var m = queries.length;
        var ans = new int[m];
        for (var i = 0; i < m; ++i) {
            int res = 1, a = queries[i][0], b = queries[i][1];
            while (a != b) {
                if (a > b) a /= 2;
                else b /= 2;
                ++res;
            }
            ans[i] = res;
        }
        return ans;
    }
}

cpp 解法, 执行用时: 176 ms, 内存消耗: 63.1 MB, 提交时间: 2022-12-20 09:46:42

class Solution {
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>> &queries) {
        int m = queries.size();
        vector<int> ans(m);
        for (int i = 0; i < m; ++i) {
            int res = 1, a = queries[i][0], b = queries[i][1];
            while (a != b) {
                a > b ? a /= 2 : b /= 2;
                ++res;
            }
            ans[i] = res;
        }
        return ans;
    }
};

上一题

下一题

详情