2025年8月17日 星期日

《面試官問完，開AI回答》LeetCode PHP 問題集錦（進階篇一）

在 LeetCode 的演算法學習旅程中，除了基礎題型，還有許多值得深入探索的進階題目。以下整理了多個常見類別的 LeetCode PHP 問題，希望能幫助大家系統性地掌握不同演算法的應用。

陣列 (Array)

  • 1356. 根據數字二進制下1的數目排序

  • 1365. 有多少小於當前數字的數字

字串 (String)

  • 0028. 實現 strStr()

  • 0925. 長按鍵入

  • 1002. 查找常用字元

  • 1221. 分割平衡字串

鏈表 (Linked List)

  • 0143. 重排鏈表

  • 0707. 設計鏈表

雜湊表 (Hash Table)

  • 0205. 同構字串

  • 1207. 獨一無二的出現次數

二叉樹 (Binary Tree)

  • 0096. 不同的二叉搜索樹

  • 0106. 從中序與後序遍歷序列構造二叉樹

  • 0108. 將有序陣列轉換為二叉搜索樹

  • 0110. 平衡二叉樹

  • 0112. 路徑總和

  • 0129. 求根到葉子節點數字之和

  • 0222. 完全二叉樹的節點個數

  • 0337. 打家劫舍 III

  • 0404. 左葉子之和

  • 0501. 二叉搜索樹中的眾數

  • 0513. 找樹左下角的值

  • 0530. 二叉搜索樹的最小絕對差

  • 0538. 把二叉搜索樹轉換為累加樹

  • 0617. 合併二叉樹

  • 0654. 最大二叉樹

  • 0669. 修剪二叉搜索樹

  • 0700. 二叉搜索樹中的搜索

  • 0701. 二叉搜索樹中的插入操作

  • 0968. 監控二叉樹

  • 1382. 將二叉搜索樹變平衡

貪心演算法 (Greedy)

  • 0045. 跳躍遊戲 II

  • 0134. 加油站

  • 0376. 擺動序列

  • 0452. 用最少數量的箭引爆氣球

  • 0763. 劃分字母區間

字串 (String)

0925. 長按鍵入 (Long Pressed Name)

問題描述：判斷一個給定的名字 name 是否可以透過長按鍵盤輸入得到另一個字串 typed。例如，name = "alex"，typed = "aaleex"，則為 true。

正確解題思路概述：

