[Day21] Quick Sort

分析 由小到大排列 挑出 pivot 元素 與最後一個元素交換,為了之後操作時不會影響到 比較後發現不符合 pivot 規則 -> 停止換邊跑 另一邊執行一樣發現不符合 pivot 規則 -> 與剛不符合進行交換 左右兩邊 index 指到同一元素 -> 回合結束 觀看指向元素是否大於 pivot 元素,大於則進行交換 分支 挑出 pivot 元素 重複 4, 5, 6, 7 步驟 換右邊執行 符合規則: 左邊小於 pivot 右邊大於 pivot 但如果發現左右兩邊都皆小於 pivot -> 不做任何交換 分支...

September 10, 2022 Â· 3 min Â· Yish

[Day20] Same Tree

100. Same Tree 思路 全輪尋檢查每個節點都為一致 如果有一個不同則立即返回 false 實作 public class Solution { // 配置節點 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } //傳入樹節點 public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; //7....

September 9, 2022 Â· 1 min Â· Yish

[Day19] Unsorted Array to binary tree(DFS)

概念 將 unsorted array 轉換為 binary tree,並用深度優先(DFS)遍歷。 left node: (i+1) * 2 right node: (i+1) * 2 + 1 parent node: (i+1) / 2 level: log(i+1) 實作 package com.BT; import java.util.LinkedList; import java.util.Queue; public class BT_Array { private Integer[] nums; // 傳入陣列,用不同視角看陣列 -> 二元樹 public BT_Array(Integer[] nums) { this.nums = nums; } /** DFS left **/ public void traverse_preorder() { if (this.nums.length < 0) return; // 無陣列內容 int i_root = 0; // 預設開頭 if (this....

September 8, 2022 Â· 3 min Â· Yish

[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