《面試官問完，開AI回答》PHP 工程師的 LeetCode 刷題解構與模式化思考(二)

除了已提到的這些主題和經典題目，還有一些在 LeetCode 上非常常見且在技術面試中經常出現的演算法和資料結構模式。以下幾個領域也值得深入學習和筆記：

---

雙指針 (Two Pointers) ✌️

雙指針是一種常用的演算法技巧，通常用於處理陣列或鍊結串列。它使用兩個指針（通常是從兩端向中間移動，或同向移動）來遍歷資料結構，以減少時間複雜度。這種方法在處理排序過的資料時尤其有效，因為它可以利用資料的有序性。

搭配例題１｜ (167) Two Sum II - Input Array Is Sorted

問題描述

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

給定一個已按非遞減順序排序的 1 索引整數陣列 numbers，找出兩個數字，使其加起來等於特定的目標數字 target。讓這兩個數字為 numbers[index1] 和 numbers[index2]，其中 1 <= index1 < index2 <= numbers.length。

以長度為 2 的整數陣列 [index1, index2] 形式返回這兩個數字的索引（索引加 1）。

測試會產生一個確切的解。你不能重複使用同一個元素。

你的解法必須只使用常數額外空間。

Example 1:

Input: numbers = [2,7,11,15], target = 9

Output: [1,2]

Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6

Output: [1,3]

Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

解題思路

這題是經典的「Two Sum」問題的變種，但關鍵在於輸入陣列已經排序，並且要求常數額外空間。這就排除了使用雜湊表（會需要 O(n) 空間）的經典 Two Sum 解法。此時，雙指針技術就成為最佳選擇。

雙指針演算法步驟：

1. 初始化指針：

   • 設 left 指針指向陣列的開頭（索引 0）。

   • 設 right 指針指向陣列的末尾（索引 count(numbers) - 1）。

2. 迴圈遍歷： 進入一個 while 迴圈，條件是 left < right（當兩個指針相遇或交叉時，表示所有可能的組合都已檢查完畢）。

3. 計算當前和： 計算 current_sum = numbers[left] + numbers[right]。

4. 比較與移動指針：

   • 如果 current_sum == target： 表示找到了符合條件的兩個數字。返回它們的索引（注意題目要求返回的是 1-based 索引，所以需要將 left 和 right 都加 1）。

   • 如果 current_sum < target： 表示當前和太小了。由於陣列是排序的，為了使和變大，我們需要增加較小的那個數。因此，將 left 指針向右移動一位 (left++)。

   • 如果 current_sum > target： 表示當前和太大了。為了使和變小，我們需要減少較大的那個數。因此，將 right 指針向左移動一位 (right--)。

為什麼雙指針有效？

這種方法之所以有效，是因為陣列已排序。當 current_sum < target 時，如果我們移動 right 指針向左，和只會更小，更不可能達到 target；而移動 left 指針向右，則有機會找到更大的和。同理，當 current_sum > target 時，移動 left 指針向右會使和更大，而移動 right 指針向左則有機會使和變小。這樣，我們每次都能有效地縮小搜尋範圍。

時間複雜度： O(N)，其中 N 是陣列的長度。因為兩個指針從兩端向中間移動，最多遍歷整個陣列一次。

空間複雜度： O(1)，因為我們只使用了幾個指針變數，沒有額外的儲存空間。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $left = 0; // 左指針，初始化為陣列的起始索引 (0-based)
        $right = count($numbers) - 1; // 右指針，初始化為陣列的結束索引 (0-based)

        // 當左指針在右指針左側時，持續遍歷
        while ($left < $right) {
            $current_sum = $numbers[$left] + $numbers[$right]; // 計算當前兩個數字的和

            if ($current_sum == $target) {
                // 如果和等於目標值，找到答案。
                // 題目要求返回 1-based 索引，所以將 left 和 right 都加 1
                return [$left + 1, $right + 1];
            } elseif ($current_sum < $target) {
                // 如果和太小，需要增加總和，移動左指針向右
                $left++;
            } else {
                // 如果和太大，需要減少總和，移動右指針向左
                $right--;
            }
        }

        // 根據題目「每個輸入都只有一個確切的解」，所以理論上不會執行到這裡
        return []; 
    }
}
?>

---

滑動窗口 (Sliding Window) 🚪

滑動窗口是一種常用的演算法模式，通常用於解決陣列或字串中涉及子陣列（或子字串）的問題。它透過維護一個「窗口」在資料上滑動，動態調整窗口的大小（擴大或縮小），從而有效地遍歷所有符合特定條件的子序列，避免冗餘計算。

搭配例題１｜ (209) Minimum Size Subarray Sum

問題描述

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

給定一個正整數陣列 nums 和一個正整數 target，返回和大於或等於 target 的子陣列的最小長度。如果不存在這樣的子陣列，則返回 0。

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]

Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]

Output: 0

解題思路

這是一個典型的滑動窗口問題。我們需要找到一個和 >= target 的最短子陣列。

1. 初始化：

   • left (窗口左邊界指針) = 0

   • current_sum (當前窗口內元素的和) = 0

   • min_length (記錄最小長度) = 無限大 (例如 PHP_INT_MAX)

2. 擴大窗口 (右指針 right 移動)：

   • 遍歷陣列，right 指針從 0 開始向右移動，將 nums[right] 加入 current_sum。

3. 縮小窗口 (左指針 left 移動)：

   • 當 current_sum >= target 時，表示當前窗口內的和已經滿足條件。此時：

     • 更新 min_length = min(min_length, right - left + 1) (計算當前窗口的長度並更新最小長度)。

     • 從 current_sum 中減去 nums[left]，然後將 left 指針向右移動一位 (left++)。

     • 持續縮小窗口，直到 current_sum < target 為止，這樣我們才能找到更短的子陣列。

4. 返回結果：

   • 迴圈結束後，如果 min_length 仍然是無限大，表示沒有找到符合條件的子陣列，返回 0。

   • 否則，返回 min_length。

時間複雜度： O(N)，其中 N 是陣列的長度。雖然有兩個巢狀迴圈（外層 for 迴圈控制 right，內層 while 迴圈控制 left），但 left 和 right 指針都只會從陣列的開始移動到結束一次，每個元素最多被加一次和減一次。

空間複雜度： O(1)，只使用了常數額外的變數。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer $target
     * @param Integer[] $nums
     * @return Integer
     */
    function minSubArrayLen($target, $nums) {
        $n = count($nums);
        $left = 0; // 窗口的左邊界指針
        $current_sum = 0; // 當前窗口內的元素總和
        $min_length = PHP_INT_MAX; // 記錄最小長度，初始化為最大整數

        // 右指針 right 遍歷整個陣列，擴大窗口
        for ($right = 0; $right < $n; $right++) {
            $current_sum += $nums[$right]; // 將當前元素加入總和

            // 當窗口內的總和達到或超過目標值時，嘗試縮小窗口並更新最小長度
            while ($current_sum >= $target) {
                // 計算當前窗口的長度
                $current_window_length = $right - $left + 1;
                // 更新最小長度
                $min_length = min($min_length, $current_window_length);

                // 從總和中減去左邊的元素，並移動左指針向右
                $current_sum -= $nums[$left];
                $left++;
            }
        }

        // 如果 min_length 仍然是初始的最大值，表示沒有找到符合條件的子陣列
        return ($min_length === PHP_INT_MAX) ? 0 : $min_length;
    }
}
?>

---

貪婪演算法 (Greedy Algorithm) 💰

貪婪演算法是一種在每一步選擇中都採取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是全局最優的演算法策略。它不考慮未來的後果，只關注眼前的最優解。貪婪演算法並非適用於所有問題，但對於某些問題，它能提供簡單且高效的解決方案。

搭配例題１｜ (121) Best Time to Buy and Sell Stock¹

問題描述²

You are given an array prices where prices[i] is the price of a given stock on the ith day.³

You want to maximize your profit by choosing a single day to buy one st⁴ock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

給你一個陣列 prices，其中 prices[i] 是給定股票在第 i 天的價格。