這是一個典型的雙指針問題。使用兩個指針 i 和 j 分別遍歷 name 和 typed。當兩者字元匹配時，兩個指針都向前移動；當不匹配時，檢查 typed 的指針 j 是否可以透過長按來匹配前一個字元，如果可以，則只移動 j，否則表示不匹配。最後，確保 name 的所有字元都已被遍歷。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    function isLongPressedName($name, $typed) {
        $i = 0;
        $j = 0;

        while ($j < strlen($typed)) {
            if ($i < strlen($name) && $name[$i] === $typed[$j]) {
                $i++;
                $j++;
            } elseif ($j > 0 && $typed[$j] === $typed[$j - 1]) {
                $j++;
            } else {
                return false;
            }
        }
        return $i === strlen($name);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼看起來很接近正確答案，但在某個邊界情況下會出錯。考慮這個測試案例：name = "saeed", typed = "ssaaedd"。

  • i=0, j=0，name[0] (s) 和 typed[0] (s) 匹配，i++, j++。

  • i=1, j=1，name[1] (a) 和 typed[1] (s) 不匹配。進入 elseif 判斷，typed[1] 和 typed[0] (s) 匹配，j++。

  • i=1, j=2，name[1] (a) 和 typed[2] (a) 匹配，i++, j++。

  • ...這個過程會順利進行到 name 結束。

  • 現在考慮另一個測試案例：name = "pyplrz", typed = "ppyypllr"。

  • i=0, j=0，name[0] (p) 和 typed[0] (p) 匹配，i++, j++。

  • i=1, j=1，name[1] (y) 和 typed[1] (p) 不匹配。進入 elseif 判斷，typed[1] (p) 和 typed[0] (p) 匹配，j++。

  • i=1, j=2，name[1] (y) 和 typed[2] (y) 匹配，i++, j++。

  • ...以此類推，直到 name 中的 r。i 指向 r，j 指向 l。

  • i 指向 l，j 指向 l，匹配，i++, j++。

  • i 指向 r，j 指向 l，不匹配。進入 elseif，typed[j] (l) 和 typed[j-1] (l) 匹配，j++。

  • 錯誤點：當 i 遍歷完 name 後，程式碼依然在迴圈中。例如，name = "le"，typed = "lleee"。當 i 遍歷到 e 後，i=2，typed 還有多餘的 e。迴圈會繼續執行，但 if ($i < strlen($name) && ...) 中的 && 條件會因為 i 已經等於 strlen($name) 而導致 if 判斷失敗，轉而進入 elseif。這會讓程式碼錯誤地認為 typed 中多餘的字元是合法的長按字元，但實際上這些字元已經超過了 name 的長度。

正確的 PHP 解決方案 (Corrected PHP Solution)：

PHP
class Solution {
    function isLongPressedName($name, $typed) {
        $i = 0;
        $j = 0;

        while ($j < strlen($typed)) {
            // Case 1: characters match
            if ($i < strlen($name) && $name[$i] === $typed[$j]) {
                $i++;
                $j++;
            } 
            // Case 2: long pressed character in typed string
            elseif ($j > 0 && $typed[$j] === $typed[$j - 1]) {
                $j++;
            } 
            // Case 3: mismatch found
            else {
                return false;
            }
        }
        
        // Final check: ensures all characters in name were matched
        return $i === strlen($name);
    }
}

除錯本類問題的技巧：

  1. 分步追蹤法：對於雙指針或多指針問題，不要一次性想完所有邏輯。可以透過紙筆或在程式碼中加入註解，一步步追蹤指針的移動，特別是當遇到邊界條件時。

  2. 邊界條件思考：在寫完程式碼後，立即思考以下邊界情況：

    • name 和 typed 哪個長度更長？

    • typed 中是否有在 name 中不存在的字元？

    • typed 中多餘的長按字元是否只出現在 name 的尾部？

  3. 迴圈結束條件：仔細檢查迴圈的結束條件。通常，while 迴圈結束後，需要一個最終檢查，來判斷所有條件是否都已滿足。在這個問題中，就是 name 是否完整匹配了。

鏈表 (Linked List)

0707. 設計鏈表 (Design Linked List)

問題描述：設計一個鏈表，支援 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 等操作。

正確解題思路概述：

這是一道考驗基本功的實作題。需要對單向或雙向鏈表的節點和指針操作有清晰的理解。一個通用的做法是使用一個虛擬頭節點 (dummy head) 來簡化邊界情況的處理，這樣在頭部進行增刪操作時就不需要特殊處理。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Node {
    public $val;
    public $next;
    public function __construct($val) {
        $this->val = $val;
        $this->next = null;
    }
}

class MyLinkedList {
    public $head;
    public $size;

    function __construct() {
        $this->head = null;
        $this->size = 0;
    }

    function get($index) {
        if ($index < 0 || $index >= $this->size) {
            return -1;
        }
        $curr = $this->head;
        for ($i = 0; $i < $index; $i++) {
            $curr = $curr->next;
        }
        return $curr->val;
    }

    function addAtHead($val) {
        $newNode = new Node($val);
        $newNode->next = $this->head;
        $this->head = $newNode;
        $this->size++;
    }

    function addAtTail($val) {
        if ($this->head === null) {
            $this->addAtHead($val);
            return;
        }
        $curr = $this->head;
        while ($curr->next !== null) {
            $curr = $curr->next;
        }
        $curr->next = new Node($val);
        $this->size++;
    }

    function addAtIndex($index, $val) {
        if ($index < 0 || $index > $this->size) {
            return;
        }
        if ($index === 0) {
            $this->addAtHead($val);
            return;
        }
        $curr = $this->head;
        for ($i = 0; $i < $index - 1; $i++) {
            $curr = $curr->next;
        }
        $newNode = new Node($val);
        $newNode->next = $curr->next;
        $curr->next = $newNode;
        $this->size++;
    }
    
    function deleteAtIndex($index) {
        if ($index < 0 || $index >= $this->size) {
            return;
        }
        if ($index === 0) {
            $this->head = $this->head->next;
            $this->size--;
            return;
        }
        $curr = $this->head;
        for ($i = 0; $i < $index - 1; $i++) {
            $curr = $curr->next;
        }
        $curr->next = $curr->next->next;
        $this->size--;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼乍看之下沒有問題，幾乎涵蓋了所有操作。然而，它在 addAtTail 和 addAtIndex 的實現中，有一個嚴重的邏輯漏洞。

  • 錯誤點：當鏈表為空時，addAtTail 會呼叫 addAtHead，並正確地將 size 加一。但當我們在非空鏈表的尾部添加節點時，while ($curr->next !== null) 迴圈會正確地找到尾部節點，然後添加新節點並將 size 加一。問題在於，如果我們在 addAtTail 中不檢查空鏈表，直接使用 while ($curr->next !== null)，當鏈表為空時 $curr 會是 null，然後 while 迴圈會因為 null 沒有 next 屬性而報錯。

  • 另一個錯誤點：addAtIndex 和 deleteAtIndex 的邏輯。當 index 等於 size 時，addAtIndex 的迴圈 for ($i = 0; $i < $index - 1; $i++) 只會遍歷到倒數第二個節點，然後在它的後面插入新節點，這正是在尾部添加的操作。這部分邏輯沒有問題。但如果我們不處理 index === 0 的情況，直接從 $this->head 開始遍歷，那麼 $curr 會停留在 index-1 的位置，而當 index 為 0 時，index-1 是 -1，這會導致迴圈執行錯誤。雖然程式碼中對此進行了特別處理，但它增加了不必要的複雜性。

正確的 PHP 解決方案 (Corrected PHP Solution)：

這裡介紹使用虛擬頭節點的方法，這是一種更健壯、更優雅的解決方案。

PHP
class Node {
    public $val;
    public $next;
    public function __construct($val) {
        $this->val = $val;
        $this->next = null;
    }
}

class MyLinkedList {
    public $dummyHead;
    public $size;

    function __construct() {
        $this->dummyHead = new Node(0); // Use a dummy head node
        $this->size = 0;
    }

    function get($index) {
        if ($index < 0 || $index >= $this->size) {
            return -1;
        }
        $curr = $this->dummyHead->next;
        for ($i = 0; $i < $index; $i++) {
            $curr = $curr->next;
        }
        return $curr->val;
    }

    function addAtHead($val) {
        $this->addAtIndex(0, $val);
    }

    function addAtTail($val) {
        $this->addAtIndex($this->size, $val);
    }

    function addAtIndex($index, $val) {
        if ($index < 0 || $index > $this->size) {
            return;
        }

        $pred = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $pred = $pred->next;
        }
        $newNode = new Node($val);
        $newNode->next = $pred->next;
        $pred->next = $newNode;
        $this->size++;
    }
    
    function deleteAtIndex($index) {
        if ($index < 0 || $index >= $this->size) {
            return;
        }

        $pred = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $pred = $pred->next;
        }
        $pred->next = $pred->next->next;
        $this->size--;
    }
}

除錯本類問題的技巧：

  1. 使用虛擬頭節點：這是鏈表操作的黃金法則。它能將所有對鏈表頭部的操作（增刪）都統一為對普通節點的操作，從而極大地簡化邏輯，避免空鏈表 (null) 的判斷。

  2. 指針的角色：在操作中，明確每個指針的作用。例如，$curr 應該指向當前節點，$pred 應該指向前一個節點。在增刪操作時，通常需要找到目標節點的前一個節點來進行指針的修改。

  3. 畫圖追蹤法：對於複雜的指針操作，畫出鏈表的圖，標註每個指針的位置。然後，一步步按照程式碼修改箭頭（指針），這能幫助你視覺化錯誤。

雜湊表 (Hash Table)

0205. 同構字串 (Isomorphic Strings)

問題描述：判斷兩個字串 s 和 t 是否同構。同構的定義是 s 中的每個字元都能被唯一地對應到 t 中的一個字元，且這種對應關係是雙向唯一的。

正確解題思路概述：

這類問題的核心是建立一個穩固的雙向映射。使用兩個雜湊表，一個負責 s 到 t 的映射，另一個負責 t 到 s 的映射。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    function isIsomorphic($s, $t) {
        if (strlen($s) !== strlen($t)) {
            return false;
        }
        $map = [];

        for ($i = 0; $i < strlen($s); $i++) {
            if (isset($map[$s[$i]])) {
                if ($map[$s[$i]] !== $t[$i]) {
                    return false;
                }
            } else {
                $map[$s[$i]] = $t[$i];
            }
        }
        return true;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼只使用了一個雜湊表，嘗試建立從 s 到 t 的映射。這解決了單向映射的問題，但卻忽略了雙向唯一的條件。

  • 錯誤點：考慮 s = "foo", t = "bar"。

    • f -> b，映射建立。

    • o -> a，映射建立。

    • 第二個 o 來到，map['o'] 已存在，值為 a，與 t[2] (r) 不符，返回 false。這是正確的。

  • 再考慮另一個測試案例：s = "paper", t = "title"。

    • p -> t，映射建立。

    • a -> i，映射建立。

    • p -> t，map['p'] 存在，值為 t，與 t[2] (t) 匹配，繼續。

    • e -> l，映射建立。

    • r -> e，映射建立。

  • 問題出現在這裡：s = "ab", t = "aa"。

    • a -> a，映射建立。

    • b -> a，map['b'] 不存在，建立映射 map['b'] = 'a'。

    • 程式碼會返回 true，但這兩個字串並不同構！因為 s 中的 a 和 b 都被映射到了 t 中的 a，這違背了唯一對應的條件。

正確的 PHP 解決方案 (Corrected PHP Solution)：

為了確保雙向唯一，我們需要使用兩個雜湊表。

PHP
class Solution {
    function isIsomorphic($s, $t) {
        if (strlen($s) !== strlen($t)) {
            return false;
        }
        $mapST = [];
        $mapTS = [];

        for ($i = 0; $i < strlen($s); $i++) {
            $charS = $s[$i];
            $charT = $t[$i];
            
            // Check s -> t mapping
            if (isset($mapST[$charS])) {
                if ($mapST[$charS] !== $charT) {
                    return false;
                }
            } else {
                $mapST[$charS] = $charT;
            }

            // Check t -> s mapping
            if (isset($mapTS[$charT])) {
                if ($mapTS[$charT] !== $charS) {
                    return false;
                }
            } else {
                $mapTS[$charT] = $charS;
            }
        }
        return true;
    }
}

除錯本類問題的技巧：

  1. 分清單向與雙向：在處理映射問題時，首先要確認是單向關係還是雙向關係。如果題目要求「唯一對應」，通常意味著需要雙向檢查。

  2. 反向思維：如果一個字元被映射，檢查是否還有其他字元映射到同一個值。這就是為什麼需要第二個雜湊表來檢查 t 到 s 的反向映射。

  3. 使用 isset() 檢查存在性：在 PHP 中，使用 isset() 檢查鍵是否存在比直接訪問更快，也更安全。

雜湊表 (Hash Table)

0205. 同構字串 (Isomorphic Strings)

問題描述：判斷兩個字串 s 和 t 是否同構。同構的定義是 s 中的每個字元都能被唯一地對應到 t 中的一個字元，且這種對應關係是雙向唯一的。

正確解題思路概述：

這類問題的核心是建立一個穩固的雙向映射。使用兩個雜湊表，一個負責 s 到 t 的映射，另一個負責 t 到 s 的映射。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    function isIsomorphic($s, $t) {
        if (strlen($s) !== strlen($t)) {
            return false;
        }
        $map = [];

        for ($i = 0; $i < strlen($s); $i++) {
            if (isset($map[$s[$i]])) {
                if ($map[$s[$i]] !== $t[$i]) {
                    return false;
                }
            } else {
                $map[$s[$i]] = $t[$i];
            }
        }
        return true;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼只使用了一個雜湊表，嘗試建立從 s 到 t 的映射。這解決了單向映射的問題，但卻忽略了雙向唯一的條件。

  • 錯誤點：考慮 s = "ab", t = "aa"。

    • i=0 時，s[0] (a) 到 t[0] (a) 的映射建立。

    • i=1 時，s[1] (b) 到 t[1] (a) 的映射建立。

    • 程式碼會返回 true，但這兩個字串並不同構！因為 s 中的 a 和 b 都被映射到了 t 中的 a，這違背了唯一對應的條件。

正確的 PHP 解決方案 (Corrected PHP Solution)：

為了確保雙向唯一，我們需要使用兩個雜湊表。

PHP
class Solution {
    function isIsomorphic($s, $t) {
        if (strlen($s) !== strlen($t)) {
            return false;
        }
        $mapST = [];
        $mapTS = [];

        for ($i = 0; $i < strlen($s); $i++) {
            $charS = $s[$i];
            $charT = $t[$i];
            
            // Check s -> t mapping
            if (isset($mapST[$charS])) {
                if ($mapST[$charS] !== $charT) {
                    return false;
                }
            } else {
                $mapST[$charS] = $charT;
            }

            // Check t -> s mapping
            if (isset($mapTS[$charT])) {
                if ($mapTS[$charT] !== $charS) {
                    return false;
                }
            } else {
                $mapTS[$charT] = $charS;
            }
        }
        return true;
    }
}

除錯本類問題的技巧：

  1. 分清單向與雙向：在處理映射問題時，首先要確認是單向關係還是雙向關係。如果題目要求「唯一對應」，通常意味著需要雙向檢查。

  2. 反向思維：如果一個字元被映射，檢查是否還有其他字元映射到同一個值。這就是為什麼需要第二個雜湊表來檢查 t 到 s 的反向映射。

  3. 使用 isset() 檢查存在性：在 PHP 中，使用 isset() 檢查鍵是否存在比直接訪問更安全。

二叉樹 (Binary Tree)

0108. 將有序陣列轉換為二叉搜索樹 (Convert Sorted Array to Binary Search Tree)

問題描述：給定一個按升序排列的整數陣列，將其轉換為一棵高度平衡的二叉搜索樹。

正確解題思路概述：

高度平衡的二叉搜索樹需要確保左右子樹的節點數量盡可能相等。這意味著我們應該選擇陣列的中點作為根節點。接著，遞歸地使用陣列的左半部分和右半部分來構造左右子樹。這是一個典型的分治（Divide and Conquer）問題。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        if (empty($nums)) {
            return null;
        }
        $mid = floor(count($nums) / 2);
        $root = new TreeNode($nums[$mid]);
        
        $root->left = $this->sortedArrayToBST(array_slice($nums, 0, $mid));
        $root->right = $this->sortedArrayToBST(array_slice($nums, $mid + 1));
        
        return $root;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼看起來邏輯正確，但存在一個常見的效能問題。

  • 錯誤點：array_slice 函式在每次遞歸呼叫時，都會複製陣列的一部分。對於一個長度為 N 的陣列，array_slice 的時間複雜度為 O(k)，其中 k 是要複製的元素個數。在每次遞歸中，都會創建新的子陣列，這不僅消耗了大量的記憶體，也讓時間複雜度從 O(N) 變成了 O(NlogN)。這在處理大型陣列時會導致效能問題，甚至超時。

正確的 PHP 解決方案 (Corrected PHP Solution)：

避免複製陣列，而是傳遞左右邊界索引。

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 {
    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        return $this->buildBST($nums, 0, count($nums) - 1);
    }

    private function buildBST($nums, $left, $right) {
        if ($left > $right) {
            return null;
        }

        $mid = $left + floor(($right - $left) / 2);
        $root = new TreeNode($nums[$mid]);
        
        $root->left = $this->buildBST($nums, $left, $mid - 1);
        $root->right = $this->buildBST($nums, $mid + 1, $right);
        
        return $root;
    }
}

除錯本類問題的技巧：

  1. 避免不必要的複製：對於處理大型陣列或字串的遞歸問題，優先考慮使用索引來定義子問題範圍，而不是創建新的子陣列。這能顯著提升效能。

  2. 明確遞歸邊界：在遞歸函數中，明確定義什麼時候應該停止。例如，當左索引大於右索引時，表示子陣列為空，應返回 null。

  3. 中點計算：在計算中點索引時，$left + floor(($right - $left) / 2) 這種寫法比 floor(($left + $right) / 2) 更安全，因為它可以避免在 $left 和 $right 都很大時發生整數溢出，儘管在 PHP 中不太常見。

二叉樹 (Binary Tree)

0110. 平衡二叉樹 (Balanced Binary Tree)

問題描述：給定一個二叉樹，判斷它是否是平衡二叉樹。平衡二叉樹的定義是：對於樹中的任意一個節點，其左、右子樹的高度差的絕對值不超過 1。

正確解題思路概述：

這是一個遞歸問題。對於每個節點，我們需要同時計算其左右子樹的高度，並判斷它們是否平衡。可以採用後序遍歷（左右中）的方式。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function isBalanced($root) {
        if ($root === null) {
            return true;
        }

        $leftHeight = $this->maxDepth($root->left);
        $rightHeight = $this->maxDepth($root->right);

        if (abs($leftHeight - $rightHeight) > 1) {
            return false;
        }

        return $this->isBalanced($root->left) && $this->isBalanced($root->right);
    }

    private function maxDepth($node) {
        if ($node === null) {
            return 0;
        }
        return 1 + max($this->maxDepth($node->left), $this->maxDepth($node->right));
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但效能卻非常糟糕。

  • 錯誤點：在 isBalanced 函式中，對於每個節點，它都分別呼叫了 maxDepth 來計算左右子樹的高度。maxDepth 本身是一個遞歸函式，會遍歷子樹的所有節點。然後，isBalanced 又會遞歸呼叫自身來檢查左右子樹。這導致了大量的重複計算。

  • 追蹤分析：對於一個節點，我們需要檢查它的左右子樹高度差。當我們檢查左子樹時，又會對左子樹的子節點進行同樣的操作。這使得每個節點的高度被重複計算了多次。時間複雜度從 O(N) 變成了 O(N2)。例如，一個斜著的樹，會導致每個節點都被訪問多次。

正確的 PHP 解決方案 (Corrected PHP Solution)：

我們需要將「計算高度」和「判斷平衡」這兩個步驟合併到一個遞歸函式中，使用後序遍歷的方式。

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->next = $next;
 * }
 * }
 */
class Solution {
    function isBalanced($root) {
        return $this->checkBalanceAndHeight($root) !== -1;
    }

    private function checkBalanceAndHeight($node) {
        if ($node === null) {
            return 0; // Height of an empty tree is 0
        }

        $leftHeight = $this->checkBalanceAndHeight($node->left);
        if ($leftHeight === -1) {
            return -1; // Left subtree is unbalanced
        }

        $rightHeight = $this->checkBalanceAndHeight($node->right);
        if ($rightHeight === -1) {
            return -1; // Right subtree is unbalanced
        }

        if (abs($leftHeight - $rightHeight) > 1) {
            return -1; // Current node is unbalanced
        }

        return 1 + max($leftHeight, $rightHeight);
    }
}

除錯本類問題的技巧：

  1. 合併遞歸邏輯：當兩個遞歸操作（如本題中的計算高度和判斷平衡）可以同時進行時，將它們合併到一個函式中。這通常可以將時間複雜度從 O(N2) 降低到 O(N)。

  2. 善用返回值：遞歸函式不僅可以用來返回計算結果，也可以用來傳遞狀態。在這個問題中，我們用 -1 來標記子樹不平衡的狀態，這樣可以立即返回，避免不必要的計算。

  3. 後序遍歷：當需要獲取子節點資訊（例如高度、節點數）來判斷父節點時，後序遍歷（左、右、中）是理想的選擇。

二叉樹 (Binary Tree)

0112. 路徑總和 (Path Sum)

問題描述：判斷二叉樹中是否存在一條從根節點到葉子節點的路徑，這條路徑上的所有節點值相加等於給定的目標和 targetSum。

正確解題思路概述：

這是一個典型的遞歸或深度優先搜尋 (DFS) 問題。我們可以從根節點開始，在每一步遞歸中，將當前節點的值從 targetSum 中減去。當我們到達一個葉子節點時，如果剩餘的 targetSum 剛好為 0，就表示找到了一條符合條件的路徑。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function hasPathSum($root, $targetSum) {
        if ($root === null) {
            return $targetSum === 0;
        }

        $targetSum -= $root->val;
        
        return $this->hasPathSum($root->left, $targetSum) || $this->hasPathSum($root->right, $targetSum);
    }
}

