Tree Search Overview Tree Search is used to find a path from a start state to a goal state. Each node represents a state: A / | \ B C D /|\ | /\ E F G H I J The objective is to reach node J. 1. Breadth-First Search (BFS) Idea Explore nodes level by level. Level 0: A Level 1: B C D Level 2: E F G H I J Expansion order: A → B → C → D → E → F → G → H → I → J Uses a Queue (FIFO) . Advantages Finds shortest path in unweighted graphs. Complete. Disadvantages High memory consumption. 2. Depth-First Search (DFS) Idea Go as deep as possible before backtracking. Expansion order: A → B → E → F → G → C → H → D → I → J Uses a Stack (LIFO) . Advantages Low memory usage. Simple implementation. Disadvantages May miss the shortest path. Can get trapped in deep branches. 3. Best-First Search Idea Expand the node with the smallest heuristic value. h(n) where: h(n) = estimated distance to goal Example: Node h(n) B 1 D 3 C 6 ...

一、什麼是 Tree Search（樹狀搜尋）？ 在人工智慧（AI）與演算法中，許多問題都可以表示成一棵樹(圖一)： 起點(A) / | \ B C D /|\ | / \ E F G H I J 每個節點(Node)代表一種狀態(State)。 例如： 迷宮中的位置 棋局的盤面 路徑規劃中的城市 遊戲中的決策 搜尋演算法的目的： 從起點找到目標節點（Goal Node） 二、Breadth First Search (BFS) 核心思想 先搜尋離起點最近的節點。 一層一層往外擴展。 Level 0: A Level 1: B C D Level 2: E F G H I J 搜尋順序： A B C D E F G H I J 圖一結果： A → B → C → D → E → F → G → H → I → J 使用資料結構 Queue（佇列） FIFO： First In First Out 先進先出 例如： Queue: A 取出A 加入B,C,D Queue: B,C,D BFS特性 優點 如果邊權重相同： BFS一定找到最短路徑。 缺點 需要大量記憶體。 假設每個節點有10個子節點： 深度5： 10^5 = 100000 需要保存很多節點。 時間複雜度 O(V + E) V = Vertex（節點數） E = Edge（邊數） 三、Depth First Search (DFS) 核心思想 一路往下走到底。 不能走才回頭。 A | B | E 然後： A | B | F 搜尋順序 圖一結果： A B E F G C H D I J 使用資料結構 Stack（堆疊） LIFO Last In First Out 後進先出 例如： push(B) push(C) push(D) pop() => D DFS特性 優點 記憶體需求小。 只需保存： 目前路徑 即可。 缺點 可能找到很差的解。 例如： A ├── Goal └── 巨大子樹 DFS可能先跑完整個巨大子樹。 時間複雜度 O(V+E)...

題目原文描述  https://leetcode.com/problems/squares-of-a-sorted-array/ 中文描述 給定一個由小排到大的整數陣列 nums ，算出每個數字的平方，並由小排到大排序。 限制條件： 1 <= nums.length <= 10000 -10000 <= nums[i] <= 10000 範例一： 輸入 nums = [-4, -1, 0, 2, 3] 輸出 [0, 1, 4, 9, 16] 平方後 [16, 1, 0, 4, 9]，排序後 [0, 1, 4, 9, 16] 解法一： 算出每個數字平方後，再做排序。 Python Code class Solution :     def sortedSquares ( self , nums : List[ int ]) -> List[ int ]:         for i in range ( len (nums)):             nums[i] = nums[i] * nums[i]                 return sorted (nums) 解法二： 用兩個指標 left 與 right 分別指到陣列的開頭索引 0 與結束索引 len(nums) - 1。 maxIdx 為目前找到的最大值之索引位置。可參考底下動畫圖片 Python Code class Solution :     def sortedSquares ( self , nums : List[ int ]) -> List[ int ]:         res = [ 0 ] * len (nums) # 存放結果的陣列         right = len (nums) - 1 # 陣列結束索引         left = 0 # 陣列開頭索引  ...

題目原文描述  https://leetcode.com/problems/max-consecutive-ones/ 中文描述 給一個二進位陣列 nums ，找出最大連續出現 1 的次數。 範例一： 輸入 nums = [ 1, 1, 0, 0, 1, 1, 1, 1] 輸出 4 範例二： 輸入 nums = [ 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0] 輸出 3 解法： 使用一個變數 curOnes 紀錄目前連續出現 1 的次數，若目前的數字為 0 ，將 curOnes 歸零。 每次將 curOnes 加 1 時，與 maxOnes 比較，若 curOnes 比 maxOnes 大，則 maxOnes 等於 curOnes。 Python Code class Solution :     def findMaxConsecutiveOnes ( self , nums : List[ int ]) -> int :         curOnes = 0         maxOnes = 0         for n in nums:             if n == 0 :                 curOnes = 0                         curOnes += n             if curOnes > maxOnes:                     maxOnes = curOnes         return maxOnes ...

題目原文描述 https://leetcode.com/problems/ransom-note/ 中文描述 給定兩個字串 ransomNote 與 magazine。判斷 ransomNote 是否可由 magazine 中的英文字母所組成。 magazine 中的每一個英文字母只能使用一次。 範例一： 輸入 ransomNote = "c", magazine = "d" 輸出 false 範例二： 輸入 ransomNote = "bb", magazine = "bc" 輸出 false 範例三： 輸入 ransomNote = "aabc", magazine = "cbaa" 輸出 true 範例四： 輸入 ransomNote = "bb", magazine = "bcb" 輸出 true 解法一： 判斷 ransomNote 的一個字母是否有在 magazine 出現，若沒有輸出 false。 若有，則將此字母從 magazine 移除。 ransomNote 每個字母都判斷完畢後，即可輸出 true。 Python Code class Solution :     def canConstruct ( self , ransomNote : str , magazine : str ) -> bool :         for ch in ransomNote:             if ch not in magazine:                 return False                         magazine = magazine.replace(ch, '' , 1 )         return True 解法二： 使用 key 和 value 的資料結構 letterDic，將 magazine 的每個字...

題目原文描述  https://leetcode.com/problems/middle-of-the-linked-list/ 中文描述 指定一個單向鏈結串列 head，找出此鏈結串列的中間節點。如果有兩個中間節點(串列大小為偶數時)，請顯示第二個。 範例一： 輸入  head = [1, 3, 5, 7, 9] 輸出 [5, 7, 9] 因為 5 是中間節點。 範例二： 輸入  head = [1, 3, 5, 7, 9, 11] 輸出 [7, 9, 11] 因為 5 與 7 是中間節點，選擇第二個 7。 解法一： 用迴圈與掃過串列一次，算出串列大小 size， 之後再用從節點開頭逐一走訪至 size // 2 來找出中間節點。 Python Code # Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next class Solution :     def middleNode ( self , head : Optional[ListNode]) -> Optional[ListNode]:         size = 0         t = head         while t != None :             t = t.next             size += 1                 size = size // 2         i = 0   ...