你想要透過選擇某一天買入一支股票，並在未來的另一天賣出該股票來最大化你的利潤。

返回你可以從這筆交易中獲得的最大利潤。如果你無法獲得任何利潤，返回 0。

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transactions are done, and the max profit = 0.

解題思路

這是一個典型的貪婪演算法問題。我們需要找到最小的買入價格，以及其之後的最大賣出價格，使得利潤最大化。

其貪婪策略是：在遍歷 prices 陣列時，始終維護一個迄今為止遇到的最低買入價格，並用這個最低買入價格去計算當前可能的最大利潤。

1. 初始化：

   • min_price：初始化為一個極大的值（例如 PHP_INT_MAX），表示迄今為止的最低買入價格。

   • max_profit：初始化為 0，表示迄今為止的最大利潤。

2. 遍歷價格： 遍歷 prices 陣列中的每一個 price。

   • 更新最低買入價格： min_price = min(min_price, price)。在任何一天，我們都希望以最低的價格買入。

   • 計算當前利潤並更新最大利潤： max_profit = max(max_profit, price - min_price)。我們用當前的 price 減去迄今為止的 min_price 來計算潛在利潤，並用這個潛在利潤來更新 max_profit。這個邏輯確保了買入發生在賣出之前。

3. 返回結果： 遍歷結束後，max_profit 中儲存的值就是最大利潤。如果沒有利潤（即 max_profit 仍為 0），則返回 0。

時間複雜度： O(N)，其中 N 是 prices 陣列的長度。我們只需要遍歷陣列一次。

空間複雜度： O(1)，只使用了常數額外的變數。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $min_price = PHP_INT_MAX; // 追蹤到目前為止的最低買入價格
        $max_profit = 0;          // 追蹤到目前為止的最大利潤

        // 遍歷每一天的股票價格
        foreach ($prices as $price) {
            // 更新最低買入價格：選擇當前價格和歷史最低價格中的較小值
            $min_price = min($min_price, $price);
            
            // 計算如果今天賣出能獲得的利潤 (當前價格 - 最低買入價格)
            $current_profit = $price - $min_price;
            
            // 更新最大利潤：選擇當前利潤和歷史最大利潤中的較大值
            $max_profit = max($max_profit, $current_profit);
        }

        return $max_profit; // 返回最大利潤
    }
}
?>

---

堆疊 / 佇列 (Stack / Queue) 🗂️

堆疊（Stack）和佇列（Queue）是兩種最基本的線性資料結構。

• 堆疊 遵循「後進先出」（LIFO: Last In, First Out）原則，類似於一疊盤子。主要操作是 push（壓入）和 pop（彈出）。

• 佇列 遵循「先進先出」（FIFO: First In, First Out）原則，類似於排隊。主要操作是 enqueue（入隊）和 dequeue（出隊）。

  它們在演算法中廣泛應用於遍歷（如樹的層次遍歷）、表達式求值、回溯、任務排程等。

搭配例題１｜ (20) Valid Parentheses

問題描述

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

給定一個只包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s，判斷輸入字串是否有效。

有效字串需滿足：

1. 開括號必須由相同類型的括號閉合。

2. 開括號必須以正確的順序閉合。

3. 每個閉括號都有一個相同類型的對應開括號。

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

解題思路

這是一個典型的使用堆疊 (Stack) 來解決的問題。堆疊的 LIFO 特性非常適合處理括號的配對問題：當遇到一個開括號時，我們將它「推入」堆疊；當遇到一個閉括號時，我們期望堆疊頂部是與其匹配的開括號。

演算法步驟：

1. 初始化：

   • 創建一個空的堆疊 stack（在 PHP 中可以用陣列模擬，使用 array_push 和 array_pop）。

   • 創建一個映射表 map，將每個閉括號對應到其匹配的開括號。例如：')' => '(', '}' => '{', ']' => '['。

2. 遍歷字串： 逐一檢查字串 s 中的每個字元 char。

   • 如果 char 是開括號（'(', '{', '['）：

     • 將 char 推入堆疊。

   • 如果 char 是閉括號（')', '}', ']'）：

     • 檢查堆疊是否為空： 如果此時堆疊為空，表示沒有對應的開括號，則字串無效，返回 false。

     • 彈出堆疊頂部元素： 從堆疊中彈出最頂部的元素 top_element。

     • 檢查是否匹配： 檢查 top_element 是否與 map[char] 相等（即是否為匹配的開括號）。如果不相等，則括號順序不正確，字串無效，返回 false。

3. 最終檢查：

   • 字串遍歷結束後，如果堆疊仍然不為空，表示有些開括號沒有被閉合，則字串無效，返回 false。

   • 如果堆疊為空，表示所有括號都已正確配對，字串有效，返回 true。

時間複雜度： O(N)，其中 N 是字串的長度。因為我們只遍歷字串一次，並且堆疊操作（push, pop, isEmpty）的時間複雜度為 O(1)。

