刷了360多道算法題，我終于頓悟了它的真諦
大家好，我是哪吒。
最近一直在刷算法題，刷華為OD算法題，有諸多好處：
- 比如可以考華為OD崗位，大廠算法崗，待遇直接拉滿，走向人生巔峰。
- 不考也沒(méi)關(guān)系，就當(dāng)練習(xí)算法題了，哪吒半年時(shí)間刷了360多道題，平均一天六道題，一道題40分鐘，一天刷4個(gè)小時(shí)？現(xiàn)在一看到算法題，真的有一種靈光乍現(xiàn)的感覺(jué)。
希望用我自己瘋狂刷題的勁頭，感染大家，讓大家愛(ài)上刷題，順利通過(guò)華為OD機(jī)試，掌握更多優(yōu)秀的算法。
下面這道題，是很經(jīng)典的深度優(yōu)先搜索dfs算法 + 二叉樹(shù)。掌握一道題，精通一類題，沖吧~
一、題目描述
某文件系統(tǒng)中有N個(gè)目錄，每個(gè)目錄都有一個(gè)獨(dú)一無(wú)二的ID。每個(gè)目錄只有一個(gè)父目錄，但每個(gè)父目錄下可以有零個(gè)或者多個(gè)子目錄，目錄結(jié)構(gòu)呈樹(shù)狀結(jié)構(gòu)。
假設(shè)，根目錄的ID為0，且根目錄沒(méi)有父目錄，其他所有目錄的ID用唯一的正整數(shù)表示，并統(tǒng)一編號(hào)。
現(xiàn)給定目錄ID和其父目錄ID的對(duì)應(yīng)父子關(guān)系表[子目錄ID，父目錄ID]，以及一個(gè)待刪除的目錄ID，請(qǐng)計(jì)算并返回一個(gè)ID序列，表示因?yàn)閯h除指定目錄后剩下的所有目錄，返回的ID序列以遞增序輸出。
注意：
- 被刪除的目錄或文件編號(hào)一定在輸入的ID序列中。
- 當(dāng)一個(gè)目錄刪除時(shí)，它所有的子目錄都會(huì)被刪除。
說(shuō)人話就是：
輸入m行數(shù)據(jù)，第一個(gè)元素是子節(jié)點(diǎn)值，第二個(gè)是父節(jié)點(diǎn)值，m行數(shù)據(jù)可以組成一個(gè)二叉樹(shù)。
最后輸入要?jiǎng)h除的節(jié)點(diǎn)，求二叉樹(shù)剩下的節(jié)點(diǎn)值。
例如輸入：
5
8 6
10 8
6 0
20 8
2 6
8
二叉樹(shù)就會(huì)變?yōu)椋?/p>
6
2 8
10 20
刪除最后的8，輸出6 2就是結(jié)果。
很簡(jiǎn)單吧，少年~
二、輸入描述
輸入的第一行為父子關(guān)系表的長(zhǎng)度m;
接下來(lái)的m行為m個(gè)父子關(guān)系對(duì);
最后一行為待刪除的ID。序列中的元素以空格分割。
三、輸出描述
輸出一個(gè)序列，表示因?yàn)閯h除指定目錄后，剩余的目錄ID。
四、深度優(yōu)先搜索dfs
1、搜索的要點(diǎn)：
- 初始狀態(tài)。
- 重復(fù)產(chǎn)生新?tīng)顟B(tài)。
- 檢查新?tīng)顟B(tài)是否為目標(biāo)，是結(jié)束，否轉(zhuǎn)（2）。
如果搜索是以接近起始狀態(tài)的程序依次擴(kuò)展?fàn)顟B(tài)的，叫寬度優(yōu)先搜索。
2、如果擴(kuò)展是首先擴(kuò)展新產(chǎn)生的狀態(tài)，則叫深度優(yōu)先搜索。
深度優(yōu)先搜索用一個(gè)數(shù)組存放產(chǎn)生的所有狀態(tài)。
- 把初始狀態(tài)放入數(shù)組中，設(shè)為當(dāng)前狀態(tài)。
- 擴(kuò)展當(dāng)前的狀態(tài)，產(chǎn)生一個(gè)新的狀態(tài)放入數(shù)組中，同時(shí)把新產(chǎn)生的狀態(tài)設(shè)為當(dāng)前狀態(tài)。
- 判斷當(dāng)前狀態(tài)是否和前面的重復(fù)，如果重復(fù)則回到上一個(gè)狀態(tài)，產(chǎn)生它的另一狀態(tài)。
- 判斷當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)，如果是目標(biāo)，則找到一個(gè)解答，結(jié)束算法。
- 如果數(shù)組為空，說(shuō)明無(wú)解。
3、深度優(yōu)先搜索dfs代碼架構(gòu)：
public int def(int x, int y ,int step){
if(遞歸出口/達(dá)到目標(biāo)狀態(tài)){
//進(jìn)行對(duì)應(yīng)操作
return 0;
}
for (int i = 0; i < n; i++) {
//遍歷剩下的所有的情況
if(visit[i]==0){
//未訪問(wèn)
x = 下一步更新;
y = 下一步更新;
visit[i] = 1;
def(x,y,step);
visit[i] = 0; //記得回溯還原
}
}
}五、解題思路
根據(jù)題目描述，輸入數(shù)據(jù)可以組成一個(gè)二叉樹(shù)，如果將某個(gè)節(jié)點(diǎn)刪除，求剩余節(jié)點(diǎn)。
輸入父子關(guān)系表的長(zhǎng)度m。
接下來(lái)的m行輸入父子關(guān)系。
輸入待刪除的ID。
遍歷m個(gè)父子關(guān)系，拼接成二叉樹(shù)，拼接剩余的目錄ID。
- 如果該關(guān)系的父節(jié)點(diǎn)是value。
- 如果該父節(jié)點(diǎn)不是待移除的ID。
- 拼接成二叉樹(shù)。
- 拼接剩余的目錄ID -- builder。
- 移除滿足條件的父子關(guān)系。
- 父子關(guān)系集合treeList移除某節(jié)點(diǎn)，treeList長(zhǎng)度-1，下一個(gè)坐標(biāo)i也應(yīng)該-1。
- 如果剩余的父子關(guān)系集合treeList為0，則不需要再進(jìn)行dfs，如果要dfs的node節(jié)點(diǎn)是null，則不需要再尋找其左右子節(jié)點(diǎn)；
- 遍歷treeList，拼接二叉樹(shù)。
在剩余的父子關(guān)系集合treeList中尋找父節(jié)點(diǎn)是node.left的節(jié)點(diǎn)，進(jìn)行樹(shù)的再次拼接。
在剩余的父子關(guān)系集合treeList中尋找父節(jié)點(diǎn)是node.right的節(jié)點(diǎn)，進(jìn)行樹(shù)的再次拼接。
輸出符合條件的目錄ID。
六、Java算法源碼
public class OdTest04 {
static Node rootNode = null;
static int removeValue = 0;
// 剩余的目錄ID
static StringBuilder builder = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 父子關(guān)系表的長(zhǎng)度m
int m = Integer.valueOf(sc.nextLine());
// m個(gè)父子關(guān)系
List<int[]> treeList = new ArrayList<>();
for (int i = 0; i < m; i++) {
int[] treeArr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
if(treeArr[1] == 0){
rootNode = new Node(treeArr[0]);
// 拼接二叉樹(shù)根ID
builder.append(treeArr[0]).append(" ");
continue;
}
treeList.add(treeArr);
}
// 待刪除的ID
removeValue = Integer.valueOf(sc.nextLine());
/**
* 遍歷m個(gè)父子關(guān)系，拼接成二叉樹(shù)，拼接剩余的目錄ID
*/
dfs(treeList,rootNode);
builder.deleteCharAt(builder.length() - 1);
// 輸出符合條件的目錄ID
System.out.println(builder);
}
/**
* 深度優(yōu)先搜索dfs
* @param treeList
* @param node
*/
private static void dfs(List<int[]> treeList, Node node){
/**
* 如果剩余的父子關(guān)系集合treeList為0，則不需要再進(jìn)行dfs
* 如果要dfs的node節(jié)點(diǎn)是null，則不需要再尋找其左右子節(jié)點(diǎn)
*/
if(treeList.size() == 0 || node == null){
return;
}
for (int i = 0; i < treeList.size(); i++) {
// 父子關(guān)系
int[] treeArr = treeList.get(i);
// 如果該關(guān)系的父節(jié)點(diǎn)是value
if(treeArr[1] == node.value){
// 如果該父節(jié)點(diǎn)不是待移除的ID
if(removeValue != node.value) {
int sonValue = treeArr[0];
// 如果該子節(jié)點(diǎn)不是待移除的ID
if(removeValue != sonValue){
// 拼接成二叉樹(shù)
if(node.left == null){
node.left = new Node(sonValue);
}else if(node.right == null){
node.right = new Node(sonValue);
}
// 拼接剩余的目錄ID
builder.append(sonValue).append(" ");
}
}
// 移除滿足條件的父子關(guān)系
treeList.remove(treeArr);
// 父子關(guān)系集合treeList移除某節(jié)點(diǎn)，treeList長(zhǎng)度-1，下一個(gè)坐標(biāo)i也應(yīng)該-1
i--;
}
}
// 在剩余的父子關(guān)系集合treeList中尋找父節(jié)點(diǎn)是node.left的節(jié)點(diǎn)，進(jìn)行樹(shù)的再次拼接
dfs(treeList,node.left);
// 在剩余的父子關(guān)系集合treeList中尋找父節(jié)點(diǎn)是node.right的節(jié)點(diǎn)，進(jìn)行樹(shù)的再次拼接
dfs(treeList,node.right);
}
}七、效果展示
1、輸入
8
6 0
4 6
5 4
7 4
8 6
9 8
10 8
11 10
8
2、輸出
6 4 5 7
3、說(shuō)明
輸入可以組成二叉樹(shù)：
6
4 8
5 7 9 10
11刪除值為8的節(jié)點(diǎn)，變?yōu)? 4 5 7。
4、也許很多人會(huì)問(wèn)，如果節(jié)點(diǎn)的值相等，怎么辦？
8
6 0
4 6
5 4
5 4
5 6
5 5
10 5
11 10
5
5、輸出
6 4
6、說(shuō)明
輸入可以組成二叉樹(shù)：
6
4 5
5 5 5 10
11刪掉值為5的節(jié)點(diǎn)，變?yōu)? 4。
