You are given an integer n. There is a complete binary tree with 2n – 1 nodes. The root of that tree is the node with the value 1, and every node with a value val in the range [1, 2n – 1 – 1] has two children where:
The left node has the value 2 * val, and
The right node has the value 2 * val + 1.
You are also given a 2D integer array queries of length m, where queries[i] = [ai, bi]. For each query, solve the following problem:
Add an edge between the nodes with values ai and bi.
Find the length of the cycle in the graph.
Remove the added edge between nodes with values ai and bi.
題目給予一顆完整的二元樹，編號從 1 ~ 2 ^ n - 1。 每個節點 val 如下 左子節點：2 * val 右子節點：2 * val + 1 題目給予一個二維陣列的 queries 長度為 n。 暫時在 values ai, bi 之間新增一條邊。 求圖形中圓圈的長度。 計算完圓圈的長度後移除邊。
Example 1:
Input: n = 3, queries = [[5,3],[4,7],[2,3]] Output: [4,5,3] Explanation: The diagrams above show the tree of 23 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge. - After adding the edge between nodes 3 and 5, the graph contains a cycle of nodes [5,2,1,3]. Thus answer to the first query is 4. We delete the added edge and process the next query. - After adding the edge between nodes 4 and 7, the graph contains a cycle of nodes [4,2,1,3,7]. Thus answer to the second query is 5. We delete the added edge and process the next query. - After adding the edge between nodes 2 and 3, the graph contains a cycle of nodes [2,1,3]. Thus answer to the third query is 3. We delete the added edge.
Example 2:
Input: n = 2, queries = [[1,2]] Output: [2] Explanation: The diagram above shows the tree of 22 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge. - After adding the edge between nodes 1 and 2, the graph contains a cycle of nodes [2,1]. Thus answer for the first query is 2. We delete the added edge.
Solution:
因為結果要陣列表示，我們建立 res 這個空陣列。
接下來我們遍歷 queries 中 query 節點的起點跟終點，
每個 query 我們暫時新增一個邊，長度為 1，
透過 while() 回圈往上走，直到 u, v 兩個相遇，
如果 u < v，則把 v 移到他的父節點(題目說明是二元樹，所以除以 2)，
否則把 u 移到他的父節點，
且每走一步就 cycleLength + 1。
當 u, v 相遇的時候，把計算好的 cycleLength 放到 res 陣列中。
遍歷完所有的 queries 後，回傳 res。
Code 1: BigO(m * log n)
function cycleLengthQueries(n: number, queries: number[][]): number[] {
let res: number[] = []
for (let [u, v] of queries) {
let cycleLength: number = 1;
while (u !== v) {
if (u < v) {
v = Math.floor(v / 2);
} else {
u = Math.floor(u / 2);
}
cycleLength++;
}
res.push(cycleLength);
}
return res;
};
FlowChart:
Example 1
Input: n = 3, queries = [[5,3],[4,7],[2,3]] Processing query: 5 3 u: 5 v: 3 cycleLength now: 2 u: 2 v: 3 cycleLength now: 3 u: 2 v: 1 cycleLength now: 4 Query [5, 3] result: 4 Processing query: 4 7 u: 4 v: 7 cycleLength now: 2 u: 4 v: 3 cycleLength now: 3 u: 2 v: 3 cycleLength now: 4 u: 2 v: 1 cycleLength now: 5 Query [4, 7] result: 5 Processing query: 2 3 u: 2 v: 3 cycleLength now: 2 u: 2 v: 1 cycleLength now: 3 Query [2, 3] result: 3 Final result array: [ 4, 5, 3 ]
Example 2
Input: n = 2, queries = [[1,2]] Processing query: 1 2 u: 1 v: 2 cycleLength now: 2 Query [1, 2] result: 2 Final result array: [ 2 ]