Leetcode 筆記

# 前言

Leetcode 奮鬥筆記 出來混總是要還的, 一天一小步, 一年一大步。 Practice makes perfection

# 正文

# array

# 59. Spiral Matrix II

• 示意圖:
  

• 思路： 這題也是卡了我很久。 初次接觸這種題型, 我覺得可以先把圖畫出來, 先定義一下邏輯該怎麼走, 再來思考該怎麼實作 可參考上圖, 不同顏色代表不同的方向, 以及每次 insert 的範圍。 由上圖可以得到一些資訊
  (1) 第一層的 offset 為 1
  (2) 第二層開始, 每層的 offset 固定為 2
  (3) 若 $n / 2 !== 0, 則會有中間單獨一個數字存在, 其位置為 $res[floor($n / 2)][floor($n / 2)]
  (4) 可以看到, 輸出會是 [$n 個 array]
  (5) 共有 $n 層

有了上面歸納出的規則, 我們就可以開始實作, 具體參考代碼 時間複雜度, 由於需要 insert $n 的二次方個數, 所以時間複雜度會是 O(n 的平方)

• 題目連結
• solution example

class Solution {

    /**
     * @param Integer $n
     * @return Integer[][]
     */
    function generateMatrix($n) {
        $res = array_fill(0, $n, array_fill(0, $n, 0));
        $loop = $mid = (int) ($n / 2);
        $x = $y = 0;
        $offset = 1;
        $count = 1;
        
        while ($loop > 0) {
            $i = $x;
            $j = $y;
            
            for (; $i < $x + $n - $offset; $i++) {
                $res[$j][$i] = $count++;
            }
            
            for (; $j < $y + $n - $offset; $j++) {
                $res[$j][$i] = $count++;
            }
            
            for (; $i > $x; $i--) {
                $res[$j][$i] = $count++;
            }
            
            for (; $j > $y; $j--) {
                $res[$j][$i] = $count++;
            }
            
            $loop--;
            $x++;
            $y++;
            $offset+=2;
        }
        
        if ($n%2 !== 0) {
            $res[$mid][$mid] = $count;
        }
        
        return $res;
    }
}

# 雙指針

# 26. Remove Duplicates from Sorted Array

• 思路
  這題主要是用雙指針的概念 $left 由 $nums 的第一個 index 開始, 也就是 0 $right 開始往後 loop, 只要 $right 當下的值跟 $left 不相同, 那就代表不同的數出現了, 這時就可以更新 $left 指針, 由於 $nums 本身是 sorted array, 因此可以保證只要 loop 到的值不等同 $left, 那就一定是一個新的數, 不可能是 $left 已經跑過的數 由於 output 求的是重新排列後數組的長度 (不包含重複的數), 而 $left 是從 0 開始跑的, 因此要將 $left+1

• 題目連結

• solution example

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        $left = 0;
        for ($right = 0; $right < count($nums); $right++) {
            if ($nums[$right] !== $nums[$left]) {
                $nums[++$left] = $nums[$right];
            }
        }
        
        return $left+1;
    }
}

# 209. Minimum Size Subarray Sum

• 思路：
  這題最直接的暴力解法, 應該就是跑 double loop, 依序 loop 每一個 index, 並從每一個 index 再往後 loop, 不斷的相加更新 $sum 直到 $sum 大於 $target, 至此得到 $curLen, 然後重複這個步驟不停的 loop 直到比較完所有的 $curLen 並得到 $minLen, 這樣的時間複雜度為 O(n 的二次方)
  進階一點, 可使用 sliding window 概念 首先定義 $left, $right, 我們必須在演算法過程中不斷的更新這兩個數, 而這兩者的區間便是合法的 subarray, 而最小的 subarray 長度便是我們要的答案
  一開始 $right 往右 loop, 並與上一個 $right 相加維護 $sum, 只要 $sum 大於等於 $target, 至此, 便得到一個合法的 subarray, 此時我們記下他的長度 接下來我們更新 $left, 將 $sum - $left 直到 $sum 小於 $target, 在這個過程中, 如果 $sum 依然大於等於 $target, 這表示此 subarray 依然合法, 我們記下他的長度, 並將 $left++ 繼續 loop $left, 直到 $sum 小於等於 $target, 至此, subarray 不再合法, 我們可以再回到 $right 重複上面的步驟, 相當於不斷的在維護一個 sliding window, 並在過程中記下所有合法的 window 的長度, 而最小的 window 長度便是我們要的答案。 此解法的時間複雜度為 O(n)

• 題目連結

• solution example

class Solution {

    /**
     * @param Integer $target
     * @param Integer[] $nums
     * @return Integer
     */
    function minSubArrayLen($target, $nums) {
        $left = 0;
        $minLen = count($nums) + 1;

        for ($right = 0; $right < count($nums); $right++) {
            $curRV = $nums[$right];
            $sum += $curRV;

            while ($sum >= $target) {
                $curLen = $right - $left + 1;
                if ($curLen < $minLen) {
                    $minLen = $curLen;
                }

                $sum -= $nums[$left];
                $left++;
            }
        }

        if ($minLen === count($nums) + 1) {
            return 0;
        }

        return $minLen;
    }
}

# 167. Two Sum II - Input Array Is Sorted

首先先明確題目的目標, 是要取得 $numbers 中, 兩個數相加會剛好等於 $target 的這兩個數的位置, 即 index + 1

dictionary:
主要是維護一個 dictionary, loop $numbers, loop 到每一個 index 我們都用 $target 去扣掉當前的 value 得到 $diff, 並到 dictionary 去查這個 $diff 在嗎, 如果在, 那就代表兩個數相加等於 $target 這個條件是成立的, 接著我們只要取得當前的 index 以及 dictionary 當中等同 $diff 的 index 即可, 若是沒找到, 那就把當前的 value 放到 dictionary 中, 且記下其 index, 重複此步驟, 最多 loop 完整個 $numbers 即可得到這兩個數的位置 此法時間複雜度為 O(n), 空間複雜度為 O(n) (因為 dictionary 可能會有 n 個 index)

two pointer:
由於 $numbers 是一個 sorted array, 由小至大, 所以可以使用雙指針來解 首先定義 $left 以及 $right, 並將其相加得到一個 $sum, 如果 $sum 等同 $target, 直接破案拿到 $left 跟 $right 的位置, 如果 $sum 小於 $target, 代表 $left 可以往右移一格, 因為 $numbers 是有序的, 所以當前 $left 的下一個數勢必為此 array 中僅大於當前 $left 的數, 因此由此數來替換當前 $left 可取得下一個僅大於當前 $sum 的由兩個數相加的 $sum, 並用他再來跟 $target 比較一次 如果 $sum > $target, 原理同上, 則移動 $right 往左推, 取得下一個僅小於當前 $right 的數 此法時間複雜度為 O(n), 空間複雜度為 O(1) (不管 n 是多少, 都只維護 $left, $right, $sum)

• 題目連結
• 雙指針 solution example

