一加Ace2 Pro官宣：普及16G內存 引領24G
一加官方今天繼續為本月發布的新機一加Ace2 Pro帶來預熱，公布了內存方面的信息。“淘汰 8GB ，12GB 起步，16GB 普及，24GB 引領，還有呢？#一加Ace2Pro#，2023 年 8 月，敬請期待。”同時
大家好，我是哪吒。
最近一直在刷算法題，刷華為OD算法題，有諸多好處：
希望用我自己瘋狂刷題的勁頭，感染大家，讓大家愛上刷題，順利通過華為OD機試，掌握更多優秀的算法。
下面這道題，是很經典的深度優先搜索dfs算法 + 二叉樹。掌握一道題，精通一類題，沖吧~
某文件系統中有N個目錄，每個目錄都有一個獨一無二的ID。每個目錄只有一個父目錄，但每個父目錄下可以有零個或者多個子目錄，目錄結構呈樹狀結構。
假設，根目錄的ID為0，且根目錄沒有父目錄，其他所有目錄的ID用唯一的正整數表示，并統一編號。
現給定目錄ID和其父目錄ID的對應父子關系表[子目錄ID，父目錄ID]，以及一個待刪除的目錄ID，請計算并返回一個ID序列，表示因為刪除指定目錄后剩下的所有目錄，返回的ID序列以遞增序輸出。
注意：
說人話就是：
輸入m行數據，第一個元素是子節點值，第二個是父節點值，m行數據可以組成一個二叉樹。
最后輸入要刪除的節點，求二叉樹剩下的節點值。
例如輸入：
5
8 6
10 8
6 0
20 8
2 6
8
二叉樹就會變為：
6
2 8
10 20
刪除最后的8，輸出6 2就是結果。
很簡單吧，少年~
輸入的第一行為父子關系表的長度m;
接下來的m行為m個父子關系對;
最后一行為待刪除的ID。序列中的元素以空格分割。
輸出一個序列，表示因為刪除指定目錄后，剩余的目錄ID。
如果搜索是以接近起始狀態的程序依次擴展狀態的，叫寬度優先搜索。
深度優先搜索用一個數組存放產生的所有狀態。
public int def(int x, int y ,int step){ if(遞歸出口/達到目標狀態){ //進行對應操作 return 0; } for (int i = 0; i < n; i++) { //遍歷剩下的所有的情況 if(visit[i]==0){ //未訪問 x = 下一步更新; y = 下一步更新; visit[i] = 1; def(x,y,step); visit[i] = 0; //記得回溯還原 } }}根據題目描述，輸入數據可以組成一個二叉樹，如果將某個節點刪除，求剩余節點。
輸入父子關系表的長度m。
接下來的m行輸入父子關系。
輸入待刪除的ID。
遍歷m個父子關系，拼接成二叉樹，拼接剩余的目錄ID。
在剩余的父子關系集合treeList中尋找父節點是node.left的節點，進行樹的再次拼接。
在剩余的父子關系集合treeList中尋找父節點是node.right的節點，進行樹的再次拼接。
輸出符合條件的目錄ID。
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); // 父子關系表的長度m int m = Integer.valueOf(sc.nextLine()); // m個父子關系 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]); // 拼接二叉樹根ID builder.append(treeArr[0]).append(" "); continue; } treeList.add(treeArr); } // 待刪除的ID removeValue = Integer.valueOf(sc.nextLine()); /** * 遍歷m個父子關系，拼接成二叉樹，拼接剩余的目錄ID */ dfs(treeList,rootNode); builder.deleteCharAt(builder.length() - 1); // 輸出符合條件的目錄ID System.out.println(builder); } /** * 深度優先搜索dfs * @param treeList * @param node */ private static void dfs(List<int[]> treeList, Node node){ /** * 如果剩余的父子關系集合treeList為0，則不需要再進行dfs * 如果要dfs的node節點是null，則不需要再尋找其左右子節點 */ if(treeList.size() == 0 || node == null){ return; } for (int i = 0; i < treeList.size(); i++) { // 父子關系 int[] treeArr = treeList.get(i); // 如果該關系的父節點是value if(treeArr[1] == node.value){ // 如果該父節點不是待移除的ID if(removeValue != node.value) { int sonValue = treeArr[0]; // 如果該子節點不是待移除的ID if(removeValue != sonValue){ // 拼接成二叉樹 if(node.left == null){ node.left = new Node(sonValue); }else if(node.right == null){ node.right = new Node(sonValue); } // 拼接剩余的目錄ID builder.append(sonValue).append(" "); } } // 移除滿足條件的父子關系 treeList.remove(treeArr); // 父子關系集合treeList移除某節點，treeList長度-1，下一個坐標i也應該-1 i--; } } // 在剩余的父子關系集合treeList中尋找父節點是node.left的節點，進行樹的再次拼接 dfs(treeList,node.left); // 在剩余的父子關系集合treeList中尋找父節點是node.right的節點，進行樹的再次拼接 dfs(treeList,node.right); }}8
6 0
4 6
5 4
7 4
8 6
9 8
10 8
11 10
8
6 4 5 7
輸入可以組成二叉樹：
6 4 85 7 9 10 11刪除值為8的節點，變為6 4 5 7。
8
6 0
4 6
5 4
5 4
5 6
5 5
10 5
11 10
5
6 4
輸入可以組成二叉樹：
6 4 55 5 5 10 11刪掉值為5的節點，變為6 4。
本文鏈接：http://www.www897cc.com/showinfo-26-39503-0.html刷了360多道算法題，我終于頓悟了它的真諦
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號