空間複雜度： O(N)，在最壞情況下（例如 ((((((），堆疊會儲存所有開括號。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        $stack = []; // 使用 PHP 陣列模擬堆疊
        // 映射表：閉括號對應其匹配的開括號
        $map = [
            ')' => '(',
            '}' => '{',
            ']' => '['
        ];

        // 遍歷字串中的每個字元
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];

            // 如果是開括號，推入堆疊
            if ($char === '(' || $char === '{' || $char === '[') {
                array_push($stack, $char);
            } 
            // 如果是閉括號
            else {
                // 如果堆疊為空，表示沒有匹配的開括號
                if (empty($stack)) {
                    return false;
                }
                // 從堆疊中彈出頂部元素
                $top_element = array_pop($stack);
                // 檢查彈出的元素是否與當前閉括號的匹配開括號一致
                if ($top_element !== $map[$char]) {
                    return false; // 不匹配，無效
                }
            }
        }

        // 遍歷結束後，如果堆疊為空，表示所有括號都已正確配對
        return empty($stack);
    }
}
?>

---

圖論基礎 (Graph Basics) 🗺️

圖（Graph）是一種由頂點（或節點）和邊組成的資料結構，用於表示物件之間的關係。圖論是研究圖的數學分支，而圖演算法則是處理圖的演算法，例如遍歷（DFS/BFS）、尋找最短路徑、最小生成樹等。許多現實世界的問題都可以建模為圖問題，如社交網路、交通網路等。

搭配例題１｜ (200) Number of Islands

問題描述

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

給定一個 m x n 的二進位網格 grid，它表示地圖，其中 '1' 代表陸地，'0' 代表水。返回島嶼的數量。

一個島嶼被水環繞，並由水平或垂直連接的相鄰陸地（'1'）形成。你可以假設網格的所有四條邊都被水環繞。

Example 1:

Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

Output: 1

Example 2:

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

Output: 3

解題思路

這是一個經典的圖遍歷問題，可以用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 來解決。將網格中的每個 '1' 視為圖中的一個節點，相鄰的 '1' 之間有邊。一個島嶼就是一個連通分量。

基本思想：

遍歷網格中的每個單元格。如果遇到一個 '1'，這表示我們找到了一個新的島嶼的一部分。然後，以這個 '1' 為起點，使用 DFS 或 BFS 遍歷這個島嶼的所有相連的陸地單元格，並將它們標記為已訪問（例如，將 '1' 改為 '0'），以避免重複計算。每當我們找到一個新的未訪問的 '1'，就將島嶼計數器加一。

方法一：深度優先搜尋 (DFS)

1. 初始化：

   • num_islands (島嶼計數器) = 0。

   • 獲取網格的維度 rows 和 cols。

2. 遍歷網格： 使用兩個巢狀迴圈遍歷 grid[r][c] 的每個單元格。

   • 如果 grid[r][c] 是 '1'：

     • 將 num_islands 加 1。

     • 呼叫一個輔助 DFS 函式，從 (r, c) 開始探索並「沉沒」整個島嶼（即將所有相連的 '1' 變為 '0'）。

3. 輔助 DFS 函式 dfs(grid, r, c)：

   • 邊界條件： 如果 r 或 c 超出網格範圍，或者 grid[r][c] 是 '0'（水或已訪問的陸地），則返回。

   • 標記已訪問： 將 grid[r][c] 設為 '0'。

   • 遞迴探索相鄰陸地： 遞迴呼叫 dfs 探索其四個方向的鄰居：

     • dfs(grid, r + 1, c) (下)

     • dfs(grid, r - 1, c) (上)

     • dfs(grid, r, c + 1) (右)

     • dfs(grid, r, c - 1) (左)

時間複雜度： O(RowstimesCols)。每個單元格最多被訪問一次。

空間複雜度： O(RowstimesCols)，在最壞情況下（整個網格都是陸地且是斜線或Z字形連接），遞迴堆疊的深度可能達到整個網格的大小。

方法二：廣度優先搜尋 (BFS)

1. 初始化：

   • num_islands = 0。

   • 獲取網格的維度 rows 和 cols。

2. 遍歷網格： 使用兩個巢狀迴圈遍歷 grid[r][c] 的每個單元格。

   • 如果 grid[r][c] 是 '1'：

     • 將 num_islands 加 1。

     • 創建一個佇列 queue。

     • 將 [r, c] 放入佇列。

     • 將 grid[r][c] 設為 '0'（標記為已訪問）。

     • 進入 BFS 迴圈。

3. BFS 迴圈： 當佇列不為空時：

   • 從佇列中取出一個單元格 [row, col]。

   • 定義四個方向的位移量 directions = [[1,0], [-1,0], [0,1], [0,-1]]。

   • 遍歷四個方向：

     • 計算鄰居的座標 (nr, nc)。

     • 檢查有效性： 如果 (nr, nc) 在網格範圍內且 grid[nr][nc] 是 '1'：

       • 將 grid[nr][nc] 設為 '0'（標記為已訪問）。

       • 將 [nr, nc] 放入佇列。

時間複雜度： O(RowstimesCols)。每個單元格最多被訪問一次。

空間複雜度： O(min(Rows,Cols))，在最壞情況下（島嶼形成一個大的矩形），佇列的大小可能與網格的最小邊長相關。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid) {
        $rows = count($grid);
        if ($rows === 0) {
            return 0;
        }
        $cols = count($grid[0]);
        $num_islands = 0;

        // 遍歷整個網格
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                // 如果找到陸地 '1'，表示找到一個新島嶼
                if ($grid[$r][$c] === '1') {
                    $num_islands++; // 島嶼計數器加一
                    // 從當前陸地開始，使用 DFS 將整個島嶼「沉沒」（標記為 '0'）
                    $this->dfs($grid, $r, $c, $rows, $cols);
                }
            }
        }

        return $num_islands;
    }

    /**
     * DFS 輔助函式，用於探索並標記島嶼的所有部分
     * @param String[][] $grid 網格
     * @param Integer $r 當前行索引
     * @param Integer $c 當前列索引
     * @param Integer $rows 網格總行數
     * @param Integer $cols 網格總列數
     */
    private function dfs(&$grid, $r, $c, $rows, $cols) {
        // 邊界條件：
        // 1. 超出網格範圍
        // 2. 當前單元格是水 ('0')
        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols || $grid[$r][$c] === '0') {
            return;
        }

        // 將當前陸地標記為水 ('0')，表示已訪問，避免重複計算
        $grid[$r][$c] = '0';

        // 遞迴探索四個方向的鄰居
        $this->dfs($grid, $r + 1, $c, $rows, $cols); // 下
        $this->dfs($grid, $r - 1, $c, $rows, $cols); // 上
        $this->dfs($grid, $r, $c + 1, $rows, $cols); // 右
        $this->dfs($grid, $r, $c - 1, $rows, $cols); // 左
    }


    /**
     * BFS 解法 (使用佇列)
     * @param String[][] $grid
     * @return Integer
     */
    function numIslandsBFS($grid) {
        $rows = count($grid);
        if ($rows === 0) {
            return 0;
        }
        $cols = count($grid[0]);
        $num_islands = 0;

        // 定義四個方向的位移量
        $directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

        // 遍歷整個網格
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] === '1') {
                    $num_islands++; // 發現一個新島嶼
                    $grid[$r][$c] = '0'; // 立即將其標記為已訪問 (水)

                    $queue = [[$r, $c]]; // 創建佇列並將當前陸地加入

                    // BFS 遍歷相連的陸地
                    while (!empty($queue)) {
                        list($curr_r, $curr_c) = array_shift($queue); // 從佇列取出當前座標

                        // 探索四個方向的鄰居
                        foreach ($directions as $dir) {
                            $next_r = $curr_r + $dir[0];
                            $next_c = $curr_c + $dir[1];

                            // 檢查鄰居是否在網格內，且是未訪問的陸地
                            if ($next_r >= 0 && $next_r < $rows && 
                                $next_c >= 0 && $next_c < $cols && 
                                $grid[$next_r][$next_c] === '1') {
                                
                                $grid[$next_r][$next_c] = '0'; // 標記為已訪問 (水)
                                array_push($queue, [$next_r, $next_c]); // 將鄰居加入佇列
                            }
                        }
                    }
                }
            }
        }

        return $num_islands;
    }
}
?>

---

回溯法 (Backtracking) 🔄

回溯法（Backtracking）是一種窮舉搜索的演算法，用於在所有可能的候選解中尋找一個或多個解。它通常用於解決約束滿足問題和組合優化問題。回溯法本質上是一種深度優先搜尋 (DFS)，它在搜尋過程中如果發現當前路徑無法導向有效解，就會「回溯」到上一個決策點，嘗試其他的選擇。

搭配例題１｜ (46) Permutations

問題描述

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

給定一個包含不同整數的陣列 nums，返回所有可能的全排列。你可以按任何順序返回答案。

Example 1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]

Output: [[0,1],[1,0]]

解題思路

這是一個典型的使用回溯法來解決的問題。回溯法通常涉及遞迴。我們要找到所有可能的排列，這意味著我們需要嘗試所有可能的數字組合。

回溯法演算法步驟：

1. 定義輔助遞迴函式： 創建一個輔助函式，例如 backtrack(current_permutation, remaining_elements, result)。

   • current_permutation：目前已經建立的部分排列。

   • remaining_elements：還沒有被放入當前排列的數字。

   • result：儲存所有完整排列的最終列表。

2. 基本情況 (Base Case)：

   • 如果 remaining_elements 為空（或者說 current_permutation 的長度等於原始 nums 的長度），表示已經形成了一個完整的排列。將 current_permutation 加入 result 列表，然後返回。

3. 遞迴步驟 (Recursive Step)：

   • 遍歷 remaining_elements 中的每一個數字 num。

   • 選擇：

     • 將 num 從 remaining_elements 中移除，並將它添加到 current_permutation 的末尾。

   • 遞迴： 呼叫 backtrack 函式，傳入更新後的 current_permutation 和 remaining_elements。

   • 撤銷選擇（回溯）： 遞迴呼叫返回後，需要將 num 從 current_permutation 中移除，並將它放回 remaining_elements。這一步是回溯法的核心，它確保我們探索了所有可能性，並在探索完一個分支後恢復到之前的狀態，以便嘗試其他分支。

時間複雜度： O(NtimesN)。

• N 是所有可能排列的數量（每個排列的深度都是 N）。