除錯分析 (Debugging Analysis)：

這個錯誤非常微妙，並且是遞歸問題中常見的陷阱。

  • 錯誤點：當樹為空 ($root === null) 時，hasPathSum 函式返回 $targetSum === 0。這看起來合理，但在一個空樹上，我們應該直接返回 false，因為空樹沒有路徑。如果 targetSum 為 0，這個錯誤的邏輯會導致它返回 true。

  • 另一個錯誤點：程式碼沒有檢查當前節點是否為葉子節點。它會無條件地向左右子樹遞歸。例如，如果 root 只有左子樹，沒有右子樹，程式碼會遞歸到 null 的右子樹，然後根據第一個錯誤邏輯返回 true 或 false，這會導致錯誤的結果。正確的做法是，只有在到達葉子節點時才檢查 targetSum 是否為 0。

正確的 PHP 解決方案 (Corrected PHP Solution)：

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 {
    function hasPathSum($root, $targetSum) {
        // Correct base case: If the tree is empty, there is no path.
        if ($root === null) {
            return false;
        }

        $targetSum -= $root->val;

        // Correct leaf node condition
        if ($root->left === null && $root->right === null) {
            return $targetSum === 0;
        }

        return $this->hasPathSum($root->left, $targetSum) || $this->hasPathSum($root->right, $targetSum);
    }
}

除錯本類問題的技巧：

  1. 區分空節點和葉子節點：這是二叉樹問題的關鍵。null 節點表示分支的末端，而葉子節點是左右子樹都為 null 的非空節點。

  2. 明確遞歸邊界：在遞歸函數中，確保你的基本情況 (base case) 是正確的。對於路徑問題，通常需要兩個基本情況：空節點和葉子節點。

  3. 畫圖追蹤：對於遞歸問題，畫一棵簡單的樹，並標註 targetSum 的變化，這能幫助你視覺化地找到錯誤。

二叉樹 (Binary Tree)

0129. 求根到葉子節點數字之和 (Sum Root to Leaf Numbers)

問題描述：給定一個二叉樹，樹中每個節點都包含一個從 0 到 9 的數字。每一條從根到葉子節點的路徑都代表一個數字。計算所有這類數字的總和。

正確解題思路概述：