class Solution {

    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $map = [];
        for ($i = 0; $i < count($numbers); $i++) {
            $diff = $target - $numbers[$i];
            if (array_key_exists($diff, $map)) {
                return [$map[$diff]+1, $i+1];
            }
            
            $map[$numbers[$i]] = $i;
        }
    }
}

• dictionary solution example

class Solution {

    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $left = 0;
        $right = count($numbers) - 1;

        while ($left < $right) {
            $sum = $numbers[$left] + $numbers[$right];

            if ($sum === $target) {
                return [$left+1, $right+1];
            } elseif ($sum > $target) {
                $right--;
            } elseif ($sum < $target) {
                $left++;
            }
        }

    }
}

# 二分查找

# 34. Find First and Last Position of Element in Sorted Array

• 思路
  這題的暴力解法, 可以使用單層 loop, 從 index 0 依序往後遍歷, 若無符合 target 則為 [-1, -1], 若有找到, 則記下為 $left & $right, 並繼續往後 loop, 若走到下個數時, $left 已存在, 則只更新 $right, 遍歷完整個 array 後可得到 $left & $right, 時間複雜度為 O(n)

較進階的解法: 由於這是一個 sorted array, 因此可以採用二分查找 首先必須找到 $left, 根據 solution 中的 code, (int) ($left + ($right - $left) / 2);
這邊確保了若 $left 與 $right 之間的數的數量非為基數 (也就是沒有一個剛好的中間點), 則 pivot 需是往左偏的, 這樣用意是為了避免無限迴圈, 因為 $nums[$pivot] >= $target, $right = $pivot, 如果遇到 $left 與 $right 緊鄰彼此, 這時 $pivot 是偏右的話, 那就會無限迴圈了 $nums[$pivot] >= $target, $right = $pivot, $nums 中同時有多個數值都為 $target 時, $right 會無限往左縮, 直到 $nums[$pivot] < $target , 此時代表 $target 位於 $pivot 的右邊, 所以調整 $left 往右

• 題目連結
• solution example

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        // 先假設 $target 不存在
        $result = [-1, -1];

        // 當 $left, $right 重疊也要斷開
        while ($left < $right) {
	    // $pivot 需偏左
            $pivot = (int) ($left + ($right - $left) / 2);
            if ($nums[$pivot] >= $target) {
                $right = $pivot;
            } else {
                $left = $pivot + 1;
            }
        }

	// 如果 $nums[$left] 不存在 (超出 $nums 範圍), 或 $nums[$left] 不等於 $target, 則代表不存在直接 return
        if (!isset($nums[$left]) || $nums[$left] !== $target) {
            return $result;
        }

        $result[0] = $left;

        $right = count($nums) - 1;
	// 邏輯同上, 只是 $pivot 需偏右, 這樣 $left 往右推時, 當 $left 與 $right 緊鄰時, $pivot 才會偏右, 若偏左, 則 `$nums[$pivot] <= $target` 這個條件會造成無限迴圈
        while ($left < $right) {
            $pivot = (int) ($left + ($right - $left) / 2 + 1);
            if ($nums[$pivot] <= $target) {
                $left = $pivot;
            } else {
                $right = $pivot - 1;
            }
        }

        $result[1] = $right;

        return $result;

    }
}

# 長度最小/大子數組

# 904 fruit into baskets

• 題目連結
• sliding window, 花了一天且又參考別人的 code 才終於搞懂, 基本上原理同一般的 sliding window, 用我自己可以理解的話來說, 假設 $fruits 是一個 array, 裡面有很多水果,
  目的是要取出兩種水果持續出現最長的那一段。 window 的 right 會一直往右跑, 每跑一次, 我們都將當前的水果種類以及總共的數量放到 basket 中, 並且 right 每跑一次, 我們都記下當前長度, 以及最大長度。 而當
  basket 出現了三種水果, 這表示這個 subarray 已經不合乎標準了, 我們需要從 window 的另一端開始往後推, 每推一次, 就把籃子中對應的該水果數量減一, 而當該水果的數量歸零, 我們就把該水果拿掉,
  這下子籃子裡頭又恢復成兩種水果, 此時 start 的位置就是合法的 subarray 的起點, 這邊花了我很多時間理解, 為什麼籃子變成兩種水果時, subarray 就合法了？ 因為我們是從 start 按順序往後推的, 而之前
  right 也是按順序往後跑, 一個個的將水果加到籃子裡去, 所以只要移除的順序跟放入的順序是一致的, 當籃子水果回到兩種時, 那就可以說, 籃子裡頭剩下的種類以及數量, 都是屬於 start 跟 right 之間的水果, 而此時這段
  array 也符合了條件, 因此可以再次計算它的長度, 以及比較是否可以取代最大長度

class Solution {
    /**
     * @param Integer[] $fruits
     * @return Integer
     */
    function totalFruit($fruits) {
        // $fruits array 中, 合法 subarray 的起點
        $start = 0;
        $maxLen = 0;
        // 籃子, 主要用來統計已放入的水果的種類 & 數量
        $basket = [];
        for ($current = 0; $current < count($fruits); $current++) {
            // 當前要放入的水果
            $currentFruit = $fruits[$current];
            // 將當前水果放入籃子
            $basket[$currentFruit]++;
            
            // 當籃子中有了三種水果, 這表示該 subarray 已經不合法, 要移動 start 位置使其再次合法
            while (count($basket) >= 3) {
                // 從籃子中, 將起點指向的水果數量減一
                $basket[$fruits[$start]]--;
                // 如果減完, 發現該水果數量已經歸零, 則從籃子中移除, 這樣就會恢復到兩種水果
                if ($basket[$fruits[$start]] === 0)
                    unset($basket[$fruits[$start]]);
                
                // 起點往後移
                $start++;
            }
            
            // 上面的 while loop 會讓 subarray 合法, 即將 start 移動到正確的位置, 所以一旦走到這行, 表示 start 已經位於正確的位置, 就可以計算目前合法 subarray 的長度
            $currentLen = $current - $start + 1;
            // 比較目前 subarray 的長度是否可以取代最大長度
            $maxLen = $currentLen > $maxLen ? $currentLen : $maxLen;
        }
        
        return $maxLen;
    }
}

# 76. Minimum Window Substring

