C++BFS走訪 level排序與DFS cycle長度計數解Leetcode 2471 Minimum Number of Operations to Sort a Binary Tree

An-Wen Deng
4粉絲
22 次觀看·2024年12月24日
好 各位好
我們來解今天
NICODE的問題
今天的問題是第2471題
所謂的minimum number of operations to sort a binary tree by level
基本上它就是去針對一個二元素
而且是每一個level去做排序
排序當然基本上
這裡就是要用所謂的交換swamp
去計算最少需要多少次
我們看它的題目說明
它這裡是給一個root
就是一個binary tree
然後基本上這是很重要的條件
每一個節點
它的值是唯一的
一個operation的意思就是
任何兩個節點
在相同level
可以交換它們的值
swamp
它要你返回的是
最少的operation
也就是它最少交換的次數
去使得每個level
它都是排序好的
而且排序的順序是
increasing order
由小而大
因為它是唯一的
所以在這邊的話
當然就是遞增的order
先看它的立體1
這邊是它所給的二元素
基本上你去計算它需要幾次的交換
它就可以達到它提供的要求
就是每個level都是遞增的排序
所以這邊需要交換這個level
這個第二層的部分
level 2的部分
稍微需要考慮一下
在這邊9跟10這裡
當然這邊是不需要交換
基本上它需要交換的部分
在這個第二個level的話
基本上它排序好之後
它會是
5
6
7
8
那它目前的情況是
5
7
6
8
5
所以我們試著可以去
寫出它的一個
變換的一個過程
所以我們這邊可以稍微看一下
所以在這邊的話
5的話會到7
5會到7
那7會到8
8然後到5
所以它在這邊的話
它就形成一個
size為3的一個cycle
基本上如果說你的一個
permutation形成一個cycle的情況下
所以這邊的話
基本上它需要兩個交換
swap
所以這邊
這邊是1
這邊是2
所以1加2
就會等於
3
基本上第一個例子
可以用這樣的方式來解答
接下來我們看第二個
所以那個
第二個例子我們可以看
這個當然
level0的話當然是沒有交換
level1的話
這邊是一個交換
我們再看它
第二個
第二層的level
這邊稍微留意一下
這裡的話是
4
到
7
7又到4
那這邊是5
到6
6又到
5
所以呢
原則上這邊是有兩個
two cycle
兩個two cycle的話
個別就是你要交換兩次
所以這邊要加2
所以
1加2當然就等於3嘛
所以這個答案當然是3
那我們再看第三個例子
第三個例子很簡單
因為它都完全排序好了
所以答案當然就是0
都沒有什麼問題
接下來我們看一下它相關的constraints
constraints的部分
關乎我們大概怎麼去解這個問題
嗯
那我們先看它的
節點的個數
最多可以到達是
嗯
十萬
十五次方
所以蠻多的
那它節點的值最大也可以到達十萬
嗯
以這樣的一個數字大小
我們當然就是用一般的sort
就好了
系統裡面內設的一個
sorting函數應該就
就好了
你如果另外再去
做counting sort的話
基本上它不見得會比較快
不見得
因為它會用掉蠻多的記憶體
那一個重點是說
數的每一個
上面的每一個節點的值
都是唯一的
這個當然就
在排序上就
就會比較好用
好那我們看一下
我們的解答
大約的一個解答的一個步驟
解答的步驟大概我們
前面當然是用所謂的
BFS
的方式來
來解
當然在這邊的話
BFS裡面有Q
所以Q它的
型態它是
Treat Not
的pointer
所以這樣的方式
一開始當然就是你把
root就放進
這個Q裡面
那一開始的
swamp的個數當然是0
好那主要
你BFS你就是一個
fire loop
一個conditional fire loop
所以只要它不是空
你就可以做下面的事情
基本上
4、5、6
都是在這個迴圈裡面
那
所以
進入這個迴圈的話
我們一開始當然先算
目前
目前在Q裡面的個數
基本上就是
我們目前這個level的一個個數
然後呢
我們去
建造一個
容器IDX
基本上我們就是讓它的值
是從0、1
一直到QZ-1
那這個當然
可以用不同的方式去完成
然後呢
我們需要一個
容器去
取得在這個level
所有節點的一個值
這個是有利於
後面的排序的部分
然後再來就是
進行我們這個level
裡面所有節點
的一個處理
所以這邊當然就是我們一般
BFX的
處理
特別是在
基本上在這個內層的Full迴圈裡面
它都是
這個level上所有的一個節點
所以我們一開始當然就
取它的
Nod
就是它在最前面的
那個節點
當然要記得要把它
做pop的動作
然後我們將它的值呢
存到
AR在I的
位置
那我們再看它的
左指數、右指數
是否有存在
如果有存在的話
我們就將它左指數
跟右指數的節點
將它放到
這個Q裡面
這其實是滿一般的一個處理
比較
需要注意的是
因為你需要排序
而你排序呢
基本上是針對每個level
那我們
因為根據它的一個序數
我們知道每一個值都是唯一的
所以呢我們可以針對
它的IDX來排序
那基本上就是它
對應的AR的值
來做這樣的排序
那在這裡也是不需要
所謂的stable sort
因為原則上
每一個值都不同
所以不會有unstable的
一個情況
那再來就是
我們要去計算
swamp的個數
swamp的個數當然一個比較簡單的方式
就是再透過一個
迴圈去計算
那我們去看J是
每次IDX
在I的值假設為J
那J如果不等於I的話
我們的swamp
當然就要下1
那實際上我們也要
真的去做這樣swamp的動作
然後
在
迴圈呢
其實你還要再recheck一次
確定它真的是
相同的話
你才進行到下一次的
迭代I的一個情況
那這個方式
當然是可以去替代的
可以用
其他的一個
方式
來解
那當然最後當然就是
把我們swamp的個數
把它回傳回去
這個當然是我們一個
第一個解答的方式
那我們再看
特別這個
所謂其他的方式我們大概是
怎麼處理呢
那另外一個
方式我們就是會
利用到這樣的一個
計算的一個公式
這裡面當然牽扯到
跟所謂的
permutation的
那個
計算是有關聯的
原則上呢我們是將
這樣的
identity的
IDX
IDX基本上就是已經排序
排序好的
這是已經排序的東西
根據AR值
排序的
好
所以呢
那這邊當然就是0、1
一直到QZ-1
這樣的一個
這樣的一個map
那原則上呢
這個你可以考慮
就是一個graph
基本上它的edge
它是X到
IDX坐在X上面
那這個當然
這個edge是有
方向性的
這是有方向性的
那所以我們第二個approach
就是透過
這樣的一個公式
那這個公式因為它
其實它是跟permutation
是有關聯的
甚至你可以說
它是一個
所謂的permutation group
那原則上呢
它最主要
它是要藉由
下面一個事情
也就是說任何的一個
permutation呢
基本上它是一連串的
所謂的cyclic
transformation
那什麼叫
cyclic transformation呢
基本上它是可以把它寫成
這樣一個
tuple的一個形態
比方說你從I0 I1
一直到Ik
那這個長度當然就是k加1
那基本上它所代表的就是
你I0
會到I1
I1會到I2
那你最後
最後的Ik會到I0
所以它會形成一個
cycle的一個情況
就如同我們在
剛剛的
所解釋在
example 1的情況
它就是一個
呈現一個
長度為3的一個cycle
那基本上呢
這樣的每一個cycle呢
實際上它就可以藉由
k個two cycle的
一個乘積
其實two cycle就是swamp
我們一般所講的swamp
那基本上
你要計算這個長度
我們當然就是用
DFS的方式就可以計算
好
其實我們再回過頭來
我們再看
我們的第一個例子
那我們看到第一個例子
它基本上它的圖形
就可以畫成是
這樣一個形態
那原則上就是說
你level 2的情況
基本上就是
3跟4對調嘛
這沒什麼好說的
基本上我們特別要講的是
在level
所以這邊level 2
的一個情形
好
level 2的情況我們知道它是
7685
所以它的
根據它的ARR的值
你排序以後
它的IDX的值
它就是2130
好
所以我們是可以把它寫成
上下的
這樣一個排列
上面當然就是根據它的
0123
下面的話就是
根據它的IDX
實際上也是針對
ARR的排序
好
所以我們在這邊就可以看
它其實就是
0到2
2到3
3再到0
好
所以基本上它就是
形成一個cycle
那這個cycle它的長度是為
3
好
那-1的話就等於2
那它實際上真的需要做的
swap是先
23兩個對調
然後再02兩個對調
基本上透過這樣的方式
所以這邊的長度
是3
這邊的長度是
2
這裡的長度是
1
1的話當然-1是0
2-1是1
3-1是2
下面是分別
又是兩個
ID的話我們基本上是可以不用看
所以這個整個加起來
當然就是3
透過這樣的方式
我們實際上
就可以把這樣的
一個問題把它解出來
接下來我們看我們在lead code
實作的一個情形
好這邊是我們
lead code的一個解答
那我們把這邊
的註解把它打開
這邊也把它打開
我們基本上是可以看
它一個執行過程
好
先用這三個case
執行一遍
好所以在
這邊我們其實就可以看
第一個例子
它的一個情形
我們把
它的圖
顯示出來這樣其實會比較
容易可以看到
它的計算的一個步驟
第二個
例子的情況
所以像這邊
如果是一個的話
其實它就是
就是one cycle
one cycle就是自己對自己
像這個是two cycle
01對調
這邊有兩個two cycle
所以加起來是3
第三個
基本上它全部都是
one cycle
其實根本不用管它
所以這個是有關於
我們一個解答的部分
好
這個細節的部分
我們其實稍微
仔細看一下
其實我們在這邊比較
呃
有關於它Lens的技術
我們原則上就可以採用
DFS的
一個情形
其實它的撰寫非常簡單
我們當然需要一個
Visit
去
儲存它是否有走訪
的一個情況
它如果已經走訪過了
當然就return出去
return 0
然後這個部分
呃
我們在第七行的部分呢
當然它已經走訪到
所以我們把它設為1
然後我們再看它
IDX所對應的值是
Z
然後再用遞回的方式
當然已經
長度增加1了
透過這樣的方式我們其實就可以
完成它的一個
呃
Cycle Lens的一個計算
那實際的
在程式
裡面的一個情況
基本上就是在
這個第四十行
到
四十七行的部分
其實它的整個
呃
程式的一個流程大致是如此
那我們就先談到這裡