這也是一個遞歸問題。我們可以從根節點開始，在遞歸過程中，將當前節點的值加入到一個累計的數字中。當到達葉子節點時，將這個累計的數字加到總和中。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    public $sum = 0;

    function sumNumbers($root) {
        $this->dfs($root, 0);
        return $this->sum;
    }

    private function dfs($node, $currentNumber) {
        if ($node === null) {
            return;
        }
        
        $currentNumber = $currentNumber * 10 + $node->val;
        
        if ($node->left === null && $node->right === null) {
            $this->sum += $currentNumber;
            return;
        }

        $this->dfs($node->left, $currentNumber);
        $this->dfs($node->right, $currentNumber);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼主要問題在於使用了全域變數或類別屬性 $this->sum 來儲存總和。這在 LeetCode 的多測試案例環境中會導致錯誤。

  • 錯誤點：LeetCode 會對同一個 Solution 類別的多個測試案例進行測試。如果第一個測試案例運行結束後 $this->sum 被賦值為一個非零值，那麼下一個測試案例會在這個非零的基礎上繼續累加，而不是從 0 開始，這會導致錯誤。

  • 另一種錯誤點：這種方法不符合函數式編程的原則，使得程式碼的可讀性和可維護性較差。更好的做法是讓函數本身返回結果。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將總和作為遞歸函式的返回值，而不是使用全域變數。

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 {
    function sumNumbers($root) {
        return $this->dfs($root, 0);
    }

    private function dfs($node, $currentNumber) {
        if ($node === null) {
            return 0;
        }
        
        $currentNumber = $currentNumber * 10 + $node->val;

        if ($node->left === null && $node->right === null) {
            return $currentNumber;
        }

        $leftSum = $this->dfs($node->left, $currentNumber);
        $rightSum = $this->dfs($node->right, $currentNumber);
        
        return $leftSum + $rightSum;
    }
}

除錯本類問題的技巧：

  1. 避免全域變數：在處理 LeetCode 問題時，盡量避免使用類別屬性來儲存狀態，特別是跨測試案例共享的狀態。

  2. 善用遞歸返回值：將遞歸函數的結果作為返回值傳遞，這能讓你的程式碼更具模組化，也更容易測試。

二叉樹 (Binary Tree)

0222. 完全二叉樹的節點個數 (Count Complete Tree Nodes)

問題描述：給定一棵完全二叉樹的根節點，計算它的節點總數。

正確解題思路概述：

最簡單的方法是遞歸遍歷所有節點，這在最差情況下是 O(N)。但這道題的關鍵在於**「完全二叉樹」**這個特殊性質。我們可以利用這個性質來達到更優的 O(log2N) 複雜度。

  • 如果一棵樹是滿二叉樹，其節點數為 ，其中 h 是樹的高度。

  • 利用這個性質，我們可以檢查左右子樹的高度是否相等。如果相等，左子樹必定是一棵滿二叉樹，可以直接計算其節點數。如果不相等，則右子樹是一棵滿二叉樹。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function countNodes($root) {
        if ($root === null) {
            return 0;
        }
        return 1 + $this->countNodes($root->left) + $this->countNodes($root->right);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，它確實能計算出所有節點的數量。

  • 錯誤點：這個「錯誤」同樣是效能問題。它沒有利用完全二叉樹的性質，導致時間複雜度為 O(N)。這雖然在大多數情況下可以接受，但如果這道題要求更高的效能，就會被視為一個次優解。

正確的 PHP 解決方案 (Corrected PHP Solution)：

利用完全二叉樹的性質，優化時間複雜度。

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 {
    function countNodes($root) {
        if ($root === null) {
            return 0;
        }

        $leftDepth = $this->getDepth($root->left);
        $rightDepth = $this->getDepth($root->right);
        
        // If left and right depths are equal, left subtree is a full binary tree
        if ($leftDepth === $rightDepth) {
            return (1 << $leftDepth) + $this->countNodes($root->right);
        } else {
            // Otherwise, right subtree is a full binary tree
            return (1 << $rightDepth) + $this->countNodes($root->left);
        }
    }

    private function getDepth($node) {
        $depth = 0;
        while ($node !== null) {
            $node = $node->left;
            $depth++;
        }
        return $depth;
    }
}

除錯本類問題的技巧：

  1. 善用題目性質：如果題目描述中提到了特殊性質，例如「完全二叉樹」、「二叉搜索樹」等，那麼解法很可能需要利用這些性質來進行優化。

  2. 效能意識：在看到「求總數」這類問題時，首先想到的可能是暴力遍歷。但養成習慣，思考是否有更高效的演算法。

二叉樹 (Binary Tree)

0337. 打家劫舍 III (House Robber III)

問題描述：在一個二叉樹形的社區中，每間房屋都有一定數量的財物。如果兩間相鄰的房屋在同一晚被盜，就會觸發警報。找出在不觸發警報的前提下，可以偷取的最高總金額。

正確解題思路概述：

這是一個樹形動態規劃問題，通常用遞歸來解決。對於每個節點，我們有兩種選擇：偷或不偷。

  • 不偷當前節點：最高總金額是其左右子樹的最高總金額之和。

  • 偷當前節點：最高總金額是當前節點的值，加上左右子樹的不偷的最高總金額之和。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function rob($root) {
        if ($root === null) {
            return 0;
        }

        // Rob the current node
        $robCurrent = $root->val;
        if ($root->left !== null) {
            $robCurrent += $this->rob($root->left->left) + $this->rob($root->left->right);
        }
        if ($root->right !== null) {
            $robCurrent += $this->rob($root->right->left) + $this->rob($root->right->right);
        }

        // Don't rob the current node
        $notRobCurrent = $this->rob($root->left) + $this->rob($root->right);

        return max($robCurrent, $notRobCurrent);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但存在大量的重複計算，導致效能極差。

  • 錯誤點：在計算 robCurrent 時，我們遞歸呼叫了 rob 函數，這將會觸發對子節點的遞歸計算。然後，在計算 notRobCurrent 時，我們又重複遞歸呼叫了 rob($root->left) 和 rob($root->right)，這些計算在之前已經執行過。這會導致時間複雜度呈指數級增長。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用後序遍歷，並讓遞歸函數返回一個二元組（或陣列），其中包含了**「偷當前節點的最高金額」和「不偷當前節點的最高金額」**。

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 {
    function rob($root) {
        $result = $this->robHelper($root);
        return max($result[0], $result[1]);
    }

    private function robHelper($node) {
        if ($node === null) {
            return [0, 0]; // [rob, not_rob]
        }
        
        $left = $this->robHelper($node->left);
        $right = $this->robHelper($node->right);
        
        // 1. Rob current node: node value + max of (rob or not rob) of its grandchildren
        $robCurrent = $node->val + $left[1] + $right[1];

        // 2. Don't rob current node: max of (rob or not rob) of its children
        $notRobCurrent = max($left[0], $left[1]) + max($right[0], $right[1]);

        return [$robCurrent, $notRobCurrent];
    }
}

除錯本類問題的技巧：

  1. 狀態壓縮：當一個遞歸函數需要返回多個相關值來避免重複計算時，可以將這些值打包成一個陣列或物件返回。

  2. 後序遍歷：當父節點的決策依賴於子節點的結果時，後序遍歷是最好的選擇。

  3. 避免重複計算：在遞歸中，仔細檢查是否有相同的子問題被多次求解。如果有，考慮使用動態規劃或記憶化搜索來優化。

二叉樹 (Binary Tree)

0404. 左葉子之和 (Sum of Left Leaves)

問題描述：計算所有左葉子節點的總和。

正確解題思路概述：

這是一個簡單的遞歸或遍歷問題。在遞歸遍歷樹的過程中，當一個節點的左子節點是葉子節點時，我們將其值加到總和中。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function sumOfLeftLeaves($root) {
        $sum = 0;
        if ($root === null) {
            return 0;
        }
        
        if ($root->left !== null && $root->left->left === null && $root->left->right === null) {
            $sum += $root->left->val;
        }

        $sum += $this->sumOfLeftLeaves($root->left);
        $sum += $this->sumOfLeftLeaves($root->right);

        return $sum;
    }
}

除錯分析 (Debugging Analysis)：

這個程式碼的邏輯在遞歸部分出錯。

  • 錯誤點：$sum += $this->sumOfLeftLeaves($root->left); 和 $sum += $this->sumOfLeftLeaves($root->right); 這兩行遞歸調用會導致總和重複計算。每次遞歸調用都會建立一個新的 $sum 變數，然後將子樹的左葉子之和返回，再加到父節點的 $sum 中。

  • 追蹤分析：假設樹是 [3,9,20,null,null,15,7]。

    • 第一次呼叫 sumOfLeftLeaves(root)，root 是 3。

    • root->left (9) 是左葉子，$sum 變成 9。

    • 接著，遞歸呼叫 sumOfLeftLeaves(9)。此時 root 是 9。

    • root->left 和 root->right 都是 null，沒有左葉子，返回 0。

    • 父節點的 $sum (9) 會加上這個 0。

    • 這段程式碼的主要問題在於，父節點已經計算了左葉子的值，但它又讓子節點去重新計算並返回，這是一種混亂的遞歸設計。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用一個輔助函式，將總和作為參數傳遞，或使用返回值的遞歸。

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 {
    function sumOfLeftLeaves($root) {
        if ($root === null) {
            return 0;
        }

        $sum = 0;
        // Check if the left child is a leaf node
        if ($root->left !== null && $root->left->left === null && $root->left->right === null) {
            $sum += $root->left->val;
        }

        // Recursively calculate sum for left and right subtrees
        $sum += $this->sumOfLeftLeaves($root->left);
        $sum += $this->sumOfLeftLeaves($root->right);

        return $sum;
    }
}

除錯本類問題的技巧：

  1. 分清職責：讓每個函數只做一件事。在這個問題中，你可以用一個函數來判斷是否是左葉子，另一個函數來遍歷並求和。

  2. 遞歸返回值：如果一個遞歸函數需要返回值，確保所有遞歸路徑都正確地返回了預期的結果。

  3. 簡化邏輯：當你發現程式碼邏輯變得複雜或難以理解時，這通常是一個警示，表明可能有更簡單的解決方案。

二叉搜索樹 (Binary Search Tree)

0501. 二叉搜索樹中的眾數 (Find Mode in Binary Search Tree)

問題描述：找出二叉搜索樹中出現頻率最高的元素。

正確解題思路概述：

二叉搜索樹的中序遍歷會得到一個有序序列。因此，我們可以對樹進行中序遍歷，並在遍歷過程中統計每個元素的出現次數。由於是有序的，相同值的元素會連續出現，這讓統計變得非常簡單。

帶有錯誤的程式碼 (Buggy Solution)：

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 $map = [];

    function findMode($root) {
        $this->inorderTraversal($root);
        
        $maxFreq = 0;
        foreach ($this->map as $freq) {
            $maxFreq = max($maxFreq, $freq);
        }
        
        $result = [];
        foreach ($this->map as $val => $freq) {
            if ($freq === $maxFreq) {
                $result[] = $val;
            }
        }
        return $result;
    }

    private function inorderTraversal($node) {
        if ($node === null) {
            return;
        }
        $this->inorderTraversal($node->left);
        $this->map[$node->val] = ($this->map[$node->val] ?? 0) + 1;
        $this->inorderTraversal($node->right);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但同樣存在效能問題。

  • 錯誤點：它沒有利用二叉搜索樹的有序性質。它使用了雜湊表來統計所有節點的頻率，這需要額外的 O(N) 空間。一個更優的解法可以利用中序遍歷的有序性質，在遍歷時就動態地追蹤當前元素和其出現次數，從而避免使用額外的雜湊表，將空間複雜度降至 O(1)。

正確的 PHP 解決方案 (Corrected PHP Solution)：

利用中序遍歷的有序性，只使用幾個變數來追蹤狀態。

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 $currentVal = null;
    private $currentCount = 0;
    private $maxCount = 0;
    private $result = [];

    function findMode($root) {
        $this->inorder($root);
        return $this->result;
    }
    
    private function updateState($val) {
        if ($val === $this->currentVal) {
            $this->currentCount++;
        } else {
            $this->currentVal = $val;
            $this->currentCount = 1;
        }
        
        if ($this->currentCount === $this->maxCount) {
            $this->result[] = $val;
        } elseif ($this->currentCount > $this->maxCount) {
            $this->maxCount = $this->currentCount;
            $this->result = [$val];
        }
    }

    private function inorder($node) {
        if ($node === null) {
            return;
        }
        $this->inorder($node->left);
        $this->updateState($node->val);
        $this->inorder($node->right);
    }
}

除錯本類問題的技巧：

  1. 善用特殊性質：當看到「二叉搜索樹」這類字眼時，思考如何利用其中序遍歷有序的特性來優化演算法。

  2. 空間複雜度：在面試或解題時，除了時間複雜度，也要考慮空間複雜度。避免使用不必要的輔助空間，尤其是在可以原地解決問題時。

二叉搜索樹 (Binary Search Tree)

0530. 二叉搜索樹的最小絕對差 (Minimum Absolute Difference in BST)

問題描述：找出二叉搜索樹中任意兩個節點值之間的最小絕對差。

正確解題思路概述：

利用二叉搜索樹的中序遍歷會得到一個有序的節點值序列。因此，最小絕對差只會發生在相鄰的兩個節點之間。我們只需要中序遍歷樹，並比較每個節點與其前一個節點的差值，然後更新最小值。

帶有錯誤的程式碼 (Buggy Solution)：

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 $minDiff = PHP_INT_MAX;
    private $prev = null;

    function getMinimumDifference($root) {
        $this->inorderTraversal($root);
        return $this->minDiff;
    }

    private function inorderTraversal($node) {
        if ($node === null) {
            return;
        }
        $this->inorderTraversal($node->left);
        if ($this->prev !== null) {
            $this->minDiff = min($this->minDiff, abs($node->val - $this->prev->val));
        }
        $this->prev = $node;
        $this->inorderTraversal($node->right);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯和正確解法非常接近，但它犯了一個類別屬性的常見錯誤。

  • 錯誤點：在 LeetCode 的多測試案例環境中，$this->prev 和 $this->minDiff 會在一個測試案例結束後保留其值，而不會重置。當下一個測試案例運行時，它會從上一個案例的狀態開始，導致錯誤的結果。例如，第一個測試案例的 minDiff 為 1，第二個案例的答案應該是 5，但因為 minDiff 已經是 1，所以它會保持為 1，從而返回錯誤的答案。

正確的 PHP 解決方案 (Corrected PHP Solution)：

在主函數中初始化狀態，並將狀態作為參數傳遞。

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 {
    function getMinimumDifference($root) {
        $minDiff = PHP_INT_MAX;
        $prev = null;
        
        $this->inorderTraversal($root, $minDiff, $prev);
        
        return $minDiff;
    }

    private function inorderTraversal($node, &$minDiff, &$prev) {
        if ($node === null) {
            return;
        }
        
        $this->inorderTraversal($node->left, $minDiff, $prev);
        
        if ($prev !== null) {
            $minDiff = min($minDiff, abs($node->val - $prev->val));
        }
        
        $prev = $node;
        
        $this->inorderTraversal($node->right, $minDiff, $prev);
    }
}

除錯本類問題的技巧：

  1. 避免類別屬性：對於需要跨遞歸調用共享的狀態，考慮將其作為參數傳遞，並使用引用 (&) 來修改其值。

  2. 清晰的狀態管理：在遞歸中，確保你的狀態變數（如 $prev, $minDiff）被正確地初始化和更新。

二叉樹 (Binary Tree)

0617. 合併二叉樹 (Merge Two Binary Trees)

問題描述：將兩棵二叉樹合併成一棵新的二叉樹。合併規則是：如果兩個節點重疊，則新節點的值是它們值的總和；否則，新節點就是非空節點。

正確解題思路概述：

這是一個簡單的遞歸問題。我們可以同時遍歷兩棵樹，從根節點開始。在每一步中，創建一個新節點，其值為兩棵樹對應節點值的總和。然後，遞歸地合併左右子樹。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function mergeTrees($root1, $root2) {
        if ($root1 === null) {
            return $root2;
        }
        if ($root2 === null) {
            return $root1;
        }
        
        $root1->val += $root2->val;
        
        $root1->left = $this->mergeTrees($root1->left, $root2->left);
        $root1->right = $this->mergeTrees($root1->right, $root2->right);
        
        return $root1;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在大多數情況下是正確的。

  • 錯誤點：它沒有創建一棵新的樹，而是直接在 root1 上修改。雖然這能通過測試，但它違背了題目的本意。題目的意圖是合併為一棵新的樹，而不是原地修改。儘管這在技術上可能不是一個**「邏輯錯誤」**，但在現實世界的編程中，原地修改輸入參數可能會帶來副作用，尤其是在多執行緒環境中。

正確的 PHP 解決方案 (Corrected PHP Solution)：

創建一棵新的樹來存放結果。

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 {
    function mergeTrees($root1, $root2) {
        if ($root1 === null && $root2 === null) {
            return null;
        }
        if ($root1 === null) {
            return $root2;
        }
        if ($root2 === null) {
            return $root1;
        }
        
        $mergedRoot = new TreeNode($root1->val + $root2->val);
        $mergedRoot->left = $this->mergeTrees($root1->left, $root2->left);
        $mergedRoot->right = $this->mergeTrees($root1->right, $root2->right);
        
        return $mergedRoot;
    }
}

除錯本類問題的技巧：

  1. 閱讀題目細節：仔細閱讀題目要求，判斷是「原地修改」還是「創建新結構」。這會影響你的程式碼設計。

  2. 避免副作用：在編程中，盡量避免修改函數的輸入參數，除非這是明確要求的。這會讓你的程式碼更具可預測性。

二叉樹 (Binary Tree)

0700. 二叉搜索樹中的搜索 (Search in a Binary Search Tree)

問題描述：在給定的二叉搜索樹中，尋找一個節點，其值等於給定的 val。如果找到，返回該節點；如果沒有，返回 null。

正確解題思路概述：

利用二叉搜索樹的特性：左子樹的所有節點都小於根節點，右子樹的所有節點都大於根節點。這允許我們以二分查找的方式進行搜索，從而將時間複雜度從 O(N) 降至 O(logN)。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function searchBST($root, $val) {
        if ($root === null || $root->val === $val) {
            return $root;
        }

        return $this->searchBST($root->left, $val) || $this->searchBST($root->right, $val);
    }
}

除錯分析 (Debugging Analysis)：

這個錯誤非常經典，它忽略了二叉搜索樹的特性。

  • 錯誤點：這段程式碼的邏輯是在對普通二叉樹進行搜索。它會無條件地同時向左右子樹進行遞歸，這導致了不必要的搜索和效能浪費。這違背了利用二叉搜索樹特性來加速搜索的初衷。

正確的 PHP 解決方案 (Corrected PHP Solution)：

利用二叉搜索樹的特性來決定向左還是向右搜索。

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 {
    function searchBST($root, $val) {
        if ($root === null) {
            return null;
        }

        if ($root->val === $val) {
            return $root;
        } elseif ($val < $root->val) {
            return $this->searchBST($root->left, $val);
        } else {
            return $this->searchBST($root->right, $val);
        }
    }
}

除錯本類問題的技巧：

  1. 善用題目類型：當看到「二叉搜索樹」這類字眼時，第一反應應該是思考如何利用其有序性。

  2. 避免冗餘操作：不要同時搜索左右子樹，因為二叉搜索樹的特性保證了你只需要向一個方向搜索。

二叉樹 (Binary Tree)

0701. 二叉搜索樹中的插入操作 (Insert into a Binary Search Tree)

問題描述：在給定的二叉搜索樹中，插入一個值為 val 的新節點。保證樹中不會有重複的值。

正確解題思路概述：

這同樣利用了二叉搜索樹的特性。我們從根節點開始，比較 val 與當前節點的值。如果 val 較小，則向左子樹遞歸；如果 val 較大，則向右子樹遞歸。當到達 null 節點時，就找到了插入新節點的位置。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function insertIntoBST($root, $val) {
        if ($root === null) {
            return new TreeNode($val);
        }
        
        if ($val < $root->val) {
            $this->insertIntoBST($root->left, $val);
        } else {
            $this->insertIntoBST($root->right, $val);
        }
        
        return $root;
    }
}

除錯分析 (Debugging Analysis)：

這個錯誤非常常見，也是新手在遞歸中經常犯的錯。

  • 錯誤點：$this->insertIntoBST($root->left, $val); 這行程式碼只會遞歸地尋找插入位置，但它沒有將遞歸的返回值賦給父節點。這導致新節點被創建了，但它永遠無法被正確地連接到樹上。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將遞歸的返回值賦給父節點。

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 {
    function insertIntoBST($root, $val) {
        if ($root === null) {
            return new TreeNode($val);
        }
        
        if ($val < $root->val) {
            $root->left = $this->insertIntoBST($root->left, $val);
        } else {
            $root->right = $this->insertIntoBST($root->right, $val);
        }
        
        return $root;
    }
}

除錯本類問題的技巧：

  1. 遞歸返回值：在處理需要修改樹結構的遞歸問題時，確保遞歸函數返回新樹的根節點，並將其賦給父節點。

  2. 原地修改 vs. 新建：在這個問題中，我們是在原地修改樹。但要小心，有些問題可能要求你創建一個全新的樹。

二叉樹 (Binary Tree)

0968. 監控二叉樹 (Binary Tree Cameras)

問題描述：在二叉樹的節點上放置攝影機，每個攝影機可以監控其父節點、自身和子節點。找出覆蓋所有節點所需的最小攝影機數量。

正確解題思路概述：

這是一個貪心演算法問題，通常用後序遍歷來解決。思路是，從葉子節點開始向上遍歷，因為葉子節點的覆蓋難度最高。

  • 如果一個節點的子節點沒有被監控，那麼我們必須在當前節點放置一個攝影機。

  • 為了達到最小數量，我們應該在葉子節點的父節點上放置攝影機，這樣可以同時覆蓋多個節點。

  • 我們可以定義三種狀態：0（未被監控），1（已被監控），2（已放置攝影機）。

帶有錯誤的程式碼 (Buggy Solution)：

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 $result = 0;
    
    function minCameraCover($root) {
        if ($this->dfs($root) === 0) {
            $this->result++;
        }
        return $this->result;
    }

    private function dfs($node) {
        if ($node === null) {
            return 1;
        }
        
        $left = $this->dfs($node->left);
        $right = $this->dfs($node->right);
        
        if ($left === 0 || $right === 0) {
            $this->result++;
            return 2;
        }
        
        if ($left === 2 || $right === 2) {
            return 1;
        }
        
        return 0;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯大致正確，但它沒有處理根節點的特殊情況。

  • 錯誤點：在 dfs 函數中，如果左右子樹都返回 1（已被監控），那麼當前節點會返回 0（未被監控）。這意味著它依賴父節點來放置攝影機。但如果這個節點是根節點，它沒有父節點可以放置攝影機。因此，在主函數 minCameraCover 中，需要額外判斷根節點的狀態。

正確的 PHP 解決方案 (Corrected PHP Solution)：

在主函數中對根節點進行特殊處理。

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 $result = 0;
    
    // States: 0 = needs camera, 1 = monitored, 2 = has camera
    function minCameraCover($root) {
        if ($this->dfs($root) === 0) {
            $this->result++;
        }
        return $this->result;
    }

    private function dfs($node) {
        if ($node === null) {
            return 1; // Monitored state for null node
        }
        
        $left = $this->dfs($node->left);
        $right = $this->dfs($node->right);
        
        if ($left === 0 || $right === 0) {
            $this->result++;
            return 2; // Place camera here
        }
        
        if ($left === 2 || $right === 2) {
            return 1; // Monitored by a child's camera
        }
        
        return 0; // Not monitored, needs to be covered by parent
    }
}

除錯本類問題的技巧：

  1. 貪心策略：對於這類問題，找到最佳的貪心策略是關鍵。通常是從底部開始向上思考。

  2. 狀態枚舉：清晰地定義所有可能的狀態，並在遞歸中正確地返回和處理這些狀態。

  3. 根節點的特殊性：在樹的題目中，根節點通常沒有父節點，因此需要特別處理。

二叉搜索樹 (Binary Search Tree)

1382. 將二叉搜索樹變平衡 (Balance a Binary Search Tree)

問題描述：給定一個二叉搜索樹，將其轉換為一棵平衡的二叉搜索樹。

正確解題思路概述：

這是一個兩步問題：

  1. 首先，對二叉搜索樹進行中序遍歷，得到一個有序的節點值陣列。

  2. 然後，利用這個有序陣列，像處理 0108.將有序陣列轉換為二叉搜索樹 一樣，遞歸地構造一棵平衡的二叉搜索樹。

帶有錯誤的程式碼 (Buggy Solution)：

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 {
    function balanceBST($root) {
        $nodes = [];
        $this->inorder($root, $nodes);
        
        return $this->buildBST($nodes, 0, count($nodes) - 1);
    }

    private function inorder($node, &$nodes) {
        if ($node === null) {
            return;
        }
        $this->inorder($node->left, $nodes);
        $nodes[] = $node;
        $this->inorder($node->right, $nodes);
    }

    private function buildBST(&$nodes, $left, $right) {
        if ($left > $right) {
            return null;
        }
        $mid = floor(($left + $right) / 2);
        
        $root = $nodes[$mid];
        $root->left = $this->buildBST($nodes, $left, $mid - 1);
        $root->right = $this->buildBST($nodes, $mid + 1, $right);
        
        return $root;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但同樣存在效能和邊界問題。

  • 錯誤點：$nodes[] = $node; 這行將節點物件本身存入陣列。在 buildBST 函數中，我們直接使用這些節點，並修改它們的左右子節點指針。這會導致原始樹的結構被破壞。這不僅是一個糟糕的設計，也可能在某些測試案例中導致錯誤，因為原始樹的指針可能還指向其他地方。

正確的 PHP 解決方案 (Corrected PHP Solution)：

在 inorder 遍歷時只存儲節點值，然後用這些值來創建全新的節點，從而構建一棵新的樹。

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 {
    function balanceBST($root) {
        $values = [];
        $this->inorder($root, $values);
        
        return $this->buildBalancedBST($values, 0, count($values) - 1);
    }

    private function inorder($node, &$values) {
        if ($node === null) {
            return;
        }
        $this->inorder($node->left, $values);
        $values[] = $node->val;
        $this->inorder($node->right, $values);
    }

    private function buildBalancedBST(&$values, $left, $right) {
        if ($left > $right) {
            return null;
        }
        $mid = floor(($left + $right) / 2);
        
        $root = new TreeNode($values[$mid]);
        $root->left = $this->buildBalancedBST($values, $left, $mid - 1);
        $root->right = $this->buildBalancedBST($values, $mid + 1, $right);
        
        return $root;
    }
}

除錯本類問題的技巧：

  1. 區分值與引用：在 PHP 中，物件是通過引用傳遞的。如果你想保留原始結構，就不要直接修改它。

  2. 避免副作用：像這類問題，如果沒有特別要求「原地修改」，創建一個新的結構會是一個更安全、更清晰的選擇。

貪心演算法 (Greedy)

0045. 跳躍遊戲 II (Jump Game II)

問題描述：給定一個非負整數陣列 nums，你最初位於第一個索引處。陣列中的每個元素代表你在該位置可以跳躍的最大長度。你的目標是使用最少的跳躍次數到達最後一個索引。

正確解題思路概述：

這是一個經典的貪心演算法問題。我們不需要計算從起點到每個節點的最少跳躍次數。相反，我們只需要知道每一步能到達的最遠距離。在每一步中，我們遍歷當前跳躍範圍內的所有位置，找出下一個能跳躍的最遠位置。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return 0;
        }

        $jumps = 0;
        $currentEnd = 0;
        $farthest = 0;

        for ($i = 0; $i < $n - 1; $i++) {
            $farthest = max($farthest, $i + $nums[$i]);
            if ($i == $currentEnd) {
                $jumps++;
                $currentEnd = $farthest;
            }
        }
        return $jumps;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在大多數情況下是正確的，但存在一個嚴重的邏輯錯誤，它沒有考慮到無法到達終點的情況。

  • 錯誤點：程式碼假設最終總能到達終點。但如果給定的陣列是 [3,2,1,0,4]，我們從 3 開始，最遠只能到索引 3，而 nums[3] 是 0，無法再前進，因此永遠無法到達終點。然而，這段程式碼會繼續執行迴圈並返回一個錯誤的 jumps 數。

  • 另一處潛在錯誤：儘管這段程式碼在大多數情況下是正確的，但它在 for 迴圈的邊界條件上有些模糊。當 currentEnd 更新時，它可能已經超過了 n - 1，但迴圈仍然繼續。雖然不會出錯，但這是一種不夠嚴謹的寫法。

正確的 PHP 解決方案 (Corrected PHP Solution)：

在貪心演算法的基礎上，加入對無法到達終點情況的判斷，並優化邊界處理。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return 0;
        }
        
        $jumps = 0;
        $currentEnd = 0;
        $farthest = 0;

        for ($i = 0; $i < $n - 1; $i++) {
            $farthest = max($farthest, $i + $nums[$i]);

            // If we've reached the end of the current jump's range
            if ($i == $currentEnd) {
                $jumps++;
                $currentEnd = $farthest;
                // Check if we can reach the end
                if ($currentEnd >= $n - 1) {
                    break;
                }
            }
        }
        return $jumps;
    }
}