目標是要在一個 array 中, 找到符合目標 array 的最小 subarray。 這樣講有點抽象, 請通過題目連結去看看題目敘述 這題的暴力解, 是跑雙層 loop, 先 loop 每一個 $s index, 再從每一個 $s
index 往後 loop, 直到找到符合目標的 subarray, 並記下 left 以及長度, 最後再回傳最小的 subarray, 時間複雜度是 O(n 的平方)。 較佳的解法, 採用 sliding window, 藉由維護一個
map, 由這個 map 來判斷 window 是否符合, 若是, 則比較長度, 若為最小長度, 則記下 left 以及長度 首先, 先建立一個 tMap, 這個 map 記錄著 $t 的 value 以及其數量, 接著開始 loop
$s, 我們將每一個存在於 $t 中的 value 都存入 $wMap 由於存入是依照 $s 的 loop 順序存入的, 因此當 $wMap[$index] <= $tMap[$index] 時, 代表距離目標又更近一步, 因此
$distance++, 若 $wMap[$index] > $tMap[$index], 則代表該 value 的數量在之前已經滿足了, 此時不需增加 $distance, 但一樣存入 $wMap 當 $distance 數量與 $t
的長度相等, 這代表 $wMap 中有的 value 已經滿足 $t 的要求, 由於題目要求的是最小的 subarray, 因此我們需要從 window 的 left 開始往前推, 不斷的從 $wMap 中依序拿掉 value, 只要
$distance 與 $t 的長度依然相等, 那就代表介於當下 $left 與 $right 之間的 window 是合法的, 我們取得這個 window 的長度並比較它是否是至今最小的, 如果是則記錄下當下的 left, 以及此長度 若
$distance 再度小於 $tLen, 則代表當下介於 $left 與 $right 之間的 window 已經不再合乎要求, 即停止 $left 的推進, 回到 $right, 繼續從 $right 往右邊遍歷 重複這個步驟,
直到完全遍歷 $s

• 題目連結
• solution example code:

class Solution {

    /**
     * @param String $s
     * @param String $t
     * @return String
     */
    function minWindow($s, $t) {
        $sLen = strlen($s);
        $tLen = strlen($t);
        $begin = $left = $right = $distance = 0;
        $minStr = '';
        $wMap = [];
        $tMap = [];
        $minLen = $sLen + 1;

        if ($sLen === 0 || $tLen === 0 || $sLen < $tLen) {
            return $minStr;
        }

        // 建立 $tMap
        for ($tIndex = 0; $tIndex < $tLen; $tIndex++) {
            $curTV = $t[$tIndex];
            $tMap[$curTV]++;
        }

        while ($right < $sLen) {
            $curRV = $s[$right];
            if (!array_key_exists($curRV, $tMap)) {
                $right++;
                continue;
            }

            $wMap[$curRV]++;

            // 表示距離目標近了一步, distance ++
            if ($wMap[$curRV] <= $tMap[$curRV]) {
                $distance++;
            }

            // 表示 window 已滿足條件
            while ($distance === $tLen) {
                $curLV = $s[$left];

                if (!array_key_exists($curLV, $tMap)) {
                    $left++;
                    continue;
                }

                $curLen = $right - $left + 1;

                // 如果當下的長度是最短的, 則記下 $left 以及長度
                if ($curLen < $minLen) {
                    $minLen = $curLen;
                    $begin = $left;
                }

                $wMap[$curLV]--;
		// 如果 $wMap 中的 value 與 $tMap 不再相等, 那代表 window 不再合法
                if ($wMap[$curLV] < $tMap[$curLV]) {
                    $distance--;
                }

                $left++;
            }

            $right++;
        }

        if ($minLen === $sLen + 1) {
            return '';
        }

        return substr($s, $begin, $minLen);
    }
}

# BST

# 653. Two Sum IV - Input is a BST

• 題目連結
• 先不管 root 是不是 BST 結構, two sum 的條件, 當 input 任兩個值相加等於 $k, 則結果為 true, 反之為 false 。 我們假設 $root 是一個 array, 最暴力的解法當然是直接雙層
  loop, 這樣時間複雜度會是 n 的平方, 好一點的解法是利用 map, 將 loop 跑過的 value 存到一個 map 中作為 key, 而下一個 loop 到的值, 只要用 $k - value 得到的值, 看看 map
  中存不存在這個 key, 如果存在, 代表這個 input 中確實有兩個 value 相加後等於 $k, 如果跑完 loop 都不存在, 那代表結果為 false, 這樣只需要跑一次 loop, 且 map 找 key 為 O(1),
  所以時間複雜度為 O(n), n 為 input 內的數量。 因為這題的 input 結構為 BST, 所以我們可以利用 BST 的特性, 用遞迴來跑, 然而其時間複雜度還是 O(n)
• solution example code:

/**
 * 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 TreeNode $root
     * @param Integer $k
     * @return Boolean
     */
    function findTarget($root, $k) {
        $map = [];
        
        return $this->find($root, $map, $k);
    }
    
    function find($node, &$map, $k) {
        if (is_null($node)) {
            return false;
        }
        
        $difference = $k - $node->val;
        
        if (array_key_exists($difference, $map)) {
            return true;
        }
        
        $map[$node->val] = true;
        
        return $this->find($node->left, $map, $k) || $this->find($node->right, $map, $k);
    }
}

# 977. Squares of a Sorted Array

暴力解： 最後使用較基本的解法, 先 square 整個 array, 在使用原生 sort(), 底層應使用歸併演算法, 因此時間複雜度為 O(n log n)
雙指針： 時間複雜度為 O(n)

• 題目連結
• solution example code 1:

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums) {
        $left = 0;
        $right = $end = count($nums) - 1;
        $output = array_fill(0, count($nums), 0);

        while ($left <= $right) {
            if ($nums[$left]**2 > $nums[$right]**2) {
                $output[$end] = $nums[$left]**2;
                $left++;
            } else {
                $output[$end] = $nums[$right]**2;
                $right--;
            }

            $end--;
        }

        return $output;
    }
}

• solution example code 2:

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums) {
        for ($i = 0; $i < count($nums); $i++) {
            $nums[$i] = $nums[$i]**2;
        }

        sort($nums);

        return $nums;
    }
}

# binary search

# 69. Sqrt(x)

暴力解： 直接從 0 開始 loop 到 $x, 用 ($x / $i === $i) 去判斷 $i 是否為解, 時間複雜度為 O(n)
二分法： 簡單來說, 如果二分法中, $pivot === $target 的答案不存在, 而求 inserted position 的話, 那結果會是 $left, 如果是求僅次於 inserted position 的上一個位置的話,
那結果會是 $right, 這題求得屬於 inserted position 的上一個位置, 因此是 return $right 時間複雜度為 O(log n)

• 題目連結
• solution example code:

class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        $left = 0;
        $right = $x;
        
        while ($left <= $right) {
            $pivot = (int) ($left + ($right - $left) / 2);
            if ($pivot*$pivot === $x) {
                return $pivot;
            } elseif ($pivot*$pivot > $x) {
                $right = $pivot - 1;
            } else {
                $left = $pivot + 1;
            }
        }
        
        return $right;
    }
}

# 367. Valid Perfect Square

這題的暴力解, 就 loop 整個 1 ~ $num 的範圍, 每一個 index 都用 $value ** 2 === $num 去判斷, 即可得到結果, 時間複雜度為 O(n), 空間複雜度為 O(1)
可使用 binary serach 概念來解, 設 $left = 1, $right = $num, 開始二分, 只要 $pivot**2 === $num 即為答案, 時間複雜度為 O(log n), 空間複雜度為 O(1)

• 題目連結
• solution example code:

class Solution {

    /**
     * @param Integer $num
     * @return Boolean
     */
    function isPerfectSquare($num) {
        $left = 1;
        $right = $num;

        while ($left <= $right) {
            $pivot = (int) ($left + ($right - $left) / 2);

            if ($pivot**2 === $num) {
                return true;
            } elseif ($num > $pivot**2) {
                $left = $pivot + 1;
            } else {
                $right = $pivot - 1;
            }
        }

        return false;
    }
}

