力扣2509-LCA
这是我第一次参加力扣周赛,只过了第一题,第三题直接卡过去的,但是后来力扣官方还是直接WA了,直接上链接:
这个题目是第四题!!
周赛链接:竞赛 - 力扣 (LeetCode)
第四题链接:力扣
题目:
2509. 查询树中环的长度
给你一个整数 n
,表示你有一棵含有 2n - 1
个节点的 完全二叉树 。根节点的编号是 1
,树中编号在[1, 2n - 1 - 1]
之间,编号为 val
的节点都有两个子节点,满足:
- 左子节点的编号为
2 * val
- 右子节点的编号为
2 * val + 1
给你一个长度为 m
的查询数组 queries
,它是一个二维整数数组,其中 queries[i] = [ai, bi]
。对于每个查询,求出以下问题的解:
- 在节点编号为
ai
和bi
之间添加一条边。 - 求出图中环的长度。
- 删除节点编号为
ai
和bi
之间新添加的边。
注意:
- 环 是开始和结束于同一节点的一条路径,路径中每条边都只会被访问一次。
- 环的长度是环中边的数目。
- 在树中添加额外的边后,两个点之间可能会有多条边。
请你返回一个长度为 m
的数组 answer
,其中 answer[i]
是第 i
个查询的结果。
先直接上代码:
class Solution {
public:vector cycleLengthQueries(int n, vector>& queries) {//最近公共祖先问题//题目已经明确是一个完全二叉树int t = queries.size();vector w;for (int k = 0; k < t; k++) {int a = queries[k][0], b = queries[k][1]; //两个结点就是a and bint ans = 1;while (a != b) a > b ? a = a / 2 : b = b / 2, ans++; //a和b谁的数比较大,谁就除以2//循环终止条件是a和b相等w.push_back(ans);}return w;}
};
其实题目的主要思想很简单,就是寻找这个完全二叉树的最近公共祖先。
最近公共祖先还可以用倍增的思想,时间复杂度会更好,但是不会😥😭。
若有错误或侵权,请指出,会积极改正。
本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击【内容举报】进行投诉反馈!