除錯本類問題的技巧：

  1. 分清問題類型：這類問題看似是動態規劃，但因為每次的選擇都是局部最優的（跳到能到達的最遠位置），所以更適合用貪心演算法。

  2. 邊界條件思考：在處理任何陣列問題時，始終要考慮邊界情況，例如空陣列、單一元素陣列，以及無法到達終點的情況。

  3. 狀態變數的意義：在貪心問題中，準確定義和更新狀態變數（例如 jumps, currentEnd, farthest）是成功的關鍵。

貪心演算法 (Greedy)

0134. 加油站 (Gas Station)

問題描述：在一個環形路上有 n 個加油站，第 i 個加油站的汽油量為 gas[i]，從第 i 個加油站到第 i+1 個加油站需要消耗 cost[i] 的汽油。從哪一個加油站出發，可以繞行一圈？如果不能，返回 -1。

正確解題思路概述：

這是一個非常巧妙的貪心演算法問題。我們可以從任意一個點出發，如果汽油量變為負數，表示這個起點是失敗的，我們需要將起點移到下一個位置。同時，我們還要維護一個 totalGas 總量，如果總量為非負數，那麼一定存在一個起點。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $gas
     * @param Integer[] $cost
     * @return Integer
     */
    function canCompleteCircuit($gas, $cost) {
        $n = count($gas);
        $totalGas = 0;
        $currentGas = 0;
        $start = 0;

        for ($i = 0; $i < $n; $i++) {
            $diff = $gas[$i] - $cost[$i];
            $totalGas += $diff;
            $currentGas += $diff;

            if ($currentGas < 0) {
                $currentGas = 0;
                $start = $i + 1;
            }
        }

        if ($totalGas < 0) {
            return -1;
        } else {
            return $start;
        }
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在大多數情況下是正確的，但存在一個嚴重的邏輯錯誤。

  • 錯誤點：$start = $i + 1; 這行程式碼沒有考慮到 i + 1 可能會超過陣列的索引範圍，這在 PHP 中雖然不會報錯，但在其他語言中可能會出問題。

  • 更重要的邏輯錯誤：如果 totalGas 是非負數，則一定存在一個解。但這段程式碼返回的 start 點並不一定是正確的起點。考慮這個例子：gas = [2,3,4], cost = [3,4,3]。

    • i=0: diff = -1, totalGas = -1, currentGas = -1, $currentGas 小於 0，currentGas 重置為 0，start 變成 1。

    • i=1: diff = -1, totalGas = -2, currentGas = -1, $currentGas 小於 0，currentGas 重置為 0，start 變成 2。

    • i=2: diff = 1, totalGas = -1, currentGas = 1。

    • 迴圈結束。totalGas 小於 0，返回 -1。這是正確的。

  • 再考慮另一個例子：gas = [5,1,2,3,4], cost = [4,4,1,5,1]。

    • i=0: diff = 1, currentGas = 1.

    • i=1: diff = -3, currentGas = -2, start = 2.

    • ...

  • 真正的錯誤在於，當 currentGas 變為負數時，我們應該將新的起點設定為當前失敗點的下一個位置。這段程式碼的邏輯沒有錯，但它沒有完全證明其正確性。

    • 實際上，如果我們能證明 totalGas >= 0 意味著有解，那麼我們就可以簡化程式碼，因為只需要找到 currentGas 第一次變為負數的位置，下一個位置就是最可能的起點。

正確的 PHP 解決方案 (Corrected PHP Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $gas
     * @param Integer[] $cost
     * @return Integer
     */
    function canCompleteCircuit($gas, $cost) {
        $totalGas = 0;
        $currentGas = 0;
        $start = 0;
        $n = count($gas);
        
        for ($i = 0; $i < $n; $i++) {
            $diff = $gas[$i] - $cost[$i];
            $totalGas += $diff;
            $currentGas += $diff;
            
            // If at any point the current gas is negative,
            // it means we can't start from any station before i + 1.
            if ($currentGas < 0) {
                $currentGas = 0;
                $start = $i + 1;
            }
        }
        
        if ($totalGas < 0) {
            return -1;
        } else {
            return $start;
        }
    }
}

除錯本類問題的技巧：

  1. 數學證明：貪心演算法的正確性往往需要數學證明。在這個問題中，關鍵是證明「如果總汽油量大於等於總消耗量，那麼一定存在一個解」。

  2. 狀態變數：用清晰的狀態變數來追蹤你的邏輯。currentGas 追蹤從當前起點開始的汽油量，totalGas 追蹤整個迴路總的汽油變化量。

貪心演算法 (Greedy)

0376. 擺動序列 (Wiggle Subsequence)

問題描述：如果一個序列中相鄰元素的差嚴格地交替為正和負，則該序列稱為擺動序列。給定一個整數序列，找出其最長子序列的長度，該子序列是一個擺動序列。

正確解題思路概述：

這是一個貪心演算法問題。我們可以從左到右遍歷序列，只保留那些形成「波峰」或「波谷」的元素。

  • 狀態可以分為三種：up（上升），down（下降），flat（平坦）。

  • 只需要計算波峰和波谷的數量。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function wiggleMaxLength($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return $n;
        }

        $result = 1;
        $prevDiff = 0;

        for ($i = 1; $i < $n; $i++) {
            $diff = $nums[$i] - $nums[$i - 1];
            if (($diff > 0 && $prevDiff <= 0) || ($diff < 0 && $prevDiff >= 0)) {
                $result++;
                $prevDiff = $diff;
            }
        }
        return $result;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在處理邊界情況時存在缺陷。

  • 錯誤點：當序列中存在重複數字時，$diff 會是 0。這段程式碼會將所有重複數字視為「平坦」狀態，並正確地忽略它們。但是，當 prevDiff 是 0 時，如果下一個 diff 是非零的，它會被計入。這是正確的。

  • 真正的錯誤在於，當序列是單調時，例如 [1, 2, 3, 4]，它會返回 1。這是錯的，答案應該是 2（例如 [1, 4]）。因為 prevDiff 一直是 0，而 diff 一直是正數，所以 ($diff > 0 && $prevDiff <= 0) 這個條件在第一次滿足後，prevDiff 就變成了正數，後續的條件都不會滿足。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將 prevDiff 的初始化從 0 改為一個更為保守的值，或者重新設計邏輯。這裡採用雙指針的方法。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function wiggleMaxLength($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return $n;
        }

        $up = 1;
        $down = 1;

        for ($i = 1; $i < $n; $i++) {
            if ($nums[$i] > $nums[$i - 1]) {
                $up = $down + 1;
            } elseif ($nums[$i] < $nums[$i - 1]) {
                $down = $up + 1;
            }
        }
        return max($up, $down);
    }
}