# 704. Binary Search

這題的暴力解就是用 loop 把 $nums 全部跑過一次, 時間複雜度是 O(n)
較進階的解法, 可以使用 binary search, 時間複雜度為 O(log n)

• 題目連結
• solution example code:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $pivot = (int) ($left + ($right - $left) / 2);
            if ($nums[$pivot] === $target) {
                return $pivot;
            } elseif ($nums[$pivot] > $target) {
                $right = $pivot - 1;
            } elseif ($nums[$pivot] < $target) {
                $left = $pivot + 1;
            }
        }

        return -1;
    }
}

# string

# 雙指針

# 844. Backspace String Compare

首先看完題目後, 先搞清楚一個邏輯, 那就是今天不管兩個 string 的長度分別是多少, 如果這兩個 string 最後的結果相同這件事情成立的話, 那先決條件就是, 當 backspace 往後刪除到一個定點後 (也就是暫時沒遇到 ‘
#’ 符號了, 且往後刪的次數都有確實跑了), 那這兩個 string 當前的值必須是要一樣的。 儘管此時兩個 string 的長度可能不一, 那是因為還沒跑過的地方可能還存在 ‘#’ 符號, 但只要刪除到了一個定點, 那兩個 string
當前的值勢必要相同。 搞清楚這個邏輯後, 我們便可使用 two pointer 的概念來實作 首先, $pos 是由 string 的最後一個位置開始往前跑, 那我們設定兩個條件, 只要這兩個條件成立, 那這兩個 string
相同這件事就會成立 第一, 如上所敘, string 往前刪除到一個定點後, 兩個 string 的當前值必須相同 第二, 不管一開始的位置是什麼, 兩個相同的 string 代表其長度也相同, 所以最終兩個 string 的位置都必須停在
-1, 即全部都刪光了 如下 example code, 需注意 substr() 不比 array, 當 index 為 -1 時代表從最後往前數, 所以在往前刪除的 loop 記得要判斷 -1 就不可繼續, 因為從最後開始算,
有可能剛好最後一個值就是 ‘#’, 這樣就又成立了

• 題目連結
• solution example code:

class Solution {

    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function backspaceCompare($s, $t) {
        $sIndex = strlen($s) - 1;
        $tIndex = strlen($t) - 1;

        while ($sIndex >= 0 || $tIndex >= 0) {
            $back = 0;
            while ($sIndex >= 0 && (substr($s, $sIndex, 1) === '#' || $back !== 0)) {
                $back += substr($s, $sIndex, 1) === '#' ? 1 : -1;
                $sIndex--;
            }

            $back = 0;
            while ($tIndex >= 0 && (substr($t, $tIndex, 1) === '#' || $back !== 0)) {
                $back += substr($t, $tIndex, 1) === '#' ? 1 : -1;
                $tIndex--;
            }

            if ($sIndex >= 0 && $tIndex >= 0 && substr($s, $sIndex, 1) === substr($t, $tIndex, 1)) {
                $sIndex--;
                $tIndex--;
            } else {
                break;
            }
        }

        return $sIndex === -1 && $tIndex === -1;
    }
}

# Linked List

# 203. Remove Linked List Elements

dummy head:
主要思路是採用迭代的方式, 如果當前的 node->val 等於 $val 的話, 則把上一個 node 的 next 接到下一個 node 考量到 head 可能也是要刪掉的 node, 因此建立一個 dummy head

• 題目連結
• solution dummy head example code:

/**
 * 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
     * @param Integer $val
     * @return ListNode
     */
    function removeElements($head, $val) {
        $dummyHead = new ListNode(null, $head);
        $current = $dummyHead;
        
        while ($current->next) {
            $next = $current->next;
            if ($next->val === $val) {
                $current->next = $next->next;
                continue;
            }
            
            $current = $current->next;
        }
        
        return $dummyHead->next;
    }
}

• solution example code:

/**
 * 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
     * @param Integer $val
     * @return ListNode
     */
    function removeElements($head, $val) {
        // 如果符合刪除條件, 往下跳, 目的在於取得不符合刪除條件的 head
        while ($head->val === $val) {
            $head = $head->next;
        }

	// 如果取得的 head 是 null, 直接 return
        if (is_null($head)) {
            return $head;
        }

	// 已知該 $head 不符合刪除條件, 可作為 $pre
        $pre = $head;
	// $head->next 尚未知是否該被刪除, 進入迭代判斷
        $cur = $head->next;

        while (!is_null($cur)) {
            if ($cur->val === $val) {
                $pre->next = $cur->next;
            } else {
                $pre = $cur;
            }

            $cur = $cur->next;
        }

        return $head;
    }
}

# 2. Add Two Numbers

將 $l1, $carry 以及 $l2 的 val 相加, 若超過 10 則代表需進位, 記下 $carry, 以此模式不斷迭代持續相加, 直到 $l1 以及 $l2 皆為 null, 至此已完成所有 node 的相加, 除了最後一個
$carry, 接著判斷 $carry 是否為 0, 若否, 則代表最後一次相加是大於 0 的, 在迴圈外補上最後一個 node, 時間複雜度為 O(n), n 為 $l1 或 $l2, 視乎哪個較長

• 題目連結
• solution dummy head example code:

/**
 * 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 $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $result = new ListNode();
        $resultForIterate = $result;

        $sum = 0;
        $carry = 0;

        while (!is_null($l1) || !is_null($l2)) {
            $l1Num = is_null($l1) ? 0 : $l1->val;
            $l2Num = is_null($l2) ? 0 : $l2->val;

            $sum = $l1Num + $l2Num + $carry;

            $carry = $sum >= 10 ? 1 : 0;

            $resultForIterate->next = new ListNode($sum%10);
            $resultForIterate = $resultForIterate->next;

            $l1 = $l1->next;
            $l2 = $l2->next;
        }

        if ($carry === 1) {
            $resultForIterate->next = new ListNode($carry);
        }
        return $result->next;
    }
}

# 206. Reverse Linked List

實作的邏輯示意圖如下:

實作步驟拆解：

1. $temp = $cur->next, 這邊是將 $cur->next 指向的地址存到 $temp
2. $cur->next = $pre, 這邊改變了 $cur 的 next 指向, 變成指向 $pre
3. $pre = $cur, 這獲得 $cur 的位址, 存到 $pre
4. $cur = $temp, 獲得 $temp 的位址, 存到 $cur

• 題目連結
• solution dummy head example code:

/**
 * 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 ListNode
     */
    function reverseList($head) {
        $pre = null;
        $cur = $head;

        while ($cur) {
            $temp = $cur->next;
            $cur->next = $pre;
            $pre = $cur;
            $cur = $temp;
        }

        return $pre;
    }
}

# 24. Swap Nodes in Pairs

實作步驟拆解, 假如 input 為四個 node 的 linked list

