# LeetCode 刷起來
###### tags: `LeetCode`
## Two Sum (難度:Easy)
https://leetcode.com/problems/two-sum/
```php
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
```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
```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/
```php
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $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/
```php
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
```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
```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
```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
```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
```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
```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
```
```go
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
```go
/**
* 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。
```go
/**
* 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 深度會等於回傳陣列的長度,所以先查右元樹後要再查左元樹。
```go
/**
* 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`
```GO
/**
* 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` 對應的值即可
```go
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`)
```go
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
}
```