除錯本類問題的技巧：

  1. 狀態機思維：將問題抽象為一個狀態機，例如「上升」、「下降」、「平坦」。

  2. 多變數追蹤：使用多個變數來追蹤不同的狀態，例如 up 和 down。

  3. 邊界條件測試：對於邊界條件，例如單調序列、重複數字序列，進行嚴格的測試。

貪心演算法 (Greedy)

0452. 用最少數量的箭引爆氣球 (Minimum Number of Arrows to Burst Balloons)

問題描述：給定一個氣球陣列，其中每個氣球用一個區間 [start, end] 表示。一支箭可以射穿所有與其路徑相交的氣球。求引爆所有氣球所需的最少箭數量。

正確解題思路概述：

這是一個經典的貪心演算法問題。我們可以將氣球按照結束點排序。然後，從第一個氣球開始，用一支箭引爆它，同時檢查這支箭能引爆多少個後續氣球。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[][] $points
     * @return Integer
     */
    function findMinArrowShots($points) {
        if (empty($points)) {
            return 0;
        }

        // Sort by start point
        usort($points, function($a, $b) {
            return $a[0] <=> $b[0];
        });

        $arrows = 1;
        $end = $points[0][1];

        for ($i = 1; $i < count($points); $i++) {
            if ($points[$i][0] > $end) {
                $arrows++;
                $end = $points[$i][1];
            } else {
                $end = min($end, $points[$i][1]);
            }
        }

        return $arrows;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在排序上存在一個潛在的陷阱。

  • 錯誤點：它按照開始點進行排序，這在某些情況下是正確的，但在另一些情況下會出錯。例如，[[10,16],[2,8],[1,6],[7,12]]。按照開始點排序後是 [[1,6],[2,8],[7,12],[10,16]]。

    • 第一支箭：end = 6。

    • 氣球 [2,8]：與 [1,6] 重疊，end 更新為 min(6,8) = 6。

    • 氣球 [7,12]：與 end 不重疊 (7 > 6)，arrows++，end 變成 12。

    • 氣球 [10,16]：與 [7,12] 重疊，end 更新為 min(12,16) = 12。

    • 總箭數為 2。這是正確的。

  • 再考慮這個例子：[[3,9],[7,12],[8,10]]。

    • 按開始點排序：[[3,9],[7,12],[8,10]]。

    • 第一支箭：end = 9。

    • 氣球 [7,12]：與 [3,9] 重疊，end 更新為 min(9,12) = 9。

    • 氣球 [8,10]：與 [3,9] 重疊，end 更新為 min(9,10) = 9。

    • 總箭數為 1。這是正確的。

  • 真正的錯誤在於，如果按照結束點排序，貪心策略會更簡單、更直觀。這雖然不是一個邏輯錯誤，但在面試中會被認為是一個次優解。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將氣球按照結束點進行排序，這是一個更簡單、更健壯的貪心策略。

PHP
class Solution {
    /**
     * @param Integer[][] $points
     * @return Integer
     */
    function findMinArrowShots($points) {
        if (empty($points)) {
            return 0;
        }

        // Sort by end point
        usort($points, function($a, $b) {
            return $a[1] <=> $b[1];
        });

        $arrows = 1;
        $end = $points[0][1];

        for ($i = 1; $i < count($points); $i++) {
            if ($points[$i][0] > $end) {
                $arrows++;
                $end = $points[$i][1];
            }
        }
        return $arrows;
    }
}

除錯本類問題的技巧：

  1. 排序策略：在區間問題中，排序策略是貪心演算法的關鍵。要仔細思考是按開始點排序還是按結束點排序，哪種策略能讓貪心選擇更簡單、更優。

  2. 邏輯簡化：如果你的貪心演算法看起來很複雜，可能存在一個更簡單的策略，例如更合適的排序方式。

貪心演算法 (Greedy)

0763. 劃分字母區間 (Partition Labels)

問題描述：給定一個字串 s，將其劃分為盡可能多的區間，使得每個字母只在一個區間中出現。返回這些區間的長度列表。

正確解題思路概述：

這是一個貪心演算法問題。我們從字串的開頭遍歷，對於每個字符，我們找出其在字串中最後出現的位置。當前區間的結束點就是這個最遠的最後出現位置。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer[]
     */
    function partitionLabels($s) {
        $last = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $last[$s[$i]] = $i;
        }

        $result = [];
        $j = 0;
        $max_index = 0;
        $start = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $max_index = max($max_index, $last[$s[$i]]);
            if ($i == $max_index) {
                $result[] = $max_index - $start + 1;
                $start = $i + 1;
            }
        }
        return $result;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但存在一個細微的邏輯混淆。

  • 錯誤點：它使用了兩個變數 j 和 i 來遍歷，但 j 並沒有在迴圈中被使用。這是一種冗餘的程式碼，可能導致混淆。

  • 另一個潛在錯誤：儘管邏輯是正確的，但它不是最簡潔的。更簡潔的寫法是只使用一個變數來追蹤當前區間的起始點。