• 每個排列的形成過程，在每個節點上需要進行 O(N) 的操作（例如在陣列中移除元素或檢查是否已使用）。

  空間複雜度： O(N)。主要用於遞迴呼叫堆疊的深度（最大為 N）和儲存單個排列的臨時空間。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        $result = []; // 儲存所有完整排列的最終結果
        $n = count($nums);
        
        // 如果輸入陣列為空，則沒有排列，返回空陣列
        if ($n === 0) {
            return $result;
        }

        // 輔助遞迴函式
        // $current_permutation: 目前已經形成的部分排列
        // $used: 追蹤哪些數字已經被使用過 (索引為鍵，boolean 為值)
        // $nums: 原始數字陣列
        // $result: 引用傳遞，用於儲存所有完整排列
        $this->backtrack([], array_fill(0, $n, false), $nums, $result);

        return $result;
    }

    private function backtrack(&$current_permutation, &$used, $nums, &$result) {
        // 基本情況: 如果當前排列的長度等於原始數字陣列的長度，則表示形成了一個完整的排列
        if (count($current_permutation) === count($nums)) {
            $result[] = $current_permutation; // 將完整排列加入結果列表
            return;
        }

        // 遞迴步驟: 遍歷所有可能的數字
        for ($i = 0; $i < count($nums); $i++) {
            // 如果當前數字已經被使用過，則跳過
            if ($used[$i]) {
                continue;
            }

            // 選擇: 將數字加入當前排列，並標記為已使用
            $current_permutation[] = $nums[$i];
            $used[$i] = true;

            // 遞迴: 探索下一個位置
            $this->backtrack($current_permutation, $used, $nums, $result);

            // 撤銷選擇 (回溯): 移除當前數字，並將其標記為未使用，以便嘗試其他分支
            array_pop($current_permutation);
            $used[$i] = false;
        }
    }
}
?>

堆積 / 優先佇列 (Heap / Priority Queue) ⛰️

堆積（Heap），或稱優先佇列（Priority Queue），是一種特殊的樹狀資料結構，它滿足堆積性質：在最大堆積中，父節點的值總是大於或等於其子節點的值；在最小堆積中，父節點的值總是小於或等於其子節點的值。這使得堆積非常適合快速找到集合中的最大或最小元素（O(1) 查找），以及高效地插入和刪除元素（O(logN)）。在 PHP 中，可以使用 SplMinHeap 或 SplMaxHeap 類來實現。

搭配例題１｜ (215) Kth Largest Element in an Array

問題描述¹

Given an integer array nums and an integer k, return the kth largest element in the array.²

Note that it is the kth largest element in the sorted order, not the kth distinct element.³

You must solve it in ⁴O(n) time comple⁵xity.

給定一個整數陣列 nums 和一個整數 k，返回陣列中第 k 個最大的元素。

請注意，這是指在排序後的順序中的第 k 個最大元素，而不是第 k 個不同的元素。

你必須在 O(n) 的時間複雜度內解決這個問題。

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2

Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4

Output: 4

解題思路

找到陣列中第 k 個最大的元素，有幾種常見方法：

方法一：排序 (Sorting)

最直接的方法是對整個陣列進行排序，然後取第 n - k 個元素（如果陣列長度為 n，且按升序排序）。

時間複雜度：O(NlogN) (取決於排序演算法)。

空間複雜度：O(logN) 或 O(N) (取決於排序演算法)。

缺點： 題目要求 O(N) 時間複雜度，所以這個方法不夠優化。

方法二：使用最小堆積 (Min-Heap / Priority Queue)

這個方法是解決「Top K」問題的標準做法，且能達到題目要求的時間複雜度。

1. 建立一個大小為 k 的最小堆積 (Min-Heap)。

2. 遍歷陣列 nums：

   • 對於每個數字 num：

     • 將 num 加入堆積。

     • 如果堆積的大小超過 k，則從堆積中移除最小的元素（即堆積的根）。

3. 返回結果： 遍歷完所有數字後，堆積的根（即堆積中最小的元素）就是陣列中第 k 個最大的元素。

為什麼這樣有效？

最小堆積會始終保留著它所處理過的所有數字中最大的 k 個。如果新來的數字比堆積中的最小元素還小，它就不可能是前 k 大的元素之一，因此不會被保留；如果新來的數字比堆積中的最小元素大，它就會取代堆積中的最小元素，確保堆積始終持有前 k 大的元素。最終，堆積的根就是這 k 個元素中最小的一個，也就是整體第 k 大的元素。

時間複雜度： O(NlogK)。每個數字被處理一次（N 次），每次操作（插入、刪除最小）需要 O(logK) 時間，因為堆積的大小最大為 k。如果 k 遠小於 N，這會接近 O(N)。在最壞情況下 k 接近 N，時間複雜度是 O(NlogN)。但通常面試會默認這是在 O(N) 範疇內。

空間複雜度： O(K)，用於儲存堆積。

方法三：快速選擇 (Quickselect)

快速選擇演算法是基於快速排序思想的一種選擇演算法，它能在平均 O(N) 時間複雜度內找到陣列中的第 k 小/大元素。

時間複雜度： 平均 O(N)，最壞 O(N2)（但透過隨機選擇軸心等優化可以避免最壞情況）。

空間複雜度： O(1) （原地操作，不考慮遞迴堆疊）。

備註： 雖然快速選擇是理論上最優解，但實現起來比堆積複雜，且面試中通常接受堆積解法。題目若明確要求 O(N) 且面試官允許，則可考慮實現。這裡提供堆積解。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function findKthLargest($nums, $k) {
        // 創建一個最小堆積 (Min-Heap)
        // PHP 的 SplMinHeap 預設就是最小堆積
        $minHeap = new SplMinHeap();

        // 遍歷陣列中的每個數字
        foreach ($nums as $num) {
            // 將數字加入堆積
            $minHeap->insert($num);

            // 如果堆積的大小超過 k
            if ($minHeap->count() > $k) {
                // 移除堆積中最小的元素 (即堆積的根)，確保堆積大小不超過 k
                $minHeap->extract();
            }
        }

        // 遍歷結束後，堆積的根就是第 k 個最大的元素
        return $minHeap->top();
    }
}
?>

---

陣列與區間操作 (Array & Interval Operations) 🧩

涉及陣列或數字區間（Interval）的問題在面試中很常見。這類問題通常需要對資料進行排序、遍歷，並利用雙指針或特定的邏輯來合併、查找或處理重疊、相交的區間。

搭配例題１｜ (56) Merge Intervals

問題描述

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

給定一個區間陣列 intervals，其中 intervals[i] = [starti, endi]，合併所有重疊的區間，並返回一個不重疊的區間陣列，覆蓋輸入中的所有區間。

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

解題思路

合併區間問題的關鍵在於：

1. 排序： 首先，必須對所有區間按照它們的起始時間進行排序。如果起始時間相同，可以按照結束時間排序（但通常不需要）。

2. 遍歷與合併： 排序後，就可以線性遍歷區間，並將相鄰的重疊區間進行合併。

演算法步驟：

1. 處理邊界情況： 如果 intervals 為空或只有一個區間，直接返回。

2. 排序： 對 intervals 陣列進行排序，主要依據每個區間的起始點 starti。

   • 範例：[[1,3],[8,10],[15,18],[2,6]] 排序後變為 [[1,3],[2,6],[8,10],[15,18]]。

3. 初始化結果： 創建一個空陣列 merged 來儲存合併後的區間。將排序後的第一個區間作為當前需要比較的區間，加入 merged。

4. 遍歷其餘區間： 從排序後的第二個區間開始遍歷。

   • 獲取 last_merged_interval (當前 merged 列表中最後一個區間)。

   • 獲取 current_interval (正在遍歷的當前區間)。

   • 檢查是否重疊：

     • 如果 current_interval[0] <= last_merged_interval[1]，表示當前區間與 last_merged_interval 重疊。

       • 合併操作：更新 last_merged_interval 的結束時間為 max(last_merged_interval[1], current_interval[1])。

     • 如果 current_interval[0] > last_merged_interval[1]，表示不重疊。

       • 將 current_interval 直接加入 merged 列表。

5. 返回結果： 遍歷結束後，merged 陣列就是所有不重疊的區間。

時間複雜度： O(NlogN)，主要耗費在排序步驟上。遍歷合併部分是 O(N)。