1. 預設會有一個 dummy head, 避免一些需要特別處理的邏輯
2. $next = $cur->next, 取得下一個 node, 準備用來當第一個
3. $cur->next = $cur->next->next, 將第一個 node 的 next 指向第三個 node
4. $next->next = $cur, 將第二個 node 的 next 指向第一個 node, 承 3, 此時的第一個 node 的 next 已指向第三個 node
5. $pre->next = $next, 最後, 將 $dummyHead 的 next 指向第二個 node, 至此, 轉換步驟完成
6. $cur = $next->next->next, 將 $cur 重新定義為第三個 node
7. $pre = $next->next, 將 $pre 重新定義為第二個 node
8. 重複以上步驟直到 $cur->next === null, 代表最後不成對

• 題目連結
• solution dummy head example code:

/**
 * 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 ListNode
     */
    function swapPairs($head) {
        $dummyHead = new ListNode(null, $head);

        $pre = $dummyHead;
        $cur = $dummyHead->next;

        if (is_null($cur)) {
            return $head;
        }

        while ($cur->next) {
            $next = $cur->next;
            $cur->next = $cur->next->next;
            $next->next = $cur;
            $pre->next = $next;
            $cur = $next->next->next;
            $pre = $next->next;
        }

        return $dummyHead->next;
    }
}

# 19. Remove Nth Node From End of List

以下為解題拆解：

1. 首先使用 dummyHead 避免一些不必要的判斷
2. 概念是使用雙指針, right 指針先跑到第 $n 個 node, 這時的 left 指針指向第一個 node, 如果說此時的 right 已經是在最後一個 node, 那 left 恰好是從 end 往前數的第 $n 個 node
3. 首先先把 right 往前推, 推 $n - 1 次的話可以到第 $n 個 node, 但我們要推 $n 次, 因為我們要 left 是指向從結尾往前數的第 $n+1 個 node, 相當於目標 node 的前一個, 這樣才方便刪除
4. 因為我們有使用 dummyHead, 如果說往前跑 $n 次, 而 right 正指向最後一個 node, 此時 $pre 會等於 $dummyHead, 而 target node 會是 $dummyHead->next,
   也就是第一個 node, 如果說, 往前跑 $n 次之後, right 指向 null, 這代表這個 $n 實際上已經超出了這個 linked list 的長度, 不符合條件
5. 取得 right node 之後, 我們讓 left 指向 dummyHead, 然後開始繼續往下跑, 直到 right 指向最後一個 node
6. 此時的 left 剛好會是從結尾往前數的第 $n + 1 個 node
7. 最後再實施刪除動作, 就完成了

• 題目連結
• solution dummy head example code:

/**
 * 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
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n) {
        $dummyHead = new ListNode(null, $head);
        $right = $dummyHead;
        
        for ($i = 1; $i < $n + 1; $i++) {
            $right = $right->next;
        }
        
        if (is_null($right)) {
            return false;
        }
        
        $left = $dummyHead;
        
        while ($right->next) {
            $left = $left->next;
            $right = $right->next;
        }
        
        $pre = $left;
        $cur = $pre->next;
        $next = $cur->next;
        
        if ($next) {
            $pre->next = $next;
        } else {
            $pre->next = null;
        }
        
        return $dummyHead->next;
    }
}

# 160. Intersection of Two Linked Lists

以下為解題拆解：

1. 先計算兩個 list 的長度
2. 取得兩個長度的差值, 為 $diff
3. 將比較長的 list 的 head 跳 $diff 個 node
4. 至此, 兩個 list 的 head 距離 intersection node 已經一致
5. 開始比較兩個 head 是否相同, 直至結束, 有找到則 return head, 沒找到則 return null

• 題目連結
• solution dummy head example code:

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

class Solution {
    /**
     * @param ListNode $headA
     * @param ListNode $headB
     * @return ListNode
     */
    function getIntersectionNode($headA, $headB) {
        $lenA = 0;
        $lenB = 0;

        $tempA = $headA;
        $tempB = $headB;

        while ($tempA) {
            $lenA++;
            $tempA = $tempA->next;
        }

        while ($tempB) {
            $lenB++;
            $tempB = $tempB->next;
        }

        $diff = abs($lenA - $lenB);

        if ($lenA > $lenB) {
            $long = $headA;
            $short = $headB;
        } else {
            $long = $headB;
            $short = $headA;
        }

        while ($diff !== 0) {
            $long = $long->next;
            $diff--;
        }

        while ($long) {
            if ($long === $short) {
                return $long;
            }

            $long = $long->next;
            $short = $short->next;
        }

        return null;
    }
}

# 142. Linked List Cycle II

• 以下為雙指針解題拆解：
  (1) 示意圖：
  
  (2) 首先, 我們定義 fast 以及 slow 指針, fast 走兩格, slow 走一格, 如果最終兩個指針指向同一個點, 那代表是有 circle 存在的, 否則 fast 會先到達終點變成 null
  (3) 從上圖可以看到, 如果兩個指針相交, 那肯定是在 circle 裡相交, 否則 fast 就先變成 null 了, 沒機會相交
  (4) 如示意圖, 我們假設 x 為起始點至入口點的距離, y 為入口點至相遇點的距離, z 為相遇點至入口點的距離
  (5) slow = x+y, fast = x+n*(y+z)+y, 由於 fast 走兩格, slow 走一格, 所以當相遇的那一刻, fast 走過的距離會剛好等於 slow 的兩倍,
  所以 2*(x+y) = x+n*(y+z)+y
  (6) 我們慢慢的化簡公式, x+y = n*(y+z), x = n*(y+z) - y, 化簡到這其實就可以得到一個結果, 那就是 x 到入口點的距離, 剛好會等於從入口點開始走, 走了 n 圈之後再扣掉 y 的距離,
  換言之, 如果是從相遇點開始走的話, 那走 n 圈之後再走 z 剛好會等於 x
  (7) 從以上的結論, 我們可以得到一個邏輯, 讓一個指針從起始點開始走, 另一個指針從相遇點開始走, 每次都走一格, 直到兩者相遇, 那個點就是 circle 的入口點

• 題目連結

• solution example code:

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

class Solution {
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function detectCycle($head) {
        $fast = $head->next->next;
        $slow = $head->next;
        
        while ($fast && $slow) {
            if ($fast === $slow) {
                $index1 = $head;
                $index2 = $fast;
                
                while ($index1 !== $index2) {
                    $index1 = $index1->next;
                    $index2 = $index2->next;
                }
                
                return $index1;
            }
            
            $fast = $fast->next->next;
            $slow = $slow->next;
        }
        
        return null;
    }
}

# hash table

# 242. Valid Anagram

建立一個 hash table, 遍歷 string s, key 為字母, value 為數量, 然後在遍歷 string t, 逐一扣掉 hash table, 若最後該 hash table 為 empty, 代表兩個 string
含有一樣的字母, 時間複雜度為 O(m+n), 空間複雜度, 由於是 a-z 26 個字母, 因此為 O(1)

• 題目連結
• solution example code:

class Solution {

    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isAnagram($s, $t) {
        $dic = [];
        
        for ($i = 0; $i < strlen($s); $i++) {
            $dic[substr($s, $i, 1)]++;
        }
        
        for ($i = 0; $i < strlen($t); $i++) {
            $curChr = substr($t, $i, 1);
            $dic[$curChr]--;
            if ($dic[$curChr] === 0) {
                unset($dic[$curChr]);
            }
        }
        
        return empty($dic);
    }
}

# 1002. Find Common Characters

• 思路 因為 string 有限制在 lowercase 英文字母, 所以會介於 ASCII 97~122 共 26 個字母 概念就是, 將所有 string 轉成 hash table, 記錄下 $key = 字母, $value =
  出現次數, 然後最終取得每個字母的最小出現次數, 換言之, 如果有個字母在某個 string 中沒出現過, 那就會是 0, 如果在 string 1 出現過三次, 但在 string 2 只出現過一次, 那就只算一次
  最後將這個紀錄著最小出現次數的 hash table 再轉成相對應的 array 輸出, 便是解答 時間複雜度為 O(n), 空間複雜度為 O(1)

• 題目連結

• solution example code:

class Solution {

    /**
     * @param String[] $words
     * @return String[]
     */
    function commonChars($words) {
        $firstDic = array_fill(97, 26, 0);
        $firstWord = $words[0];
        
        for ($i = 0; $i < strlen($firstWord); $i++) {
            $asic = ord(substr($firstWord, $i, 1));
            $firstDic[$asic]++;
        }
        
        for ($i = 1; $i < count($words); $i++) {
            $otherDic = array_fill(97, 26, 0);
            $word = $words[$i];
            for ($j = 0; $j < strlen($word); $j++) {
                $asic = ord(substr($word, $j, 1));
                $otherDic[$asic]++;
            }
            
            for ($k = 97; $k <= 122; $k++) {
                $firstDic[$k] = min($firstDic[$k], $otherDic[$k]);
            }
        }
        
        $output = [];
        
        foreach($firstDic as $key => $value) {
            $chr = chr($key);
            while ($value) {
                array_push($output, $chr);
                $value--;
            }
        }
        
        return $output;
    }
}

# 349. Intersection of Two Arrays

• 思路 先將其中一個 array 轉成 hash table, 然後在 loop 另外一個 array 來判斷 each item 是否存在於 hash table, 使用 hash table 的原因是因為 hash table 找
  key 的時間複雜度為 O(1), 而 array 為 O(n)
  時間複雜度為 O(m+n), 空間複雜度為 O(m+n)

• 題目連結

• solution example code:

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        $res = [];
        $nums2Map = [];

        for ($i = 0; $i < count($nums2); $i++) {
            $nums2Map[$nums2[$i]] = true;
        }

        for ($i = 0; $i < count($nums1); $i++) {
            if (array_key_exists($nums1[$i], $nums2Map)) {
                $res[] = $nums1[$i];
            }

            unset($nums2Map[$nums1[$i]]);
        }

        return $res;
    }
}

# 454. 4Sum II

• 思路 對我來說, 這題難的地方在於數學邏輯, 求的是共有幾種 output = 0 的組合, 要先有數學概念, 假如 n1 + n2 等於 -3 有兩組, 而 n3 + n4 等於 3 的有兩組, 那就是 2*2=4, 共有四種組合
  先將 n1+n2 的所有組合都記錄下來, 存在 $dic, key 為 sum, value 為該 $sum 出現的次數, 接下來一樣去 loop n3 以及 n4, 假如 0 - (n3 + n4) 的值出現在 $dic 中,
  則代表當前 n3+n4 + n1+n2 會等於 0, 而 $dic 中記錄著 n1+n2 出現該值的組合次數, 所以當我們在 loop n3+n4 時, 如果在 $dic 中存在的話, 都必須加上 $dic 中紀錄的次數

• 題目連結

• solution example code:

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $dic = [];
        for ($i = 0; $i < count($nums1); $i++) {
            for ($j = 0; $j < count($nums2); $j++) {
                $sum = $nums1[$i] + $nums2[$j];
                $dic[$sum]++;
            }
        }
        
        $count = 0;
        
        for ($i = 0; $i < count($nums3); $i++) {
            for ($j = 0; $j < count($nums4); $j++) {
                $sum = $nums3[$i] + $nums4[$j];
                $diff = 0 - $sum;
                if (isset($dic[$diff])) {
                   $count += $dic[$diff]; 
                }
            }
        }
        
        return $count;
    }
}

# 383. Ransom Note

• 思路 這題直接使用 map 來記錄 ransom note 裡頭需要的字以及字數, 在 loop magazine, 把 magazine 裡頭出現相同的字扣掉, 如果 loop 完 magazine 之後, ransom note
  map 為空, 代表 ransom note 裡頭需要的字母以及字數 magazine 都有符合, 時間複雜度為 O(m+n), 空間複雜度為 O(m), m 為 $ransomNote 長度, n 為 $magazine 長度

• 題目連結

• solution example code:

class Solution {

    /**
     * @param String $ransomNote
     * @param String $magazine
     * @return Boolean
     */
    function canConstruct($ransomNote, $magazine) {
        $noteMap = [];
        for ($i = 0; $i < strlen($ransomNote); $i++) {
            $noteMap[substr($ransomNote, $i, 1)]++;
        }

        for ($i = 0; $i < strlen($magazine); $i++) {
            $chr = substr($magazine, $i, 1);
            if (isset($noteMap[$chr])) {
                $noteMap[$chr]--;

                if ($noteMap[$chr] === 0) {
                    unset($noteMap[$chr]);
                }
            }
        }

        return empty($noteMap);
    }
}

# 15. 3Sum

• 思路 使用雙指針法, 可參考下面的連結 每一次的 loop 都會再次執行 $left & $right 配對, 所以時間複雜度為 O(n 的平方), 空間複雜度為 O(1)

• 參考連結

• 題目連結

• solution example code:

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        sort($nums);
        $res = [];

        for ($i = 0; $i < count($nums); $i++) {
            if ($nums[$i] > 0) {
                return $res;
            }

            if ($nums[$i] === $nums[$i-1]) {
                continue;
            }

            $left = $i + 1;
            $right = count($nums) - 1;

            while ($left < $right) {
                if ($nums[$i] + $nums[$left] + $nums[$right] > 0) {
                    $right--;
                    while ($nums[$right] === $nums[$right+1]) {
                        $right--;
                    }
                } elseif ($nums[$i] + $nums[$left] + $nums[$right] < 0) {
                    $left++;
                    while ($nums[$left] === $nums[$left-1]) {
                        $left++;
                    }
                } else {
                    $res[] = [$nums[$i], $nums[$left], $nums[$right]];

                    while ($nums[$left] === $nums[$left+1]) {
                        $left++;
                    }

                    while ($nums[$right] === $nums[$right-1]) {
                        $right--;
                    }

                    $right--;
                    $left++;
                }
            }
        }

        return $res;
    }
}

# 18. 4Sum

