2471. Minimum Number of Operations to Sort a Binary Tree by Level
2nd approach deals with with cycle lengths. This approach is more Math. That one is related to the permutation group on [0,1,..qz-1]. That one is based on the fact that each permutation is a series of cyclic transformations.
A cyclic transformation can be denoted by (i0,i1,…,ik) which is fn fact i0→i1,i1→i2,⋯,ik−1→ik,ik→i0. A cyclic transformation of length k+1 can be performed by k 2-cycles(i.e. swaps).
The length’s counting is using DFS.
For better understanding the permuation, let’s consider the nodes on 2th level.
arr=[7,6,8,5]=>
idx=[2,1,3,0]The permutations are listed by the following
0 1 2 3 <- identity
2 1 3 0 <- idx[x]They can be represented by a cyclic transform (0,2,3) which has length 3. This cyclic transform of length 3 can be proceeded by 2 swaps (2,3) then (0, 2) (order cannot be reversed, 2=|cycle|-1=3-1)
def minimumOperations(self, root: Optional[TreeNode]) -> int:
def dfs(i, idx, viz):
if viz[i]: return 0
viz[i]=True
j=idx[i]
return 1+dfs(j, idx, viz)
q=deque()
q.append(root)
swaps=0
while q:
qz=len(q)
arr=[0]*qz
for i in range(qz):
node=q.popleft()
arr[i]=node.val
if node.left: q.append(node.left)
if node.right: q.append(node.right)
idx=sorted(range(qz), key = lambda k : arr[k])
viz=[False]*qz
for i in range(qz):
if not viz[i]:
swaps+=dfs(i, idx, viz)-1
return swaps#1718. Construct the Lexicographically Largest Valid Sequence
class Solution(object):
def constructDistancedSequence(self, n):
"""
:type n: int
:rtype: List[int]
"""
if n == 1:
return [1]
length = 2 * n - 1
nums = set(range(-2, -n - 1, -1))
h = [([0] * length)]
while h:
lis = heappop(h)
ready = nums - set(lis)
ind = 0
while ind < length and (lis[ind] != 0) :
ind += 1
first = ind
ind += 1
while ind < length and (lis[ind] != 0) :
ind += 1
second = ind
if not ready:
i = 0
while i < len(lis):
if lis[i] == 0:
lis[i] = 1
else:
lis[i] *= -1
i += 1
return lis
for num in sorted(ready):
# print(num, first, second, one)
temp1 = lis[:]
if first - num < length and lis[first - num] == 0:
temp1[first], temp1[first - num ] = num, num
heapq.heappush(h, (temp1))
temp2 = lis[:]
if second - num < length and lis[second - num ] == 0:
temp2[second], temp2[second - num ] = num, num
heapq.heappush(h, (temp2))
class Solution:
def constructDistancedSequence(self, target_number: int) -> List[int]:
# Initialize the result sequence with size 2*n - 1 filled with 0s
result_sequence = [0] * (target_number * 2 - 1)
# Keep track of which numbers are already placed in the sequence
is_number_used = [False] * (target_number + 1)
# Start recursive backtracking to construct the sequence
self.find_lexicographically_largest_sequence(
0, result_sequence, is_number_used, target_number
)
return result_sequence
# Recursive function to generate the desired sequence
def find_lexicographically_largest_sequence(
self, current_index, result_sequence, is_number_used, target_number
):
# If we have filled all positions, return true indicating success
if current_index == len(result_sequence):
return True
# If the current position is already filled, move to the next index
if result_sequence[current_index] != 0:
return self.find_lexicographically_largest_sequence(
current_index + 1,
result_sequence,
is_number_used,
target_number,
)
# Attempt to place numbers from targetNumber to 1 for a
# lexicographically largest result
for number_to_place in range(target_number, 0, -1):
if is_number_used[number_to_place]:
continue
is_number_used[number_to_place] = True
result_sequence[current_index] = number_to_place
# If placing number 1, move to the next index directly
if number_to_place == 1:
if self.find_lexicographically_largest_sequence(
current_index + 1,
result_sequence,
is_number_used,
target_number,
):
return True
# Place larger numbers at two positions if valid
elif (
current_index + number_to_place < len(result_sequence)
and result_sequence[current_index + number_to_place] == 0
):
result_sequence[current_index + number_to_place] = (
number_to_place
)
if self.find_lexicographically_largest_sequence(
current_index + 1,
result_sequence,
is_number_used,
target_number,
):
return True
# Undo the placement for backtracking
result_sequence[current_index + number_to_place] = 0
# Undo current placement and mark the number as unused
result_sequence[current_index] = 0
is_number_used[number_to_place] = False
return False
class Solution {
public:
vector<int> constructDistancedSequence(int n) {
vector<int> result(2 * n - 1, 0);
vector<bool> used(n + 1, false);
backtrack(result, used, n, 0);
return result;
}
private:
bool backtrack(vector<int>& result, vector<bool>& used, int n, int index) {
while (index < result.size() && result[index] != 0) {
index++;
}
if (index == result.size()) {
return true;
}
for (int i = n; i >= 1; i--) {
if (used[i]) continue;
if (i == 1) {
result[index] = 1;
used[1] = true;
if (backtrack(result, used, n, index + 1)) return true;
result[index] = 0;
used[1] = false;
} else if (index + i < result.size() && result[index + i] == 0) {
result[index] = i;
result[index + i] = i;
used[i] = true;
if (backtrack(result, used, n, index + 1)) return true;
result[index] = 0;
result[index + i] = 0;
used[i] = false;
}
}
return false;
}
};