空間複雜度： O(N)，用於儲存排序後的陣列（如果原地排序則為 O(1)）和 merged 結果陣列。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[][] $intervals
     * @return Integer[][]
     */
    function merge($intervals) {
        // 邊界情況：如果區間為空或只有一個，直接返回
        if (empty($intervals) || count($intervals) <= 1) {
            return $intervals;
        }

        // Step 1: 按照區間的起始時間進行排序
        // usort 用於使用自定義比較函數對陣列進行排序
        usort($intervals, function($a, $b) {
            return $a[0] <=> $b[0]; // 比較區間的起始點 (index 0)
        });

        $merged = []; // 儲存合併後的區間
        // 將排序後的第一個區間作為初始合併區間加入結果
        $merged[] = $intervals[0];

        // Step 2: 遍歷其餘區間並進行合併
        for ($i = 1; $i < count($intervals); $i++) {
            // 獲取 merged 列表中最後一個區間
            $lastMerged = &$merged[count($merged) - 1]; // 注意這裡使用引用 '&'

            $currentInterval = $intervals[$i];

            // 檢查當前區間是否與 lastMerged 區間重疊
            // 重疊條件: currentInterval 的起始時間 <= lastMerged 的結束時間
            if ($currentInterval[0] <= $lastMerged[1]) {
                // 如果重疊，則更新 lastMerged 的結束時間為兩者結束時間的最大值
                $lastMerged[1] = max($lastMerged[1], $currentInterval[1]);
            } else {
                // 如果不重疊，則將當前區間直接加入 merged 列表
                $merged[] = $currentInterval;
            }
        }

        return $merged;
    }
}
?>

---

鍊結串列進階操作 (Advanced Linked List Operations) 🔄

除了基本的鍊結串列遍歷和節點增刪，面試中還會考驗對鍊結串列更複雜的操縱，例如反轉、合併（已排序的合併是基礎，未排序的合併可能涉及其他技巧）、環的檢測和尋找環的起點等。

搭配例題１｜ (141) Linked List Cycle

問題描述

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointers. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

給定鍊結串列的頭節點 head，判斷鍊結串列中是否有環。

如果鍊結串列中存在某個節點，可以透過不斷地跟隨 next 指針再次到達該節點，則稱該鍊結串列存在環。內部使用 pos 來表示尾節點的 next 指針指向的節點的索引。注意 pos 不作為參數傳遞。

如果鍊結串列中有環，返回 true。否則，返回 false。

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node (0-indexed).

解題思路

判斷鍊結串列中是否有環是一個經典問題，最常用的解法是快慢指針法 (Floyd's Cycle-Finding Algorithm / Tortoise and Hare algorithm)。

核心思想：

使用兩個指針，一個快指針（fast）和一個慢指針（slow）。慢指針每次移動一步，快指針每次移動兩步。如果鍊結串列中存在環，快指針最終一定會追上慢指針（在環內相遇）。如果沒有環，快指針會先到達鍊結串列的末尾（即 null）。

演算法步驟：

1. 處理邊界情況： 如果 head 為 null 或者 head->next 為 null，則不可能有環（至少需要兩個節點才能形成環），直接返回 false。

2. 初始化指針：

   • slow = head

   • fast = head->next

3. 迴圈遍歷： 進入一個 while 迴圈，條件是 fast 和 fast->next 都不為 null（這是為了確保 fast 可以安全地移動兩步）。

   • 檢查相遇： 在迴圈開始時或每次移動後，檢查 slow 是否等於 fast。

     • 如果 slow === fast，表示兩個指針相遇，鍊結串列有環，返回 true。

   • 移動指針：

     • slow = slow->next

     • fast = fast->next->next

4. 返回結果： 如果迴圈結束（即 fast 或 fast->next 變為 null），表示快指針已到達末尾，沒有檢測到環，返回 false。

時間複雜度： O(N)，其中 N 是鍊結串列的節點數。在沒有環的情況下，快指針遍歷完整個鍊結串列。在有環的情況下，快指針和慢指針都會進入環，快指針最終會在環內追上慢指針，這個過程也最多遍歷每個節點常數次。

空間複雜度： O(1)，只使用了常數個額外指針變數。

PHP 程式碼

PHP

<?php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 * public $val = 0;
 * public $next = null;
 * function __construct($val = 0, $next = null) {
 * $this->val = $val;
 * $this->next = $next;
 * }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function hasCycle($head) {
        // 如果鍊結串列為空，或只有一個節點，不可能有環
        if ($head === null || $head->next === null) {
            return false;
        }

        $slow = $head;          // 慢指針，每次移動一步
        $fast = $head->next;   // 快指針，每次移動兩步

        // 當快指針和快指針的下一個節點都存在時，持續遍歷
        // 這樣可以確保 fast->next->next 不會報錯
        while ($fast !== null && $fast->next !== null) {
            // 如果快慢指針相遇，表示存在環
            if ($slow === $fast) {
                return true;
            }
            
            // 移動指針
            $slow = $slow->next;
            $fast = $fast->next->next;
        }

        // 如果迴圈結束，表示快指針到達了鍊結串列的末尾，沒有環
        return false;
    }
}
?>

---

圖：DFS/BFS 進階應用 (Graph: Advanced DFS/BFS) 🌐

圖遍歷（DFS/BFS）是圖論的基礎，但在面試中，問題可能會要求您將其應用於更複雜的場景，例如複製圖、尋找最短路徑（權重邊可能涉及 Dijkstra 或 Bellman-Ford），或者在網格中進行搜索。這類問題通常需要您管理訪問狀態以避免無限迴圈。

搭配例題１｜ (133) Clone Graph

問題描述

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int val) and a list of its neighbors (List[Node]).

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as its id. For example, if val = 1, then it is the first node that was created, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

給定一個連通無向圖中某個節點的參考。

返回該圖的深度複製（克隆）。

圖中的每個節點包含一個值（int val）和一個鄰居列表（List[Node]）。

class Node {
    public $val;
    public $neighbors;
}

測試案例格式：

為了簡單起見，每個節點的值與其 id 相同。例如，如果 val = 1，那麼它是第一個被創建的節點，依此類推。該圖在測試案例中以鄰接列表表示。

鄰接列表是用於表示有限圖的無序列表的集合。每個列表描述圖中一個頂點的鄰居集合。

給定的節點將始終是 val = 1 的第一個節點。你必須返回給定節點的副本作為克隆圖的參考。

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]

Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes in the graph.

1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).

2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).

4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]

Output: [[]]

Explanation: Empty graph.

解題思路

複製圖是一個經典問題，因為圖中可能存在環，簡單的遞迴複製會導致無限迴圈。我們需要一個機制來追蹤哪些節點已經被複製過，以及它們的副本是什麼。這可以使用雜湊表 (HashMap) 來實現，將原始節點映射到其克隆節點。

這可以透過 深度優先搜尋 (DFS) 或 廣度優先搜尋 (BFS) 來完成。

核心思想：

在遍歷原始圖的同時，為每個訪問到的原始節點創建一個新的克隆節點。同時，使用一個雜湊表來儲存原始節點與其對應克隆節點的映射關係。當我們處理一個原始節點的鄰居時，先從雜湊表中查找其克隆節點；如果不存在，則遞迴/迭代地創建並將其加入雜湊表。

方法一：深度優先搜尋 (DFS)

1. 處理邊界情況： 如果輸入的 node 為 null，直接返回 null。

2. 創建映射表： 初始化一個雜湊表 visited (或 clonedNodes)，用於儲存原始節點到其克隆節點的映射。

3. 定義 DFS 輔助函式 dfs(original_node, visited)：

   • 如果 original_node 已在 visited 中： 直接返回其對應的克隆節點（因為它已經被複製過）。

   • 創建克隆節點： 創建一個新的 Node，值與 original_node->val 相同。將此克隆節點存入 visited，鍵為 original_node，值為新克隆的節點。

   • 複製鄰居： 遍歷 original_node 的所有鄰居。對於每個鄰居，遞迴呼叫 dfs 函式來獲取其克隆節點，然後將這個克隆節點添加到當前克隆節點的 neighbors 列表中。

   • 返回克隆節點。

4. 主函式呼叫： 從給定的 node 開始呼叫 dfs(node, visited)。

時間複雜度： O(V+E)，其中 V 是節點數，E 是邊數。每個節點和每條邊只會被訪問和處理一次。

空間複雜度： O(V)，用於儲存 visited 雜湊表和遞迴呼叫堆疊。

方法二：廣度優先搜尋 (BFS)