• 思路 使用雙指針法, 可參考下面的連結 這類型的題目, 有一個很重要的點, 看似 loop 很多層, 但基本原則就是每一個最小的 loop 都是 n 個固定數 + 兩個指針根據總合來判斷移動 right or left。 由於最小
  loop 為兩個指針來移動, 總共有四個數, 所以會是兩個固定數 + 兩個指針 由於已經完成排序, 所以可以確定, 只要我們將兩個固定數其中一個往右移, 那該 loop 所得到的結果必然不會跟之前得到的結果重複,
  因為往右移代表原先的數已經不會再出現了(因為已經排序過了, 數只會越來越大, 過了就是過了)
  上面提到最小 loop 的行為是兩個固定數 + 雙指針移動, 而要求得所有的可能性, 我們需要雙層 loop 來代表兩個固定數

• 參考連結

• 題目連結

• solution example code:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        $res = [];
        sort($nums);

        for ($i = 0; $i < count($nums); $i++) {
            if ($nums[$i] > 0 && $nums[$i]*4 > $target) {
                return $res;
            }

            if ($nums[$i] === $nums[$i-1]) {
                continue;
            }

            for ($j = $i+1; $j < count($nums); $j++) {
                if ($j > $i+1 && $nums[$j] === $nums[$j-1]) {
                    continue;
                }

                $left = $j+1;
                $right = count($nums) - 1;

                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    if ($sum > $target) {
                        $right--;
                        while ($nums[$right] === $nums[$right+1]) $right--;
                    } elseif ($sum < $target) {
                        $left++;
                        while ($nums[$left] === $nums[$left-1]) $left++;
                    } else {
                        $res[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
                        while ($nums[$left] === $nums[$left+1]) $left++;
                        while ($nums[$right] === $nums[$right-1]) $right--;
                        $left++;
                        $right--;
                    }
                 }
            }
        }

        return $res;
    }
}

# String

# 344. Reverse String

• 思路 思路很簡單, 一開始愣是沒想明白, 真是菜雞 就是使用雙指針, 將第一個與最後一個交換, 然後雙指針各往中間前進一格 時間複雜度為 O(n), 空間複雜度為 O(1)

• 題目連結

• solution example code:

class Solution {

    /**
     * @param String[] $s
     * @return NULL
     */
    function reverseString(&$s) {
        $left = 0;
        $right = count($s) - 1;

        while ($left < $right) {
            $leftV = $s[$left];
            $rightV = $s[$right];
            $s[$left] = $rightV;
            $s[$right] = $leftV;

            $left++;
            $right--;
        }

        return $s;
    }
}

# 541. Reverse String II

• 思路 題目說, 如果 剩下的長度 < 2k && 剩下的長度 >= k 個字, 那就逆轉前 k 個字, 如果 剩下的長度 < k, 那就逆轉剩下的所有字, 第一個條件很明顯是廢話, 這句話真的有點繞,
  所以簡單來說, 剩下的長度 > k, 則逆轉 k 個字, 否則則逆轉剩下的所有字
  我們讓 $i += 2k, 當作錨點, 每一次的 left 以及 right 都從這個 anchor 來取 left 會等於 anchor, 而 right 會等於 anchor + k - 1, 如果 anchor 超過總長度則
  break 綜合以上所有邏輯, 就可以求得解答, 時間複雜度為 O(n), 空間複雜度為 O(1)

• 題目連結

• solution example code:

class Solution {

    /**
     * @param String $s
     * @param Integer $k
     * @return String
     */
    function reverseStr($s, $k) {
        $len = strlen($s);
        
        for ($i = 0; $i < $len; $i += 2*$k) {
            $left = $i;
            $right = $left + $k - 1;
            $right = $right < $len - 1 ? $right : $len - 1;
            
            while ($left < $right) {
                $tempL = $s[$left];
                $s[$left] = $s[$right];
                $s[$right] = $tempL;
                $left++;
                $right--;
            }
        }
        
        return $s;
    }
}

# 202. Happy Number

• 思路 這題主要應該是比較偏數學問題, 首先必須要有意識到, 這樣的 loop 下, 已經出現過的 sum 是會重複出現的 明白這一點之後, 就可以使用 map 來處理, 將計算過的 sum 存起來, 如果之後重複了就直接 return
  false, 直到取得 sum 為 1 的數, return true

• 題目連結
• solution example code:

class Solution {

    /**
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        $dic = [];
        while ($n !== 1 && $n > 0) {
            if (isset($dic[$n])) {
                return false;
            }
            
            $dic[$n] = true;
            
            $res = 0;
            
            while ($n > 0) {
                $temp = $n % 10;
                $res += $temp*$temp;
                $n = (int) ($n/10);
            }
            
            $n = $res;
        }
        
        return true;
     }
}

# Stack

# 20. Valid Parentheses

• 思路: 根據此題的規則, ( 要對應 ), { 要對應 }, 而 [ 要對應 ], 而且順序也必須符合規則, ()[]{} 為 true, ([{}]) 為 true, (] 為
  false, ({}[)) 為 false, 所以此題可以利用 Stack 的特性來解題。 stack 特性為先進後出, 所以我們可以遍歷 input, 當為 ([{ 時, 我們依序的在 stack 中放入 )]}, 而當
  input 為 )]} 時, 我們 pop stack, 並比較 input 與 stack pop 的值是否相等, 若不相等就表示對不上了。 照這個規則, 如果 input 是個合乎規格的 string, 那遍歷完整個 input
  時, stack 應為 empty, 因為有幾個 ([{ 就會 push 幾次, 而有幾個 )]} 就會 pop 幾次, 而 stack 的特性保證了順序正確
• 複雜度： 時間複雜度是 O(n), 空間複雜度為 O(n)
• 題目連結
• solution example code:

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        $stack = [];
        $parentheses = [
            '(' => ')',
            '[' => ']',
            '{' => '}'
        ];
        
        for ($i = 0; $i < strlen($s); $i++) {
            $parenthesis = $s[$i];
            if (in_array($parenthesis, ['(', '[', '{'])) {
                array_push($stack, $parentheses[$parenthesis]);
                continue;
            }
            
            if ($parenthesis !== array_pop($stack)) {
                return false;
            }
        }
        
        return empty($stack);
    }
}

# 1047. Remove All Adjacent Duplicates In String

• 思路: 題目主要是要刪除相鄰重複的數, 所以可以簡單比較相鄰的兩個數, 若相同則 $left 往回退, 若不相同則直接加上, 若 $left === -1 代表目前 stack 內其實已經沒有任何數了, 此時無條件加上
• 複雜度： 時間複雜度 O(n), 空間複雜度 O(1)
• 題目連結
• solution example code:

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function removeDuplicates($s) {
        $left = -1;
        for ($right = 0; $right < strlen($s); $right++) {
            if ($left === -1 || $s[$left] !== $s[$right]) {
                $s[++$left] = $s[$right];
                continue;
            }
            
            if ($s[$left] === $s[$right]) {
                $left--;
                continue;
            }
        }
        
        return substr($s, 0, $left+1);
    }
}

# 347. Top K Frequent Elements

• 思路: 這題是使用 priority queue 來解, 順便理解了一下 heap 資料結構。 這題用 array_flip 來解我覺得也是可以的, 但時間複雜度會增加為 O(n log n)
• 複雜度： 時間複雜度 O(n), 空間複雜度 O(n)
• 題目連結
• solution example code:

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function topKFrequent($nums, $k) {
        $queue = new SplPriorityQueue();
        
        $map = array_count_values($nums);

        
        foreach($map as $key => $value) {
            $queue->insert($key, $value);
        }
        
        $res = [];
        
        while ($k > 0 && $queue->count >= 0) {
            $res[] = $queue->extract();
            $k--;
        }
        
        return $res;
    }
}

# 150. Evaluate Reverse Polish Notation

• 思路: 這題我覺得難的主要是 ERPN 的概念, 先把這個概念搞懂了, 邏輯其實不難。 ERPN 可以 Google 先了解一下他的定義。 簡單來說, 我們建立一個 stack, 依序的 loop $tokens, 只要值不是 +, -, *, /, 我們就直接塞進 stack, 如果是的話, 那代表要做計算, 就依序 pop 兩個數出來當作 operand1 & operand2, 然後做完計算後, 再將結果 push 進 stack。 照這個流程, 只要 $tokens array 是 valid, 那 stack 中最後一個數就是 answer
• 複雜度： 時間複雜度 O(n), 空間複雜度 O(n)
• 題目連結
• solution example code:

  class Solution {
  
      /**
       * @param String[] $tokens
       * @return Integer
       */
      function evalRPN($tokens) {
          $stack = [];
          for ($i = 0; $i < count($tokens); $i++) {
              if (!in_array($tokens[$i], ['+', '-', '*', '/'])) {
                  $stack[] = $tokens[$i];
                  continue;
              }
              
              $operand2 = array_pop($stack);
              $operand1 = array_pop($stack);
              $result = $this->calculate($tokens[$i], $operand1, $operand2);
              
              $stack[] = $result;
          }
          
          return array_pop($stack);
      }
      
