[Day18] Binary Tree Traversal in Java

概念 原有樹 使用 DFS 深度優先處理左邊/右邊 左邊 DFS LEFT(常規) pre-order 馬上印 (5214367) in-order 左邊回來後印 (1234567) post-order 右邊回來後印 右邊 DFS RIGHT pre-order 馬上印 (5672431) in-order 右邊回來後印 (7654321) post-order 左邊回來後印 (7634125) BST 定義:左邊節點都會比原節點小,右邊則會比原節點大 -> validated 預先準備 public class BT_List { private Integer[] nums; private Node root; // 配置節點 public static class Node { public Node left; public Node right; public int val; public Node(){} public Node(int val) { this....

September 4, 2022 Â· 3 min Â· Yish

[Day17] Divide & Conquer(分治法) in Java

思路 使用河內塔作為練習 拆解大問題 -> 小問題 實作 測試方法 public class DivideConquer_Hanoi2 { //創建三個柱子 static Stack<Integer> pillar_A = new Stack<>(); static Stack<Integer> pillar_B = new Stack<>(); static Stack<Integer> pillar_C = new Stack<>(); public static void main(String[] args) { /** initialization **/ // 添加數字進去 //[1,2,3,4,5] pillar_A.add(5); pillar_A.add(4); pillar_A.add(3); pillar_A.add(2); pillar_A.add(1); int layer = pillar_A.size(); //5 /** Divide & Conquer **/ hanoi(layer, pillar_A, pillar_B, pillar_C); System.out.println(); } 具體 private static void hanoi(int layer, Stack<Integer> pillar_from, Stack<Integer> pillar_mid, Stack<Integer> pillar_to) { // 相對位置 //改變觀看視角 不是以變數名稱作絕對位置 而是以當下傳入為主 if (layer == 0) return; // 沒東西可以用了 /** base case : when layer == 1, it's our base case **/ /** step01: move the above plate to the pillar_mid, to clear the room for the plate below **/ // 把上面盤子拿出來 把來源盤子移到中間 hanoi(layer - 1, pillar_from, pillar_to, pillar_mid); /** step02: main target **/ // 出現 base -> layer=1 Integer plate = pillar_from....

August 26, 2022 Â· 1 min Â· Yish

[Day16] Branch and Bound(分支界線[回溯法優化]) in Java

思路 優化回溯法 會挑選當下最佳路徑 如果當前時數已經超過最佳時數則馬上回頭 實作 測試方法 import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; public class Travelplan_branchbound_new { Integer[][] hours; String[] c_remained = new String[]{"NP", "IS", "CA", "UK", "US"}; private void build_hour_table() { // NP: 0 (North Pole) // IS: 1 // CA: 2 // UK: 3 // US: 4 this.hours = new Integer[5][5]; hours[0][0] = 0; // NP -> NP hours[0][1] = 14; // NP -> IS hours[0][2] = 15; // NP -> CA hours[0][3] = 17; // NP -> UK hours[0][4] = 16; // NP -> US hours[1][0] = 14; // IS -> NP hours[1][1] = 0; // IS -> IS hours[1][2] = 24; // IS -> CA hours[1][3] = 8; // IS -> UK hours[1][4] = 36; // IS -> US hours[2][0] = 15; // CA -> NP hours[2][1] = 24; // CA -> IS hours[2][2] = 0; // CA -> CA hours[2][3] = 34; // CA -> UK hours[2][4] = 4; // CA -> US hours[3][0] = 17; // UK -> NP hours[3][1] = 8; // UK -> IS hours[3][2] = 34; // UK -> CA hours[3][3] = 0; // UK -> UK hours[3][4] = 30; // UK -> US hours[4][0] = 16; // US -> NP hours[4][1] = 36; // US -> IS hours[4][2] = 4; // US -> CA hours[4][3] = 30; // US -> UK hours[4][4] = 0; // US -> US } public Integer get_hour(String start, String end) { Integer x = get_index(start); Integer y = get_index(end); return this....

August 25, 2022 Â· 4 min Â· Yish

[Day15] Backtracking(回溯法[枚舉優化]) in Java

思路 優化枚舉法 如果過程當中已經超過預期時數則馬上結束不再做運算 實作 測試方法 import java.util.ArrayList; import java.util.List; public class Travelplan_backtracking_new { Integer[][] hours; // 配置國家 String[] c_remained = new String[]{"NP", "IS", "CA", "UK", "US"}; //5 // 測試案例 public static void main(String[] args) { Travelplan_backtracking_new tp = new Travelplan_backtracking_new(); tp.build_hour_table(); Integer hour_constraint = 60; // 65 ~ 100, 目標低於這個時數 tp.backtracking(hour_constraint); } // 建立行程時間 private void build_hour_table() { // NP: 0 (North Pole) // IS: 1 // CA: 2 // UK: 3 // US: 4 this....

August 21, 2022 Â· 3 min Â· Yish

[Day14] Enumeration(枚舉) in Java

思路 所有可能性都進行拜訪 排除出發點 實作 測試方法 import java.util.ArrayList; import java.util.List; public class Travelplan_enum_new { Integer[][] hours; // 配置國家 String[] c_remained = new String[]{"NP", "IS", "CA", "UK", "US"}; //5 // 測試案例 public static void main(String[] args) { Travelplan_enum_new tp = new Travelplan_enum_new(); tp.build_hour_table(); Integer hour_constraint = 60; // 65 ~ 100, 目標低於這個時數 tp.enumeration(hour_constraint); } // 建立行程時間 private void build_hour_table() { // NP: 0 (North Pole) // IS: 1 // CA: 2 // UK: 3 // US: 4 this....

August 21, 2022 Â· 3 min Â· Yish

[Day13] Greedy(貪婪) in Java

思路 最低成本 BFS 廣度優先搜尋 Breadth-First Search (最佳解) 實作 測試方法 public static void main(String[] args) { Integer[][] maze = new Integer[][] { {1,3,1,2,9}, {7,3,4,9,9}, {1,7,5,5,3}, {2,3,4,2,5}, }; Greedy_Maze_Cost_A gmc = new Greedy_Maze_Cost_A(maze); int row_start = 0; int col_start = 0; //起始位置 int row_target = 3; int col_target = 4; //目標位置 int cost_min = gmc.go_maze(row_start, col_start, row_target, col_target); System.out.println(); } public class Greedy_Maze_Cost_A { Integer[][] maze; // cost lookup table PriorityQueue<Node> pq; // explored nodes (sort by cost) Integer[][] maze_best; // unexplored nodes (null) + confirmed nodes // 節點初始化 row欄, col列, cost static class Node { Integer row; Integer col; Integer cost; public Node(Integer row, Integer col) { this....

August 15, 2022 Â· 2 min Â· Yish