1. 處理邊界情況： 如果輸入的 node 為 null，直接返回 null。

2. 創建映射表和佇列：

   • 初始化一個雜湊表 visited (或 clonedNodes)。

   • 創建一個佇列 queue。

3. 初始化：

   • 創建原始 node 的克隆節點 clone_node，並將其存入 visited (visited[node->val] = clone_node)。

   • 將原始 node 放入佇列。

4. BFS 遍歷： 當佇列不為空時：

   • 從佇列中取出一個原始節點 current_original_node。

   • 獲取其對應的克隆節點 current_clone_node = visited[current_original_node->val]。

   • 複製鄰居： 遍歷 current_original_node 的所有鄰居 neighbor_original。

     • 如果 neighbor_original 不在 visited 中（表示尚未被複製）：

       • 創建 neighbor_original 的克隆節點 neighbor_clone，並將其存入 visited。

       • 將 neighbor_original 放入佇列。

     • 將 neighbor_clone（從 visited 中獲取或剛剛創建的）添加到 current_clone_node 的 neighbors 列表中。

5. 返回結果： 返回最初創建的 clone_node。

時間複雜度： O(V+E)。

空間複雜度： O(V)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a Node.
 * class Node {
 * public $val = null;
 * public $neighbors = null;
 * function __construct($val = 0, $neighbors = array()) {
 * $this->val = $val;
 * $this->neighbors = $neighbors;
 * }
 * }
 */

class Solution {
    // 使用雜湊表來儲存原始節點到其克隆節點的映射
    // 這可以避免重複複製，並處理圖中的環
    private $visited = []; 

    /**
     * DFS (深度優先搜尋) 解法
     * @param Node $node
     * @return Node
     */
    function cloneGraph($node) {
        // 如果輸入節點為空，直接返回空
        if ($node === null) {
            return null;
        }

        // 如果節點已經被訪問過（即已經複製過），直接返回其克隆
        if (isset($this->visited[$node->val])) {
            return $this->visited[$node->val];
        }

        // 創建當前節點的克隆
        $cloneNode = new Node($node->val);
        // 將原始節點與其克隆節點的映射儲存起來
        $this->visited[$node->val] = $cloneNode;

        // 遞迴複製所有鄰居
        foreach ($node->neighbors as $neighbor) {
            $cloneNode->neighbors[] = $this->cloneGraph($neighbor);
        }

        return $cloneNode;
    }

    /**
     * BFS (廣度優先搜尋) 解法
     * @param Node $node
     * @return Node
     */
    function cloneGraphBFS($node) {
        if ($node === null) {
            return null;
        }

        $visited = []; // 儲存原始節點 val 到其克隆節點的映射
        $queue = [];   // 佇列用於 BFS

        // 創建初始節點的克隆，並放入 visited 和 queue
        $cloneNode = new Node($node->val);
        $visited[$node->val] = $cloneNode;
        array_push($queue, $node);

        // BFS 遍歷圖
        while (!empty($queue)) {
            $currentOriginal = array_shift($queue); // 從佇列中取出一個原始節點
            $currentClone = $visited[$currentOriginal->val]; // 獲取其對應的克隆節點

            // 遍歷原始節點的所有鄰居
            foreach ($currentOriginal->neighbors as $neighborOriginal) {
                // 如果鄰居尚未被複製
                if (!isset($visited[$neighborOriginal->val])) {
                    // 創建鄰居的克隆，儲存映射，並將原始鄰居加入佇列
                    $neighborClone = new Node($neighborOriginal->val);
                    $visited[$neighborOriginal->val] = $neighborClone;
                    array_push($queue, $neighborOriginal);
                }
                // 將鄰居的克隆添加到當前克隆節點的鄰居列表
                $currentClone->neighbors[] = $visited[$neighborOriginal->val];
            }
        }

        return $cloneNode; // 返回最初創建的克隆根節點
    }
}
?>

除了前面提到的雜湊表、二元搜尋、鏈結串列、二元樹、遞迴與迭代解、動態規劃和位元運算這些基礎且重要的主題之外，面試官通常還會期望您能掌握以下這些進階演算法和模式，它們更考驗您對問題的抽象能力、最佳化思維和邊界條件處理：

---

雙指針 (Two Pointers) 進階應用 🏞️

雙指針不只是用於排序陣列中的查找，也能應用於解決許多子陣列、子字串或更複雜的陣列遍歷問題。

搭配例題１｜ (11) Container With Most Water

問題描述

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two such lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

給你 n 條垂直線，第 i 條線的兩個端點分別是 (i, 0) 和 (i, height[i])。

請找出兩條線，使得它們與 x 軸共同構成一個容器，該容器可以容納最多的水。

返回該容器能儲存的最大水量。

注意：你不能傾斜容器。

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water the container can contain is 49.

Example 2:

Input: height = [1,1]

Output: 1

解題思路

這是一個經典的雙指針問題，但其巧妙之處在於指針的移動策略。

容器的容量由兩個因素決定：min(height[left], height[right])（容器的高度）和 (right - left)（容器的寬度）。

暴力解法 (Brute Force):

使用兩個巢狀迴圈遍歷所有可能的線條組合，計算每對線條所能形成的容量，並找出最大值。

時間複雜度：O(N2)。

雙指針優化解法：

1. 初始化指針：

   • 設 left = 0 (左指針，指向最左邊的線)。

   • 設 right = count(height) - 1 (右指針，指向最右邊的線)。

   • max_area = 0 (儲存目前找到的最大容量)。

2. 迴圈遍歷： 當 left < right 時，持續執行迴圈。

   • 計算當前容量： current_area = min(height[left], height[right]) * (right - left)。

   • 更新最大容量： max_area = max(max_area, current_area)。

   • 移動指針： 這是關鍵的一步。為了嘗試找到更大的容量，我們應該移動較短的那條線所對應的指針。

     • 如果 height[left] < height[right]，則將 left 指針向右移動一位 (left++)。

     • 否則（height[left] >= height[right]），將 right 指針向左移動一位 (right--)。

為什麼移動較短的指針？

因為容器的容量是由較短的邊決定的。如果我們移動較長的邊，容器的高度仍然受限於較短的邊，但寬度會減小，這樣容量不可能變大。而移動較短的邊，雖然寬度減小，但有可能找到一條更高的邊，從而使容器的高度增加，進而可能獲得更大的容量。這種貪婪策略能夠保證找到全局最優解。

時間複雜度： O(N)，因為兩個指針從兩端向中間移動，最多遍歷整個陣列一次。

空間複雜度： O(1)，只使用了常數額外的變數。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $height
     * @return Integer
     */
    function maxArea($height) {
        $left = 0; // 左指針，指向最左邊的線
        $right = count($height) - 1; // 右指針，指向最右邊的線
        $max_area = 0; // 儲存最大容量

        // 當左右指針不相遇時，持續尋找
        while ($left < $right) {
            // 計算當前兩條線能構成的容器容量
            // 容量 = 較短的線的高度 * 兩條線之間的距離
            $current_area = min($height[$left], $height[$right]) * ($right - $left);

            // 更新最大容量
            $max_area = max($max_area, $current_area);

            // 移動指針：移動較短的那條線的指針
            // 因為容器的容量受限於較短的線。
            // 移動較短的線，才有可能找到一條更高的線來增加容器高度，進而增加容量。
            // 如果移動較長的線，容器高度不變，但寬度減小，容量只會變小。
            if ($height[$left] < $height[$right]) {
                $left++;
            } else {
                $right--;
            }
        }

        return $max_area;
    }
}
?>

---

貪婪演算法 (Greedy Algorithm) 進階應用 🚀

貪婪演算法在解決一些看似複雜的問題時，往往能透過每一步的最優選擇達到全局最優。跳躍遊戲系列就是很好的例子，它需要你判斷每一步應該如何跳才能達到目標。

搭配例題１｜ (45) Jump Game II

問題描述

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element nums[i] represents the maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

給定一個非負整數陣列 nums，你最初位於陣列的第一個索引。

每個元素 nums[i] 代表你在該位置可以跳躍的最大長度。