      function calculate($operator, $operand1, $operand2) {
          switch ($operator) {
              case '+':
                  return intval($operand1 + $operand2);
              case '-':
                  return intval($operand1 - $operand2);
              case '*':
                  return intval($operand1 * $operand2);
              case '/':
                  return intval($operand1 / $operand2);
          }
      }
  }

# 239. Sliding Window Maximum

• 思路: 這題的目標在於取得每次移動的 sliding window 中最大的數, 邏輯思路在於維護一個 queue win, 兩個 method enqueue, dequeue,
  • enqueue 的功能會把每一次要新放入 win 當中的數, 依序地跟 win 當中的數做比較, 若新的數比較大, 則 pop 當前 win 中的數, 最多可以 pop 完所有 win 當中的數, 最後再把新的數放入 win 中, 這樣可以確保 win 的第一個數一定是最大的
  • dequeue 的功能, 會比較 win 當中的第一個數是否跟要移除的數相同, 若否, 則代表該數已經在之前的 enqueue 操作中被移除了, 故不做任何動作。 若是, 則將該數從 win 當中移除
  • 每次 enqueue 以及 dequeue 時, 都會更新 winLeft, winRight, 因為 PHP array 直接指定 index 的時間複雜度為 O(1)
  • 在每一次的 loop, 都將 win 當中的第一個數複製到 res 當中, res 即解答
• 複雜度: 時間複雜度為 O(n), 空間複雜度為 O(n)
• 題目連結
• solution example code:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    protected $winLeft = 0;
    protected $winRight = 0;
    protected $win = [];
    
    function maxSlidingWindow($nums, $k) {
        $numsRight = 0;
        $numsLeft = 0;
        $numsLen = count($nums);
        $res = [];
        while ($numsRight < $k) {
            $this->enqueue($nums[$numsRight]);
            $numsRight++;
        }
        
        $res[] = $this->win[$this->winLeft];
        
        
        while ($numsRight < $numsLen) {
            $this->enqueue($nums[$numsRight]);
            $this->dequeue($nums[$numsLeft]);
            $res[] = $this->win[$this->winLeft];
            $numsRight++;
            $numsLeft++;
        }
        
        return $res;
    }
    
    function enqueue($value) {
        if (empty($this->win)) {
            $this->win[] = $value;
            $this->winRight++;
        }
        
        while ($value > $this->win[$this->winRight] && $this->winRight >= $this->winLeft) {
            array_pop($this->win);
            $this->winRight--;
        }
        
        $this->win[] = $value;
        $this->winRight++;
    }
    
    function dequeue($value) {
        if ($this->win[$this->winLeft] === $value) {
            $this->winLeft++;
        }
    }
}

# Binary Tree

# 144. Binary Tree Preorder Traversal

• 思路: preorder 的順序是 中, 左, 右, 所以照著這個順序來遞迴就行了

• 複雜度： 時間複雜度 O(n), 空間複雜度 O(n)

• 題目連結

• solution example code (遞迴)

  <?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 TreeNode $root
       * @return Integer[]
       */
      function preorderTraversal($root) {
          $res = [];
          $this->traverse($root, $res);
          
          return $res;
      }
      
      function traverse($node, &$res) {
          if (is_null($node)) {
              return;
          }
          
          $res[] = $node->val;
          $this->traverse($node->left, $res);
          $this->traverse($node->right, $res);
      }
  }

• solution example code (stack)

  <?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 TreeNode $root
       * @return Integer[]
       */
      function preorderTraversal($root) {
          $stack = [];
          $res = [];
          
          array_push($stack, $root);
          
          while (count($stack) !== 0) {
              $node = array_pop($stack);
              $res[] = $node->val;
              
              if (!is_null($node->right)) $stack[] = $node->right;
              if (!is_null($node->left)) $stack[] = $node->left;
          }
          
          return $res;
      }
  }

# 145. Binary Tree Postorder Traversal

• 思路: postorder 的順序是 左, 右, 中, 所以照著這個順序來遞迴就行了
• 複雜度： 時間複雜度 O(n), 空間複雜度 O(n)
• 題目連結
• solution example code:

  <?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 TreeNode $root
       * @return Integer[]
       */
      function postorderTraversal($root) {
          $res = [];
          $this->traverse($root, $res);
          return $res;
      }
      
      function traverse($node, &$res) {
          if (is_null($node)) {
              return;
          }
          
          $this->traverse($node->left, $res);        
          $this->traverse($node->right, $res);
  
          $res[] = $node->val;
      }
  }

# 94. Binary Tree Inorder Traversal

• 思路: inorder 的順序是 左, 中, 右, 所以照著這個順序來遞迴就行了
• 複雜度： 時間複雜度 O(n), 空間複雜度 O(n)
• 題目連結
• solution example code:

  /**
   * 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 TreeNode $root
       * @return Integer[]
       */
      function inorderTraversal($root) {
          $res = [];
          $this->traverse($root, $res);
          return $res;
      }
      
      function traverse($node, &$res) {
          if (is_null($node)) {
              return;
          }
          
          $this->traverse($node->left, $res);
          $res[] = $node->val;
          $this->traverse($node->right, $res);
      }
  }