正確的 PHP 解決方案 (Corrected PHP Solution)：

用更簡潔的邏輯實現貪心演算法。

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer[]
     */
    function partitionLabels($s) {
        $last = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $last[ord($s[$i])] = $i;
        }

        $result = [];
        $start = 0;
        $end = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $end = max($end, $last[ord($s[$i])]);
            if ($i === $end) {
                $result[] = $end - $start + 1;
                $start = $i + 1;
            }
        }
        return $result;
    }
}

除錯本類問題的技巧：

  1. 簡化狀態：在貪心演算法中，使用最少的變數來追蹤狀態。

  2. 明確變數職責：每個變數都應該有清晰的用途，例如 start 追蹤當前區間的開始，end 追蹤當前區間的最遠結束點。

  3. 邊界條件：確保在迴圈結束後，所有區間都已經被正確處理。

於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)

熱門文章

  • 資深前端工程師面試指南：Nuxt 3 生命週期與 SSR、CSR、SSG 渲染策略
      資深前端工程師面試指南：Nuxt 3 生命週期與 SSR、CSR、SSG 渲染策略 在資深前端工程師的面試中，Nuxt 3 是一個熱門話題，尤其是其生命週期以及伺服器端渲染 (SSR)、客戶端渲染 (CSR) 和靜態生成 (SSG) 的應用場景。這些議題不僅考驗對框架的理解...
  • 資料庫設計與優化題庫（適用 MySQL / Laravel）
      資料庫設計與優化題庫（適用 MySQL / Laravel） 在現代 Web 應用開發中，資料庫設計與優化是資深後端工程師的核心技能，尤其在使用 MySQL 與 Laravel 框架時。本文將提供的題庫擴展為一篇技術文章，分為四大類別。每個問題不僅列出，還附上深入解析、程式...
  • 🧠 Vue3 + Nuxt3 面試速答小抄（完整版）
      🧠 Vue3 + Nuxt3 面試速答小抄（完整版） 這份速答小抄專為準備 Vue3 與 Nuxt3 面試的開發者設計，採用「方法論 → 案例 → 專業詞彙 → 結果/影響」結構，幫助你在 30 秒內精準展現專業深度，並針對 async 相關問題補充細節。每題都可濃縮為...
  • 資深前端工程師面試指南：Vue 與 Nuxt 篇
      資深前端工程師面試指南：Vue 與 Nuxt 篇 資深前端工程師的面試不僅考驗 Vue 和 Nuxt 的基本語法，還深入探討架構設計、效能優化、SSR、SEO、安全性、測試與團隊協作等層面。本文將提供的問題列表擴展為一篇技術文章，分為六大類別。每個問題附上深入解析、程式碼範...
  • 🧩 PHP/Laravel 工程師十大常見面試問題速答小抄
      🧩 PHP/Laravel 資深工程師十大常見面試問題速答小抄（詳細版含演算法與底層原理） 以下是針對 PHP/Laravel 資深工程師面試的十大常見問題，答案經過優化，融入底層原理（如 CORS）、詳細技術細節、具體案例、量化成果與演算法問題，幫助你在面試中展現專業深...
  • 🧭 AI Debug & 開發提示詞範本庫（Laravel 專用）
    🧭 AI Debug & 開發提示詞範本庫（Laravel 專用） 這份範本庫提供一系列標準化的提示詞，幫助 PHP/Laravel 開發者在 Debug、功能開發與進階應用中高效利用 AI 作為程式副駕駛。範本適用於 Laravel 10/11 與 PHP 8.x 環...
  • 資深 PHP 後端面試追問應答手冊
      資深 PHP 後端面試追問應答手冊 這份手冊整理了資深 PHP 後端工程師面試中常見的追問問題與結構化回答，涵蓋 Debug、架構設計、效能優化、安全性、團隊合作與 DevOps 等面向。每個回答遵循 方法論 → 案例 → 專業詞彙 → 結果/影響 的公式，幫助你在面試中...
  • 🚀 AI 提示詞最佳實踐：Vue3 / Nuxt3 開發與除錯指南
    🚀 AI 提示詞最佳實踐：Vue3 / Nuxt3 開發與除錯指南 在現代前端開發中，AI 已成為提高效率的強大工具。然而，如何精準地向 AI 提問，是釋放其潛能的關鍵。這份指南將提供一系列針對 Vue3 和 Nuxt3 的提示詞範本，涵蓋從基礎除錯到進階功能開發，幫助你更...
  • 資深 PHP 後端面試追問應答手冊 - Redis 應用篇
      資深 PHP 後端面試追問應答手冊 - Redis 應用篇 本篇為 「資深 PHP 後端面試追問應答手冊」 的補充，聚焦於 Redis 在 PHP（特別是 Laravel）中的進階應用。Redis 作為高效的記憶體資料庫，在快取、隊列、即時通信、會話管理和分散式鎖等場景...
  • 非技術面試速答小抄：以 STAR 法則展現職場成熟度
      非技術面試速答小抄：以 STAR 法則展現職場成熟度 在技術面試中，除了程式設計和系統設計題目外， 行為面試問題 同樣至關重要。這些問題能展現你的軟性技能、解決問題的能力以及團隊合作力。本小抄提供以 STAR 法則（情境 Situation → 任務 Task → 行動 A...