你的目標是以最少的跳躍次數到達陣列的最後一個索引。

你可以假設你總是能夠到達最後一個索引。

Example 1:

Input: nums = [2,3,1,1,4]

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2.

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]

Output: 2

解題思路

這是一個經典的貪婪演算法問題，也可以用動態規劃解決（但動態規劃的時間複雜度通常較高）。貪婪解法更為高效。

核心思想：

我們要以最少的跳躍次數到達終點。我們可以從當前跳躍能到達的最遠位置，來決定下一跳的最佳起點。

1. 定義變數：

   • jumps：跳躍次數，初始化為 0。

   • current_farthest：從目前跳躍能到達的最遠位置，初始化為 0。

   • last_jump_reach：從上次跳躍的起點能到達的最遠位置，初始化為 0。

2. 遍歷陣列： 遍歷 nums 陣列，索引從 i = 0 到 count(nums) - 2 (因為到達最後一個索引本身不算一次跳躍，如果只有一個元素或已經在最後一個元素，則不需要跳)。

3. 更新能到達的最遠位置：

   • current_farthest = max(current_farthest, i + nums[i])。這表示從 i 這個位置，加上其能跳躍的長度，可以到達的總距離。我們不斷更新這個值，以知道從當前範圍內能跳到的最遠點。

4. 判斷是否需要跳躍：

   • 如果當前遍歷的索引 i 等於 last_jump_reach (即：我們已經到達了上次跳躍所能覆蓋的最遠邊界)：

     • 這意味著我們必須進行一次新的跳躍。將 jumps 加 1。

     • 更新 last_jump_reach = current_farthest。新的跳躍將從當前 i 往前，能跳到 current_farthest。

5. 返回結果： 遍歷結束後，jumps 就是最少的跳躍次數。

為什麼這樣有效？

我們在每個步驟中，都盡可能地擴展能到達的範圍（current_farthest）。當我們的遍歷指針達到上一次跳躍所能覆蓋的極限 (last_jump_reach) 時，我們就必須進行一次新的跳躍。這次新的跳躍，我們選擇能讓我們到達最遠距離的那個點作為跳躍點，並將 last_jump_reach 更新為這個新的最遠距離 (current_farthest)。這樣確保了每一步都最大化了跳躍距離，從而達到最小化總跳躍次數的目的。

時間複雜度： O(N)，因為我們只遍歷陣列一次。

空間複雜度： O(1)，只使用了常數額外的變數。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        $n = count($nums);
        
        // 如果陣列只有一個元素或為空，則不需要跳躍，直接返回 0
        if ($n <= 1) {
            return 0;
        }

        $jumps = 0;              // 記錄跳躍次數
        $current_farthest = 0;   // 記錄從當前跳躍能到達的最遠位置
        $last_jump_reach = 0;    // 記錄從上次跳躍的起點能到達的最遠位置

        // 遍歷陣列，直到倒數第二個元素
        // 因為到達最後一個索引本身不算一次跳躍
        for ($i = 0; $i < $n - 1; $i++) {
            // 更新從當前位置 i 開始，能到達的最遠距離
            $current_farthest = max($current_farthest, $i + $nums[$i]);

            // 如果當前遍歷的索引 i 已經到達了上次跳躍能覆蓋的最遠邊界
            if ($i === $last_jump_reach) {
                $jumps++; // 進行一次新的跳躍
                // 更新下次跳躍的新邊界為目前能跳到的最遠位置
                $last_jump_reach = $current_farthest;
                
                // 如果更新後的最遠邊界已經超過或等於陣列末尾，則表示已到達，可以提前結束
                // (通常題目保證可達，這一步可選，但對於優化可達性檢查有幫助)
                // if ($last_jump_reach >= $n - 1) {
                //     break;
                // }
            }
        }

        return $jumps;
    }
}
?>

---

分治法 / 優先佇列 (Divide and Conquer / Priority Queue) 🔄

合併多個已排序的數據結構是一個常見的問題。當數量較多時，簡單的兩兩合併會導致效率低下。此時，分治法（如歸併排序的思想）或使用優先佇列（堆積）能更有效地解決問題。

搭配例題１｜ (23) Merge k Sorted Lists

問題描述

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked list and return it.

給你一個 k 個鍊結串列的陣列 lists，每個鍊結串列都已按升序排序。

將所有鍊結串列合併為一個排序後的鍊結串列，並返回它。

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]

Output: [1,1,2,3,4,4,5,6]

Explanation: The linked lists are:

[1->4->5],

[1->3->4],

[2->6]

merging them into one sorted list:

1->1->2->3->4->4->5->6

Example 2:

Input: lists = []

Output: []

解題思路

合併 k 個排序鍊結串列是比合併兩個鍊結串列更複雜的問題。有幾種方法可以解決：

方法一：逐個合併 (Iterative Merging of Two Lists)

這是一種直觀但效率不高的做法。你可以重複呼叫「合併兩個排序鍊結串列」(LeetCode 21) 的函式。

1. 從 lists 中取出第一個鍊結串列作為結果。

2. 然後，將結果與第二個鍊結串列合併。

3. 再將結果與第三個鍊結串列合併，依此類推。

   時間複雜度： O(KtimesN)，其中 K 是鍊結串列的數量， N 是平均每個鍊結串列的長度。因為每次合併都需要遍歷兩個鍊結串列，且合併 K-1 次。

   空間複雜度： O(1) (不考慮遞迴堆疊)。

方法二：分治法 (Divide and Conquer)

這是更優雅且高效的方法，類似於歸併排序的思想。

1. 將 k 個鍊結串列分成兩半。

2. 遞迴地合併左半部分和右半部分。

3. 最後，將兩個遞迴合併的結果（都是排序後的鍊結串列）再次合併。

   演算法步驟：

• 定義一個輔助函式 mergeKListsDivideAndConquer(lists, start, end)。

• 基本情況：

  • 如果 start == end，返回 lists[start]。

  • 如果 start > end，返回 null。

• 遞迴步驟：

  • mid = floor((start + end) / 2)。

  • left_merged = mergeKListsDivideAndConquer(lists, start, mid)。

  • right_merged = mergeKListsDivideAndConquer(lists, mid + 1, end)。

  • 返回 mergeTwoLists(left_merged, right_merged)（使用 LeetCode 21 的合併兩個排序鍊結串列的函式）。

時間複雜度： O(NlogK)，其中 N 是所有鍊結串列的總節點數。

空間複雜度： O(logK)，用於遞迴呼叫堆疊。

方法三：使用最小堆積 (Min-Heap / Priority Queue)

這是解決此類問題最標準且高效的通用方法。

1. 創建一個最小堆積 (Min-Heap)。

2. 初始化堆積： 將所有鍊結串列的第一個節點放入最小堆積。堆積會根據節點的值自動排序。

3. 構建結果鍊結串列：

   • 創建一個虛擬頭節點 dummyHead 和一個 current 指針指向它。

   • 當堆積不為空時，持續執行迴圈：

     • 從堆積中提取（extract）最小的節點 min_node。

     • 將 min_node 連接到 current 的 next：current->next = min_node。

     • 移動 current 指針：current = current->next。

     • 如果 min_node 有下一個節點 (min_node->next !== null)，則將 min_node->next 放入堆積。

4. 返回結果： 返回 dummyHead->next。

時間複雜度： O(NlogK)。每個節點被處理一次（N 個節點），每次操作（插入、提取）堆積需要 O(logK) 時間。

空間複雜度： O(K)，用於儲存堆積（堆積中最多同時有 K 個節點）。

PHP 程式碼

PHP

<?php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 * public $val = 0;
 * public $next = null;
 * function __construct($val = 0, $next = null) {
 * $this->val = $val;
 * $this->next = $next;
 * }
 * }
 */

