# LeetCode 刷起來

###### tags: `LeetCode`

## Two Sum (難度：Easy)

https://leetcode.com/problems/two-sum/

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $tmp = [];
        foreach ($nums as $inedx => $num) {
            if (array_key_exists($target - $num, $tmp)) {
                return [$tmp[$target - $num], $inedx];
            }

            $tmp[$num] = $inedx;
        }

        return null;
    }
}

## Two Sum II - Input Array Is Sorted(難度：Medium)
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
### GO

func twoSum(numbers []int, target int) []int {
    left := 0;
    right := len(numbers) - 1
    for right > left {
        sum := numbers[left] + numbers[right]
        if sum == target {
            return []int{left+1, right+1}
        } else if target > sum  {
           left++
        } else {
            right--
        }
    }

    return []int{}
}

### PHP

class Solution {

    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $left = 0;
        $right = count($numbers) - 1;
        while ($right > $left) {
            $sum = $numbers[$right] + $numbers[$left];
            if ($sum === $target) {
                return [$left + 1, $right + 1];
            } else if ($sum > $target) {
                $right--;
            } else {
                $left++;
            }
        }

        return [];
    }
}

## Merge Two Sorted Lists (難度：Easy)

https://leetcode.com/problems/merge-two-sorted-lists/

/**
 * 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 $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        if (empty($list1)) {
            return $list2;
        }

        if (empty($list2)) {
            return $list1;
        }

        $mergeList = new ListNode();

        if ($list1->val >= $list2->val){
            $mergeList->val = $list2->val;
            $mergeList->next = $this->mergeTwoLists($list1, $list2->next);
        } else {
            $mergeList->val = $list1->val;
            $mergeList->next = $this->mergeTwoLists($list1->next, $list2);
        }

        return $mergeList;
    }
}

## Binary Search (難度：Easy)

https://leetcode.com/problems/binary-search/

class Solution {

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

        $index = -1;
        while ($min <= $max) {
            $mid = floor(($max + $min) / 2);

            if ($nums[$mid] === $target) {
                $index = $mid;
                break; 
            }

            if ($nums[$mid] > $target) {
                $max = $mid - 1;
            } else if ($nums[$mid] < $target) {
                $min = $mid + 1;
            }
        }

        return $index;
    }
}

## Remove Duplicates from Sorted Array(難度：Easy)
https://leetcode.com/problems/remove-duplicates-from-sorted-array/

### GO

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    k := 1
    for i := 1; i < len(nums); i++ {
        if (nums[i] != nums[i-1]) {
            nums[k] = nums[i]
            k++
        }
    }

    return k
}

### PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        $nums = array_unique($nums);
        return count($nums);
    }
}

## Remove Duplicates from Sorted Array II(難度：Medium)
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii

### GO

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    k := 1
    duplicates := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            nums[k] = nums[i]
            duplicates = 0
            k++
        } else {
            duplicates++
            if duplicates < 2 {
                nums[k] = nums[i]
                k++
            }
        }
    }

    return k
}

### PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        if (count($nums) === 0) {
            return 0;
        }

        $k = 1;
        $duplicates = 0;
        for ($i = 1; $i < count($nums); $i++) {
            if ($nums[$i] !== $nums[$i -1]) {
                $nums[$k] = $nums[$i];
                $duplicates = 0;
                $k++;
            } else {
                $duplicates++;
                if ($duplicates < 2) {
                    $nums[$k] = $nums[$i];
                    $k++;
                }
            }
        }

        return $k;
    }
}

## Minimum Size Subarray Sum(難度：Medium)
https://leetcode.com/problems/minimum-size-subarray-sum/

- 經典 Sliding Window，右邊界(`right`)依序往右走並累加 `sum`，當 `sum` 大於 `target` 時，紀錄 window size。
- 接著左邊界(`left`)開始移動，window size 縮小，直到 `sum` 小於 `target`，找到前段最小 window size。
- 然後 window 開始向右開始移動(左右邊界開始右移)，期間如果有 `sum` 小於 `target`，重複上一步驟縮小 window size，縮小後 window 再開始右移，直到陣列最後。

### GO

func minSubArrayLen(target int, nums []int) int {
    left, sum := 0, 0
    minSize := len(nums) + 1
    for right := 0; right < len(nums); right++ {
        sum += nums[right]
        for sum >= target {
            if minSize > right - left + 1 {
                minSize = right - left + 1
            }
            sum -= nums[left]
            left++
        }
    }

    if minSize > len(nums) {
        return 0
    }

    return minSize
}

### PHP

class Solution {

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

        foreach ($nums as $right => $value) {
            $sum += $value;
            while ($sum >= $target) {
                if ($minSize > $right - $left + 1) {
                    $minSize = $right - $left + 1;
                }
                $sum -= $nums[$left];
                $left++;
            }
        }
        
        if ($minSize > count($nums)) {
            return 0;
        }

        return $minSize;
    }
}

## Minimum Window Substring(難度：Hard)
https://leetcode.com/problems/minimum-window-substring/

- 字串 `s` 中，先固定 `left`，`right` 移動至包含所有字串 `t` 的字母，並記下當時的 `left` 跟 window size。
- 接著 `left` 開始移動，直到遇見字串 `t` 中的任一字母，並記下當時的 `left` 跟 window size。
- `left` 右移一格後，這時代表代表包含所有字串 `t` 的字母少一個，因此 `right` 一格一格往右移，直到遇見上一步的字母。
- `right` 遇見字母後，重複步驟二，換 `left` 移動，直到 `right` 移到字串 `s` 最後一個字母
- 範例 s = `"ADOBANCKSS"`, t = `"ABC"` :

// 第 1 次: A => right 開始移動
// 第 2 次: AD
// 第 3 次: ADO
// 第 4 次: ADOB
// 第 5 次: ADOBA
// 第 6 次: ADOBAN
// 第 7 次: ADOBANC => 符合條件，已包含所有字串 `t` 的字母
// 第 8 次: DOBANC => 換 left 開始移動
// 第 9 次: OBANC
// 第 10 次: BANC => 遇到字串 `t` 包含的字母(B)，下一步要保持 window size，left & right 向右移一格
// 第 11 次: ANCK => left 向右移少了字母 B，left 固定，right 要向右找到新的字母 B
// 第 12 次: ANCKS 
// 第 13 次: ANCKSS => right 走到最後了，未遇到新的字母 B，min window 是 BANC

func minWindow(s string, t string) string {
	if len(t) > len(s) {
		return ""
	}

	letters := make(map[string]int)
	for i := 0; i < len(t); i++ {
		letters[string(t[i])]++
	}

	minWindowLeft := 0
	minWindowSize := len(s) + 1
	left, right := 0, 0

	counter := len(t)
	for right < len(s) {
		if letters[string(s[right])] > 0 {
			counter--
		}
		letters[string(s[right])]--
		right++

		for counter == 0 {
			if minWindowSize > right-left {
				minWindowLeft = left
				minWindowSize = right - left
			}

			letters[string(s[left])]++
			if letters[string(s[left])] == 1 {
				counter++
			}

			left++
		}
	}

	if minWindowSize > len(s) {
	    return ""
	}

	return s[minWindowLeft:minWindowLeft+minWindowSize]
}

## Maximum Depth of Binary Tree(難度：Easy)
https://leetcode.com/problems/maximum-depth-of-binary-tree/
左右 node 一層層統計下去，各層累加後取最大的 depth

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if (root == nil) {
        return 0
    }

    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

## Construct Binary Tree from Preorder and Inorder Traversal(難度：Medium)
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

- `pre-order` 是從 `root` 開始，然後總是從 left node 開始遍歷。如果依 root 分左右元樹，遍歷結果有個規律：`root, {左元樹所有 node...}, {左元樹所有 node...}`，如範例 `3,9,20,15,7`，3 是 `root`，接著 9 屬於左元樹 node，再來的 20、15、7 屬於右元樹 node。
- `in-order` 是從 `root` 切分，左元樹最底層且最左邊的 node 開始，然後依 left -> parent -> right 順序遍歷，遍歷結果有個規律：`{左元樹所有 node...}, root, {左元樹所有 node...}`，如範例 `9,3,15,20,7`，9 屬於左元樹 node，接著 3 是 `root`，再來 20、15、7 屬於右元樹 node。
- 綜上，`preorder` 的第一個數值就是 `root`，找到 `root` 值在 `inorder` 陣列的 index 位置，idex 前面的數值都在左元樹，後面的數值都在右元樹。利用這規律，用遞迴方式，從最上層、第二層、第三層...慢慢建構出 binary tree。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}

	root := preorder[0]
	i := slices.Index(inorder, root)

	leftPreorder := preorder[1:i+1]
	leftInorder := inorder[:i]

	rightPreorder := preorder[i+1:]
	rightInorder := inorder[i+1:]

	return &TreeNode{
	    Val: preorder[0],
	    Left: buildTree(leftPreorder, leftInorder),
	    Right: buildTree(rightPreorder, rightInorder),
	}
}

## Binary Tree Right Side View(難度：Medium)
https://leetcode.com/problems/binary-tree-right-side-view/

- 注意一些例子 root:`[1,2,3,null,5,null,null]` => ouput: `[1,3,5]` & root:`[1,2,3,6,null,null,null]` => ouput: `[1,3,6]`，右元樹最底層沒有數值時，要補上左元樹該層最右邊的值，binary tree 深度會等於回傳陣列的長度，所以先查右元樹後要再查左元樹。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    result := []int{}
    appendNodeVal(root, 1, &result)
    return result
}

func appendNodeVal(node *TreeNode, depth int, result *[]int) {
    if node == nil {
        return
    }

    if depth > len(*result) {
        *result = append(*result, node.Val)
    }

    appendNodeVal(node.Right, depth+1, result)
    appendNodeVal(node.Left, depth+1, result)
}

## Validate Binary Search Tree(難度：Medium)
https://leetcode.com/problems/validate-binary-search-tree/

node `Val` 必須在最大最小值範圍裡，檢查左子層限定 max，檢查右子層限定 min，最上層初始 mix & max 設定介於題目限定的 `-2^31 ~ 2^31-1`

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return isValid(root, math.MinInt, math.MaxInt)
}

func isValid(node *TreeNode, min, max int) bool {
    if node == nil {
        return true
    }

    if node.Val <= min || node.Val >= max {
        return false
    }

    return isValid(node.Left, min, node.Val) && isValid(node.Right, node.Val, max) 
}

## Find Peak Element(難度：Medium)
https://leetcode.com/problems/find-peak-element/

經典 Binary Search，target 改成 `mid` 對應的值即可

func findPeakElement(nums []int) int {
    left := 0
    right := len(nums) - 1
    for right > left {
        mid := (left + right) / 2
        if nums[mid] > nums[mid+1] {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

## Find First and Last Position of Element in Sorted Array(難度：Medium)
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

兩次 Binary Search，先找出 `start`(`left`)，再找出 `end`(`right`)

func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }

    start := searchStart(nums, target)
    if start == -1 {
       return []int{-1, -1} 
    }

    end := searchEnd(nums, target, start)
    return []int{start, end}
}

func searchStart(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    for right > left {
        mid :=  (left + right) / 2

        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }

    if (nums[left] == target) {
        return left
    }

    return -1
}

func searchEnd(nums []int, target int, left int) int {
    right := len(nums) - 1
    for right > left {
        mid :=  (left + right) / 2

        if nums[mid] > target {
            right = mid
        } else {
            left = mid + 1
        }
    }

    if (nums[right] == target) {
        return right
    }

    if (nums[right - 1] == target) {
        return right - 1
    }

    return -1
}