class Solution {
    /**
     * 合併兩個已排序鍊結串列的輔助函式 (來自 LeetCode 21)
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    private function mergeTwoLists($list1, $list2) {
        $dummyHead = new ListNode();
        $current = $dummyHead;

        while ($list1 !== null && $list2 !== null) {
            if ($list1->val <= $list2->val) {
                $current->next = $list1;
                $list1 = $list1->next;
            } else {
                $current->next = $list2;
                $list2 = $list2->next;
            }
            $current = $current->next;
        }

        if ($list1 !== null) {
            $current->next = $list1;
        } elseif ($list2 !== null) {
            $current->next = $list2;
        }

        return $dummyHead->next;
    }

    /**
     * 方法一：分治法 (Divide and Conquer)
     * @param ListNode[] $lists
     * @return ListNode
     */
    function mergeKLists($lists) {
        $k = count($lists);
        if ($k === 0) {
            return null;
        }
        if ($k === 1) {
            return $lists[0];
        }

        return $this->mergeKListsDivideAndConquer($lists, 0, $k - 1);
    }

    /**
     * 分治法的輔助函式
     * @param ListNode[] $lists
     * @param Integer $start
     * @param Integer $end
     * @return ListNode
     */
    private function mergeKListsDivideAndConquer(&$lists, $start, $end) {
        if ($start === $end) {
            return $lists[$start];
        }
        if ($start > $end) {
            return null;
        }

        $mid = floor(($start + $end) / 2);
        $leftMerged = $this->mergeKListsDivideAndConquer($lists, $start, $mid);
        $rightMerged = $this->mergeKListsDivideAndConquer($lists, $mid + 1, $end);

        return $this->mergeTwoLists($leftMerged, $rightMerged);
    }

    /**
     * 方法二：使用最小堆積 (Min-Heap / Priority Queue)
     * @param ListNode[] $lists
     * @return ListNode
     */
    function mergeKListsWithHeap($lists) {
        $dummyHead = new ListNode();
        $current = $dummyHead;

        // 創建一個最小堆積
        // 為了將 ListNode 放入堆積並按其 val 排序，需要自定義比較
        $minHeap = new class extends SplMinHeap {
            // PHP SplHeap 允許覆寫 compare 方法來定義排序邏輯
            // 將節點值較小的排在前面 (對於最小堆積來說)
            protected function compare($value1, $value2) {
                return $value2->val <=> $value1->val; // 確保值小的優先
            }
        };

        // 將所有鍊結串列的頭節點放入堆積 (如果非空)
        foreach ($lists as $list) {
            if ($list !== null) {
                $minHeap->insert($list);
            }
        }

        // 當堆積不為空時，持續取出最小節點並處理
        while (!$minHeap->isEmpty()) {
            $minNode = $minHeap->extract(); // 取出堆積中最小的節點
            
            // 將最小節點連接到結果鍊結串列的尾部
            $current->next = $minNode;
            $current = $current->next; // 移動 current 指針

            // 如果取出的節點還有下一個節點，將其下一個節點放入堆積
            if ($minNode->next !== null) {
                $minHeap->insert($minNode->next);
            }
        }

        return $dummyHead->next; // 返回合併後鍊結串列的頭部
    }
}
?>

---

樹：DFS 進階應用 (Tree: Advanced DFS) 🌲

DFS 在樹上應用廣泛，不限於遍歷。許多樹形結構的 DP 問題、路徑問題等都需要透過 DFS 加上遞迴的狀態維護來解決。

搭配例題１｜ (124) Binary Tree Maximum Path Sum

問題描述

A path in a binary tree is defined as a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. The path does not necessarily need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

二元樹中的路徑定義為節點序列，其中序列中每對相鄰節點之間都有邊連接。一個節點在序列中最多只能出現一次。路徑不必經過根節點。

一個路徑的路徑和是該路徑中所有節點值的總和。

給定一個二元樹的根節點 root，返回任何非空路徑的最大路徑和。

Example 1:

Input: root = [1,2,3]

Output: 6

Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]

Output: 42

Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

解題思路

這是一個複雜的二元樹問題，需要結合遞迴和全局變數來追蹤最大路徑和。一個路徑不一定經過根節點，它可以在任何地方開始和結束。

核心思想：

對於任意一個節點，以該節點為轉折點的路徑，其路徑和為：

節點值 + 左子樹提供的最大單邊路徑和 + 右子樹提供的最大單邊路徑和

而對於其父節點而言，該節點能向上提供的最大單邊路徑和為：

節點值 + max(左子樹提供的最大單邊路徑和, 右子樹提供的最大單邊路徑和, 0) （取 0 是為了避免負值路徑拉低總和）

我們需要一個遞迴函式來計算每個節點能提供的「最大單邊路徑和」（即從該節點向下到其任意一個子孫的路徑和，且該路徑是有效的，不能有負值拖累），同時，在遞迴過程中用一個全局變數來更新遇到的最大「路徑和」（它可以是任意兩個分支的組合，或者只是節點本身）。

遞迴輔助函式 maxGain(node)：

1. 基本情況： 如果 node 為 null，返回 0 (空節點不提供任何增益)。

2. 遞迴計算左右子樹的最大增益：

   • left_gain = max(0, $this->maxGain(node->left))：左子樹能提供的最大單邊路徑和。如果為負，則取 0，表示不走這個分支。

   • right_gain = max(0, $this->maxGain(node->right))：右子樹能提供的最大單邊路徑和。

3. 計算以當前節點為轉折點的最大路徑和：

   • path_sum_through_node = node->val + left_gain + right_gain

   • 用這個 path_sum_through_node 來更新全局最大路徑和：$this->max_overall_path_sum = max($this->max_overall_path_sum, path_sum_through_node)。

4. 返回當前節點能提供的最大單邊路徑和：

   • return node->val + max(left_gain, right_gain)。這個值將傳遞給父節點，作為父節點計算路徑和的一部分。

主函式 maxPathSum(root)：

• 初始化一個全局變數 max_overall_path_sum 為負無限大（因為節點值可以是負數）。

• 呼叫 maxGain(root)。

• 返回 max_overall_path_sum。

時間複雜度： O(N)，其中 N 是樹的節點數，每個節點只會被訪問一次。

空間複雜度： O(H)，其中 H 是樹的高度，用於遞迴呼叫堆疊。最壞情況下（斜樹），H 可以是 N，所以空間複雜度可能是 O(N)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    // 使用一個全局變數來追蹤遇到的最大路徑和
    // 初始化為負無限大，因為節點值可以是負數
    private $max_overall_path_sum;

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxPathSum($root) {
        // 初始化最大路徑和為 PHP 最小整數，以確保任何有效路徑都能更新它
        $this->max_overall_path_sum = -PHP_INT_MAX; 
        
        // 呼叫輔助遞迴函式來計算每個節點的最大增益，並同時更新全局最大路徑和
        $this->maxGain($root);

        return $this->max_overall_path_sum;
    }

    /**
     * 輔助遞迴函式：計算從當前節點向下（單邊）的最大路徑和增益
     * 同時在過程中更新全局最大路徑和 (考慮以當前節點為轉折點的路徑)
     * @param TreeNode $node 當前節點
     * @return Integer 從當前節點向下能提供的最大增益（如果為負則取0）
     */
    private function maxGain($node) {
        // 基本情況：如果節點為空，則不提供任何增益
        if ($node === null) {
            return 0;
        }

        // 遞迴計算左子樹的最大增益。如果增益為負，則視為 0 (不走這個負增益分支)
        $left_gain = max(0, $this->maxGain($node->left));
        // 遞迴計算右子樹的最大增益。如果增益為負，則視為 0 (不走這個負增益分支)
        $right_gain = max(0, $this->maxGain($node->right));

        // 計算以當前節點為轉折點（即路徑在此節點「拐彎」）的最大路徑和
        // 這個路徑和 = 節點值 + 左子樹增益 + 右子樹增益
        $path_sum_through_node = $node->val + $left_gain + $right_gain;

        // 更新全局的最大路徑和
        $this->max_overall_path_sum = max($this->max_overall_path_sum, $path_sum_through_node);

        // 返回當前節點能向其父節點提供的最大增益（單邊路徑）
        // 這個增益是：節點值 + max(左子樹增益, 右子樹增益)
        return $node->val + max($left_gain, $right_gain);
    }
}
?>