---
# System prepended metadata

title: Leetcode with Golang

---

# Leetcode with Golang
## 20230211 (Day1)
### :heavy_check_mark: 1. Two Sum 二和 [題目](https://leetcode.com/problems/two-sum/)
### a. 暴力解

1. 自己寫的第一版（時間O(n^2)，空間O(n)）
```
func twoSum(nums []int, target int) []int {
    var sum []int
    for i := 0; i < len(nums)-1 ; i++ {
        for j := 1; j < len(nums); j++ {
            if target != nums[i] + nums[j] || i == j {
                continue
            }
            if len(append(sum, i ,j)) == 2 {
                sum = append(sum, i ,j)
            }
        } 
    }
    return sum
}
```
2. 參考別人的解答後修改的版本（時間O(n^2)，空間O(n)）
[參考連結](https://ithelp.ithome.com.tw/articles/10233459)
```
func twoSum(nums []int, target int) []int {
    var sum []int
    for i := 0; i < len(nums)-1 ; i++ {
        for j := i+1 ; j < len(nums); j++ {
            if target != nums[i] + nums[j] {
                continue
            }
        sum = append(sum, i, j)
        }
    }
    return sum
}
```
3. 降低空間複雜度（時間O(n^2)，空間O(1)）
```
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums) - 1; i++ {
        for j := i + 1; j < len(nums); j++ {
            if target == nums[i] + nums[j] {
                return []int {i, j}
            } else {
                continue
            }
        } 
    }
    return nil
}
```


### b. Hash Map
4. 參考別人解答後自己寫的（時間O(n)，空間O(n)）
[參考連結1](https://studygolang.com/articles/27605)
[參考連結2](https://fukubaka0825.medium.com/go-leetcode-1-two-sum-cb16490140cd)
```
func twoSum(nums []int, target int) []int {
    my_map := make(map[int]int) // make(map[key]value)
    for i, v := range nums {
        complement := target - v
        if idx, exist:= my_map[complement]; exist {
            return []int{idx, i}
        }
        my_map[v] = i
    }
    return nil
}
```

### 心得
花了比預期多很多的時間在熟悉Golang語法（slice, array的差別、map的操作）上，尤其是if idx, exist:= my_map[complement]; exist {)這句，想出大概的解法倒是很快。

第一直覺就是用暴力解，但寫暴力解時要小心loop的範圍，以及需要注意一開始沒想到的edge case（一開始的寫法不小心默認了兩個解是相連的，後來又忘記一個數只能用一次，重複了）。

寫完暴力解，想了一下想到或許可用指針解，但覺得太麻煩就直接看解答（map）。覺得map的解法很直覺，但因為對map不熟悉所以花了很多時間研究實際作法及語法。




### Map參考資料
[參考資料1](https://pjchender.dev/golang/maps/)
[參考資料2](https://www.digitalocean.com/community/tutorials/understanding-maps-in-go)
[參考資料3](https://ithelp.ithome.com.tw/articles/10156167)
[參考資料4](https://hackmd.io/@action/rk8R2cuAU#map-映射)

## 20230212 (Day2)
### 20. Valid Parentheses 可靠的括號 [題目](https://leetcode.com/problems/valid-parentheses/)

### a. Stack
1. 參考別人的答案後寫出來的
[參考連結](https://blog.csdn.net/bahuan1987/article/details/102344639?spm=1001.2101.3001.6650.8&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-8-102344639-blog-126444509.pc_relevant_3mothn_strategy_recovery&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-8-102344639-blog-126444509.pc_relevant_3mothn_strategy_recovery&utm_relevant_index=11)   
   
   小技巧：建立一個以右括號為index的map
```
func isValid(s string) bool {
    if len(s) == 0 {
        return true
    }

    my_map := map[string]string {")":"(", "]":"[", "}":"{"}
    var stack []string

    for i := 0; i < len(s); i++ {
        if len(stack) == 0 {
            stack = append(stack, string(s[i]))
        } else {
            if stack[len(stack)-1] == my_map[string(s[i])] {
                stack = stack[:len(stack)-1]
            } else {
                stack = append(stack, string(s[i]))
            }
        }
    }

    if len(stack) == 0 {
        return true
    } else {
        return false
    }
} 

```

## 20230214 (Day3)
### 21. Merge Two Sorted Lists 混合兩鏈結 [題目](https://leetcode.com/problems/merge-two-sorted-lists/)
### a. Iterative
1. 參考
[參考連結](https://helloacm.com/merge-two-sorted-linked-list-using-golang/)
```
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := new(ListNode)
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }
        if list1 != nil { // list2 == nil
            tail.Next = list1
        } else if list2 != nil { // list1 == nil
            tail.Next = list2
        } else { // list1 == nil && list2 == nil
            return nil
        }
    
    return dummy.Next
}
```
### b. Recursive
1. 參考
[參考連結（同上）](https://helloacm.com/merge-two-sorted-linked-list-using-golang/)
```
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    } else if list2 == nil{
            return list1
    } else {
        if list1.Val < list2.Val {
            list1.Next = mergeTwoLists(list1.Next, list2)
            return list1
        } else {
            list2.Next = mergeTwoLists(list1, list2.Next)
            return list2
        }
    }
}
```

### 心得
寫iterative時，誤把if當成for來用，沒遍歷所有節點，所以compile沒問題但Wrong Answer。後來又誤把 } 放錯地方，比對成功提交的扣才知道問題在哪裡。

寫recursion時，一直不太確定遞迴的邏輯該怎麼寫（知道理論上是先比較第一個數的大小，抽出小的後，被抽出一個數的數組再使用func進行比較），覺得暫時只能先背起來。

這題跟可靠的括號一樣，一看到題目就大概知道可以用iterative解（因為兩個鏈結都是排序過的，所以直接比較第一個節點的值就好了），奈何對Golang語法不熟、很多細節想不到（可能跟寫扣經驗少有關吧，像是dummy head的操作也是看了一段時間才真的百分之百會寫），還是得參考別人的答案，以致於一題都會花費非常多時間（沒認真測，感覺至少要個兩小時吧），只能說服自己這是在初期所以困難多，但累積久了一定會變快變順的。

今天看了網路上大神Guan Hui-Feng（YT: [Hua Hua](https://www.youtube.com/watch?v=qckKEYP9bBA)）與[Neetcode](https://www.youtube.com/watch?v=XIdigk956u0)頻道的講解影片，發現大神們通常不只神還是很願意分享的神，覺得軟體界中這種分享的精神非常可貴，尤其對新手而言真的是值得額手稱慶了（在中文打滾四年以及念了一小段時間的物理，就知道其他領域的自學資源真的少了不知道多少。軟體業像是站在的山腳下看著頂端的大神，雖然知道頂端很遠、爬上去很辛苦，但至少手上有大神發送的地圖、半路上也有大神留下的路標。我在其他領域站在山腳下看著大神，只知道對方在山頂我在山腳，中間還有層層雲霧繚繞，連路都看不清...）。

### 121. Best Time to Buy and Sell Stock 股票最好在這些時間買賣 [題目](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

### a. 暴力解
1. 自己寫的，算法應該是對的，但在append profit的地方報out of memory了QQ （時間O(n^2)）
```
import (
    "fmt"
    "sort"
)

func maxProfit(prices []int) int {
    var profit []int
    for i := 0; i < len(prices)-1; i++ { // O(n^2)
        for j:= i+1; j < len(prices); j++ {
            if prices[j] - prices[i] > 0 {
                profit = append(profit, prices[j] - prices[i])
            } 
        } 
    }
    
    if profit == nil { 
        return 0 
    } else { // sort profit and return the biggest number // O(logn)
        sort.Ints(profit)
        ans := profit[len(profit) - 1]
        // fmt.Println(profit)
        return ans
    }
}
```
### b. DP
1. 參考 （時間O(n)）
[參考影片連結](https://www.youtube.com/watch?v=8pVhUpF1INw)
[參考連結](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solutions/385299/Go-golang-fast-and-slow-solutions/)
概念：track前k天的最小價格
```
func maxProfit(prices []int) int {
    // Lowest prices up to i-th day: L[i]
    // Max profit up to i-th day: P[i]
    // P[i] = max(P[i-1], prices[i] - L[i-1])
    // max_profit = P[n-1]
    
    Low_P := prices[0]
    Max_P := 0
    for i := range prices {
        if prices[i] < Low_P {
            Low_P = prices[i]
        } 
        if Max_P < prices[i] - Low_P {
            Max_P = prices[i] - Low_P
        }
    }
    return Max_P
}
```
2. 參考
[參考影片連結（同上）](https://www.youtube.com/watch?v=8pVhUpF1INw)
概念：操作price[i]-price[i-1]可得出持有(i-1)th到ith天的收益，最大收益就是收益數組中加起來最大的和，因此問題就轉化成53.Maximum Subarray。


### 心得

寫DP時，心裡想的一直是紀錄最小價格與最大收益就好，但不知道為什麼就寫了個數組（浪費空間而且還寫不出來，卡在max()的用法上。），查了其他人用Golang的解法後，頓悟其實紀錄一個數字就好，也不用max()了，直接用if比較就好了，更改後立刻過了，非常簡潔的想法與解法。

後來發現花花一開始講解的確是用數組，雖然如此，他說了數組的使用其實是不必要的，可以把空間降維至O(1)，但我到第二次看影片時才看懂。其實數組＆記一個數字都是正確的，只是差在空間複雜度。

## 20230215 (Day4)
### 125. Valid Palindrome 可靠的回文（不可靠啦！討厭） [題目](https://leetcode.com/problems/valid-palindrome/)
### a. 暴力解

1. 自己寫的，可complie但WA（花太多時間了先跳過，之後再找出問題在哪） 
[參考連結](https://leetcode.com/problems/valid-palindrome/solutions/421055/go-golang-slow-and-fast-solutions/)

```
Example
Input: s = "race a car"
Output: false // my output: true
Explanation: "raceacar" is not a palindrome.

func isPalindrome(s string) bool {
    ans := true
	for _, text := range s {
        var t string
		if text >= 65 && text <= 90 { // A-Z
			text = text + 32 // transform into lowercase
            t += string(text)
		}
        if text >= 97 && text <= 122 { // a-z
            t += string(text)
        }
		if text <= 48 && text <= 57 { // numbers
			t += string(text)
		}        
		if text < 65 || text > 122 { // non-alphanumeric cha
			text = 32
		}
		if text < 90 && text < 97 { // non-alphanumeric cha
			text = 32
		} 

		for i := 0; i < len(t); i++ {
            if t[i] != t[len(t)-1-i] {
                ans = false 
			} 
		}
	}
    return ans
}
```
2. 照著解答寫還是WA，瘋了
```
import (
    "fmt"
    "strings"
)

func isPalindrome(s string) bool {
    s = strings.ToLower(s)
    str := " "
    for _, c := range s { 
        if ('a' <= c && c <= 'z') || ('0' <= c && c<= '9') {
            str += string(c)
        }
    }

    if len(str) == 0 {
        return true
    }

    i,j := 0, len(str)-1
    for i <= j {
        if str[i] != str[j] {
            return false
        }
        i++
        j--
    }
    return true
}
```
3. 解答
```
func isPalindrome(s string) bool { 
    str := ""
    s = strings.ToLower(s) 
    for _, value := range s {
        if (value >= '0' && value <= '9') || (value >= 'a' && value <= 'z') {
            str += string(value)
        }
    }
    if len(str) == 0 {
        return true
    }
    i := 0
    j := len(str)-1
    for i <= j {
        if str[i] != str[j] {
            return false
        }
        i++
        j--
    }
    return true
}

```

### b. iterative
1. 參考答案後寫出來的
[參考連結（「PDF下載」中的PDF）](https://github.com/willshang/go-leetcode)
```
import (
    "fmt"
    "strings"
)

func isPalindrome(s string) bool {
    s = strings.ToLower(s)
    i, j := 0, len(s)-1

    for i < j {
        for i < j && !isChar(s[i]) {
            i++
        }
        for i < j && !isChar(s[j]) {
            j--
        }
        if s[i] != s[j] {
            return false
        }
        i++
        j--        
    }
    return true
}

func isChar(c byte) bool {
    if ('a' <= c && c <= 'z') || ('0' <= c && c <= '9') {
        return true
    } else {
        return false
    }
}
```


## 20230216 (Day 5)
### 226. Invert Binary Tree 翻轉二元樹 [題目](https://leetcode.com/problems/invert-binary-tree/submissions/899118854/)

> 0-6M: Google, Amazon, Bloomberg, Adobe, Facebook
> 6M-1Y: Microsoft, Uber
> 1Y-2Y:LinkedIn, Baidu, eBay

### a. Recursion
1. 參考
[參考連結](https://leetcode.com/problems/invert-binary-tree/solutions/1932370/golang/)
[參考連結（「PDF下載」中的PDF）](https://github.com/willshang/go-leetcode)
```
func invertTree(root *TreeNode) *TreeNode {
    if root == nil || (root.Left == nil && root.Right == nil) {
        return root
    }
    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
    return root
}
```

2. 經過自己思考後寫出來的
[參考影片](https://www.youtube.com/watch?v=_Bx_IeZrEKg)
```
func invertTree(root *TreeNode) *TreeNode {
    if root == nil || (root.Left == nil && root.Right == nil) {
        return root
    }
    tmp := root.Left // 要嘛如前一個做法同時swap，不然就要暫存其中一個的值，否則非同時又沒有暫存的話原先的值會被蓋掉
    root.Left= invertTree(root.Right) 
    root.Right = invertTree(tmp)
    return root
}
```

### b.還沒看的另一種解法
1. 參考
[參考連結（「PDF下載」中的PDF）](https://github.com/willshang/go-leetcode)
（實際跑過，compile error）

### 心得
神奇，很神奇，一直不太知道recursion怎麼跑的，雖然寫出來了，但還要再多思考幾次。

## 20230217 (Day6)
### :heavy_check_mark: 242. Valid Anagram 可靠的異位詞 [題目](https://leetcode.com/problems/valid-anagram/)

### a. 
1. 自己寫的！！！
[語法參考連結](https://stackoverflow.com/questions/22688651/golang-how-to-sort-string-or-byte)
```
import (
    "fmt"
    "sort"
    "strings"
)
func isAnagram(s string, t string) bool {
    s_sorted := SortString(s)
    t_sorted := SortString(t)
    if s_sorted == t_sorted {
        return true
    } else { return false }
}

func SortString(s string) string {
    w := strings.Split(s, "") // string to []string
    sort.Strings(w) // sort
    return strings.Join(w, "") // []string to string
}
```

### 704. Binary Search 二元搜尋 [題目](https://leetcode.com/problems/binary-search/)
### a. 暴力解
1. 自己寫的（從中間開始搜尋，往上或往下找）（O(n)）(TLE)

```
func search(nums []int, target int) int {
    for i := len(nums)/2; i < len(nums); {
        if target == nums[i] {
            return i
        } else if target < nums[i] {
            i--
        } else if target > nums[i] {
            i++
        }
    } 
    return -1
}
```
2. 參考
很奇怪，這個做法看起來也是暴力解卻過了，沒有TLE？
```
func search(nums []int, target int) int {
    if nums[0] > target || nums[len(nums)-1] < target {
        return -1
    }
    for i := 0; i < len(nums); i++ {
        if nums[i] == target {
            return i
    }
        if nums[i] > target {
            return -1
        } 
    } 
    return -1  
}
```

### b. Recursion
1. 參考（swith）
```
func search(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        mid := (l+r)/2
        switch {
            case target < nums[mid]:
                r = mid - 1
            case target > nums[mid]:
                l = mid + 1
            default:
                return mid
        }
    }
    return -1
}
```
2. 自己將switch改成if-else
> 技巧：
> 1. 一定要寫l <= r而不能寫l<r，否則nums = [5], target = 5的例子中會return -1，但其實答案是0
> 2. mid一定要放在for loop裏面，以便隨著l, r的值一起變動
```
func search(nums []int, target int) int {
    l := 0, r := len(nums)-1
    for l <= r {
        mid := (l+r)/2 // write in the for loop to be dynamic
        if target < nums[mid] {
            r = mid - 1
        } else if target > nums[mid] {
            l = mid + 1
        } else {
            return mid
        }
    }
    return -1
}
```

## 20230218 (Day7)
### :heavy_check_mark: 235. Lowest Common Ancestor of a Binary Search Tree 二元樹的最小祖先 [題目](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/)
### a. Recursive

1. 自己寫的！（弄清語法後一次AC）

```
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {

    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    } else if p.Val > root.Val && q.Val > root.Val { 
        return lowestCommonAncestor(root.Right, p, q)
    } else {
        return root
    }
}
```

### b. Iterative

1. 看到可以用迭代後寫的

```
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	
    for root != nil {
        if p.Val < root.Val && q.Val < root.Val {
            root = root.Left
    }   else if p.Val > root.Val && q.Val > root.Val { 
            root = root.Right
    }   else {
            return root
        }
    }
    return root
}
```
### 心得
原本以為LCA of a BST很難，畢竟我才剛重新複習BST的架構與操作，看到題目時連要寫暴力解都不知道從哪著手。但我回到BST思考，覺得應該是要利用左邊節點比右邊小的特徵，接著一點一點列出p, q之間關係的所有可能，就發現規律其實很簡單。這也是我第一次自己寫出recursive的解法（雖然這題其實只有一種東西需要return，所以寫法很簡單），之前都只是知道概念而未操作過。一開始邏輯寫對了，但是p.Val和q.Val都只寫出p, q，所以一直得到無法進行比較的error，一開始以為問題在root.Val上，後來直接看了解答才知道要寫p.Val和q.Val，更改後就過了。
AC後很開心的跑去找媽咪告訴他，順便拉著他硬講解了一番，用我們家的例子解釋，居然解釋通了！我超棒！
後來發現另一個做法也很簡單，邏輯相同，只是把寫法改成iterative而已，所以很快看完後自己也寫出來了。
一開始多寫了兩行
```
    if p.Val == root.Val { return p } 
    if q.Val == root.Val { return q }
```
後來看到解答其他部分跟我寫的一模一樣，卻少了這兩行，思考一下才發現其實else已經包含了p,q的值與root的值相同的情況。else裡包含的情況有：1. p,q之中，一個小於root，一個大於root。2. p與root相同。3. q與root相同。

## 20230219 (Day8)
### 733. Flood Fill 填滿洪水[題目](https://leetcode.com/problems/flood-fill/)
### a. 
1. （Not yet solved）

## 20230221 (Day9)
### 26. Remove Duplicates from Sorted Array 殺掉多出來的那個！ [題目](https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/)
### a. 指針（記數法）
1. 參考
[參考連結（「PDF下載」中的PDF）](https://github.com/willshang/go-leetcode)
概念：雙指針，數字前移
```
func removeDuplicates(nums []int) int {
    count := 1
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] != nums[i+1] {
            nums[count] = nums[i+1]
            count++
        }
    }
    return count
}
```

### :heavy_check_mark: 27. Remove Element 殺掉元素 [題目](https://leetcode.com/problems/remove-element/description/)

### a. 指針
1. 自己寫的！（跟26題概念相同）
概念：雙指針，數字前移。一旦前面出現過要刪除的數字，後面的數字就算是要留下來的（跟val不相同），還是得往前挪。重點：找出要留下來的，把他們往前移。
```
func removeElement(nums []int, val int) int {
    count := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != val {
            nums[count] = nums[i]
            count++
        }
    }
    return count
}
```

2. 雙指針，最後的數字往前移（尚不太懂最後為什麼return r而非r-1）
```
func removeElement(nums []int, val int) int {
    l, r := 0, len(nums)
    for l < r { 
        if nums[l] == val {
            nums[l] = nums[r-1]
            r--
        } else {
            l++
        }
    }
    return r // why not return r-1?
}
    
```
### :heavy_check_mark:  283. Move Zeros 移靈 [題目](https://leetcode.com/problems/move-zeroes/description/)

### a. 指針
1. 自己寫的！

```
func moveZeroes(nums []int)  {
    count := 0
    for i := 0; i < len(nums); i++{
        if nums[i] != 0 {
            if count != i {
                nums[count] = nums[i]
                nums[i] = 0
                count++
            } else {
                nums[count] = nums[i]
                count++
            }
        }
    }
}
```
2. 參考答案後的優化
[參考連結](https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0283.Move-Zeroes/)
```
func moveZeroes(nums []int)  {
    count := 0
    for i := 0; i < len(nums); i++{
        if nums[i] != 0 {
            if count != i {
                nums[count], nums[i] = nums[i], nums[count]
            } 
            count++
        }
    }
}
```

### 2460. Apply Operation to an Array 操作數組 [題目](https://leetcode.com/problems/apply-operations-to-an-array/description/)
### a. 指針
1. （Not yet solved）（感覺跟前幾題很像，但卡住了寫不出來，網路上的講解極少）

## 20230222 (Day10)
### 110. Balanced Binary Tree 平衡二叉樹 [題目](https://leetcode.com/problems/balanced-binary-tree/description/)
### a. dfs
1. 參考後寫出來，熟悉度尚不高
```
func isBalanced(root *TreeNode) bool {
    return dfs(root) != -1
}

func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := dfs(root.Left)
    right := dfs(root.Right)

    if left != -1 && right != -1 && abs(left, right) <= 1 {
        return max(left, right) + 1
    } else {
        return -1
    }
}

func abs(a, b int) int {
    if a > b {
        return a - b
    } else {
        return b - a
    }
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}
```

### 141. Linked List Cycle 鏈表環 [題目](https://leetcode.com/problems/linked-list-cycle/description/)
相似題目：142. Linked List Cycle 2
### a. 指針
1. 參考
[參考連結](https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0141.Linked-List-Cycle/)
```
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func hasCycle(head *ListNode) bool {
    fast := head
    slow := head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}
```

## 20230223 (Day11)
### 232. Implement Queue using Stacks 用堆實現棧 [題目](https://leetcode.com/problems/implement-queue-using-stacks/description/)
### a. slice
1. 參考
```
type MyQueue struct {
    a []int
}


func Constructor() MyQueue {
    return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
    this.a = append(this.a, x)
}


func (this *MyQueue) Pop() int {
    first := this.a[0]
    this.a = this.a[1:]
    return first
}


func (this *MyQueue) Peek() int {
    if len(this.a) == 0 {
        return 0
    }
    return this.a[0]
}


func (this *MyQueue) Empty() bool {
    if len(this.a) == 0 {
        return true
    }
    return false
}
```
### b. 2 stacks
1. 參考
```
type MyQueue struct {
    a, b *Stack
}


func Constructor() MyQueue {
    return MyQueue{
        a : NewStack(),
        b : NewStack(),
    }
}


func (this *MyQueue) Push(x int)  {
    this.a.Push(x)
}


func (this *MyQueue) Pop() int {
    if this.b.Len() == 0 {
        for this.a.Len() > 0 {
            this.b.Push(this.a.Pop())
        }
    }
    return this.b.Pop()
}


func (this *MyQueue) Peek() int {
    res := this.Pop()
    this.b.Push(res)
    return res
}


func (this *MyQueue) Empty() bool {
    return this.a.Len() == 0 && this.b.Len() == 0
}

type Stack struct {
    nums []int
}

func NewStack() *Stack {
    return &Stack {
        nums: []int{},
    }
}

func (s *Stack) Push(n int) {
    s.nums = append(s.nums, n)
}

func (s *Stack) Pop() int {
    res := s.nums[len(s.nums)-1]
    s.nums = s.nums[:len(s.nums)-1]
    return res
}

func (s *Stack) Len() int {
    return len(s.nums)
}

func (s *Stack) IsEmpty() bool {
    return s.Len() == 0
}
```

## 20230227 (Day)
### 383. Ransom Note 勒索信 [題目](https://leetcode.com/problems/ransom-note/description/)
### :heavy_check_mark: a. map
1. 自己寫的！
```
import (
    "fmt"
//  "sort"
    "strings"
)

func canConstruct(ransomNote string, magazine string) bool {
    // magazine = SortString(magazine)
    my_map := make(map[rune]rune)

    for _, m := range magazine {
        if _, exist := my_map[m]; exist {
            my_map[m] = (my_map[m])+1
        } else {
            my_map[m] = 1
        }
    }
    for _, r := range ransomNote {
        if _, exist := my_map[r]; exist {
            if my_map[r] == 1 {
                delete(my_map, r)
            } else {
                my_map[r] = (my_map[r])-1
            }
        } else {
            return false
        }
    }
    return true
}

// func SortString(s string) string {
//     w := strings.Split(s, "") // string to []string
//     sort.Strings(w) // sort
//     return strings.Join(w, "") // []string to string
// }
```
### b. array
[參考連結](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0383.Ransom-Note)
```
func canConstruct(ransomNote string, magazine string) bool {
    if len(ransomNote) > len(magazine) {
        return false
    }

    var cnt [26]int
    for _, v := range magazine {
        cnt[v-'a']++
    } 
    for _, v := range ransomNote {
        cnt[v-'a']--
        if cnt[v-'a'] < 0 {
            return false
        }
    }
    return true
}
```

### 心得



## 20230228 (Day)
### 70. Climbling Stairs 爬樓梯 [題目](https://leetcode.com/problems/climbing-stairs/)
### a. 動態規劃
1. 參考
[費波那契數列](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/fibonacci.html)
```
// Time: O(n), Space: O(n)

func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
```

### :heavy_check_mark: 409. Longest Palindrome 最長回文 [題目](https://leetcode.com/problems/longest-palindrome/)
### a. 暴力解
1. 自己寫的
```
func longestPalindrome(s string) int {
    if len(s) == 0 {
        return 0
    }
    if len(s) == 1 {
        return 1
    } 
    var pal [60]int
    cnt := 0
    ones := 0
    dup := 0
    for _, s := range s {
        pal[s-'A']++
    }
    for _, t := range pal {
        if t % 2 == 0 { // t is even
            cnt += t
        } else if t == 1 {
            ones -= 1
        } else {
            cnt += t - 1
            dup += 1
        }
    }
    if dup > 0 {
        return cnt + 1
    } else if dup == 0 && ones < 0 {
        return cnt + 1
    } else {
        return cnt
    }
}
```

### 206. Reverse Linked List 翻轉鏈表 [題目](https://leetcode.com/problems/reverse-linked-list/)
### Recursive
1. 參考（尚未理解）
[參考連結](https://algorithm.yuanbin.me/zh-tw/linked_list/reverse_linked_list.html)
[參考連結](https://ithelp.ithome.com.tw/articles/10271920)
```
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    result := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return result
}
```
### :heavy_check_mark: 169. Majority Element [題目](https://leetcode.com/problems/majority-element/description/)
### Array
1. 自己寫的
```
func majorityElement(nums []int) int {
    var temp1 [10000]int // positives
    var temp2 [10000]int // negatives
    for _, i := range nums {
        if i < 0 {
            temp2[-i]++
        } else {
            temp1[i]++
        }
    }
    for idx, i := range temp1 {
        if i > len(nums)/2 {
            return idx
        }
    }
    for idx, i := range temp2 {
        if i > len(nums)/2 {
            return -idx
        }
    }
    return -1
}
```

## 20230301 (Day)
### 876. Middle of the Linked List [題目](https://leetcode.com/problems/middle-of-the-linked-list/)
### a. Pointer
1. 

```
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}
```

## 20230302 (Day)
### 104. Maximun Depth of Binary Tree 二元樹的最大深度 [題目](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)
### a. Recursive
1. 
```
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    return max(left, right) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## 20230303 (Day)
### :heavy_check_mark: 217. Contains Duplicate 包含重複 [題目](https://leetcode.com/problems/contains-duplicate/)
### a. Iteration 
1. 
```
func containsDuplicate(nums []int) bool {
    sort.Ints(nums)
    for i := 1; i < len(nums); i++ {
        if nums[i-1] == nums[i] {
            return true
        } else {
            continue
        }
    }
    return false
}
```

### b. Map
1. 
```
// Time: O(n), Space: O(n)
func containsDuplicate(nums []int) bool {
    my_map := make(map[int]int)
    for _, v := range nums{
        if _, exist := my_map[v]; exist {
            return true
        } else {
            my_map[v] = v 
        }
    }
    return false
}
```


### :heavy_check_mark: 219. Contains Duplicate 2 包含重複2 [題目](https://leetcode.com/problems/contains-duplicate-ii/description/)
### a. Map
1. 

```
func containsNearbyDuplicate(nums []int, k int) bool {
    my_map := make(map[int]int)
    for idx, v := range nums {
        if _, exist := my_map[v]; exist {
            if idx - my_map[v] <= k {
                return true
            } else {
                my_map[v] = idx
            }
        } else {
            my_map[v] = idx
        }
    }
    return false
}
```

## 20230304 (Day)
### 13. Roman to Integer 羅馬數字翻譯 [題目](https://leetcode.com/problems/roman-to-integer/description/)
### a. Iteration 
1. Bobby陪我一起寫完的
```
func romanToInt(s string) int {
    w := strings.Split(s, "") // slice to []string
    cnt := 0
    for i := 0; i < len(w); i++ {
        if i != len(w)-1 {
            if w[i] == "I" && w[i+1] == "V" {
                cnt += 4
                i++
                continue
            }
            if w[i] == "I" && w[i+1] == "X" {
                cnt += 9
                i++
                continue
            }
            if w[i] == "X" && w[i+1] == "L" {
                cnt += 40
                i++
                continue
            }
            if w[i] == "X" && w[i+1] == "C" {
                cnt += 90
                i++
                continue
            }
            if w[i] == "C" && w[i+1] == "D" {
                cnt += 400
                i++
                continue
            }
            if w[i] == "C" && w[i+1] == "M" {
                cnt += 900
                i++
                fmt.Println(cnt, i)
                continue
            }
        }
        if w[i] == "I" { cnt += 1 }
        if w[i] == "V" { cnt += 5 }
        if w[i] == "X" { cnt += 10}
        if w[i] == "L" { cnt += 50 }
        if w[i] == "C" { cnt += 100 }
        if w[i] == "D" { cnt += 500 }
        if w[i] == "M" { cnt += 1000 }
    }
    return cnt
}
```

## 20230305 (Day)
### :heavy_check_mark: 844. Backspace String Compare [題目](https://leetcode.com/problems/backspace-string-compare/description/)
### a. Stack 
1. 
```
import (
    "fmt"
    "strings"
)
func backspaceCompare(s string, t string) bool {
    ss := strings.Split(s, "")
    tt := strings.Split(t, "")
    var stack_s []string
    var stack_t []string
    for i := 0; i < len(ss); i++ {
        if ss[i] != "#" {
            stack_s = append(stack_s, ss[i])
        } else {
            if len(stack_s) != 0 {
                stack_s = stack_s[:len(stack_s)-1]
            } else {
                continue
            }
        }
    }
    for i := 0; i < len(tt); i++ {
        if tt[i] != "#" {
            stack_t = append(stack_t, tt[i])
        } else {
            if len(stack_t) != 0 {
                stack_t = stack_t[:len(stack_t)-1]
            } else {
                continue
            }
        }
    }    
    // fmt.Println(stack_s)
    // fmt.Println(stack_t)
    for i := 0; i < max(len(stack_t), len(stack_s)); i++ {
        if  len(stack_s) != len(stack_t) {
            return false
        } else if stack_s[i] != stack_t[i] {
            return false
        }
    }
    return true
}
func max(a, b int) int {
    if a > b {
        return a
    } 
    return b
}
```

b. 將if-else判斷式獨立寫成function
```
func backspaceCompare(s string, t string) bool {
    return check(s) == check(t)
}
func check(str string) string {
    res := make([]string, 0)
    for _, v := range str {
        if string(v) != "#" {
            res = append(res, string(v))
        } else if string(v) == "#" {
            if len(res) != 0 {
                res = res[:len(res)-1]
            }
        }
    }
    // fmt.Println(res)
    return strings.Join(res, "")
}
```
### :heavy_check_mark: 338. Counting Bits 計算二進位 [題目](https://leetcode.com/problems/counting-bits/description/)
### a. 
1. 

```
func countBits(n int) []int {
    res := make([]int, n+1)
    for i := range res {
        // fmt.Println(i, toBinary(i))
        res[i] = toBinary(i)
    }
    return res
}

func toBinary(n int) int {
    cnt := 0
    for n >= 2 {
        if n % 2 == 1 {
            cnt += 1
        }
        n = n / 2
    }
    if n == 1 { cnt += 1 }
    return cnt
}
```
### 心得
寫Counting Bits時一直執著的覺得應該要用recursion，但怎麼樣都想不出來，腦中有種卡住通不過去的感覺，後來決定去看看其他以前寫過題目中有使用recursion的，發現這題其實只需要用for就好（因為是要由上往下的除2），因此清醒過來寫了個能計算一個數在除2時會有多少餘數是1的function（用短除法計算二進位），再分開寫進題目要求回傳的[]int就好。一開始的邏輯對了後，答案還是錯，仔細看了一下是寫進res時多寫了一堆零，改掉append到res的方式後就好了。

## 20230306 
### QUENTREND
1. 
```
package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)


/*
 * Complete the 'getTripletCount' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY a
 *  2. INTEGER d
 */

func getTripletCount(a []int32, d int32) int32 {
    // Write your code here
    a_int := make([]int, len(a))
    for i := 0; i < len(a); i++ {
        a_int[i] = int(a[i])
    }
    d_int := int(d)
    cnt := 0
    for i := 0; i < len(a_int); i++ {
        for j := i+1; j < len(a_int); j++ {
            for k := j+1; k < len(a_int); k++ {
                if (a_int[i] + a_int[j] + a_int[k]) % d_int == 0 {
                    if i != j && i != k && j != k {
                        cnt += 1
                    } 
                }
            }
        }
    }
    return int32(cnt)
}
func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    aCount, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)

    var a []int32

    for i := 0; i < int(aCount); i++ {
        aItemTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
        checkError(err)
        aItem := int32(aItemTemp)
        a = append(a, aItem)
    }

    dTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)
    d := int32(dTemp)

    result := getTripletCount(a, d)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

```
2. 
```
package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)



/*
 * Complete the 'getMaximumSumOfHeights' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts INTEGER_ARRAY maxHeight as parameter.
 */
import (
    "sort"
)
func getMaximumSumOfHeights(maxHeight []int32) int64 {
    // Write your code here
    MH := make([]int, len(maxHeight))
    for i := 0; i < len(maxHeight); i++ {
        MH[i] = int(maxHeight[i])
    }
    
    cmp := make([]int, len(MH))
    for i := 1; i < len(MH)-1; i++ {
        if MH[i] > MH[i-1] && MH[i] > MH[i+1] {
            cmp[i] = MH[i]
        }
    }
    sort.Sort(cmp)
    max := cmp[len(cmp)-1]
    cnt := 0
    my_map := make(map[int]int)
    for i := range MH {
        my_map[i] = MH[i]
    }
    
    for i := 1; i < len(MH)-1; i++ {
        if i, exist := my_map[i]; exist {
            if i != max {
                MH[i] = return_max(MH[i-1], MH[i+1])
            }
        }
        cnt += MH[i]
    }  
    return int64(cnt)  
}


func return_max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    maxHeightCount, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)

    var maxHeight []int32

    for i := 0; i < int(maxHeightCount); i++ {
        maxHeightItemTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
        checkError(err)
        maxHeightItem := int32(maxHeightItemTemp)
        maxHeight = append(maxHeight, maxHeightItem)
    }

    result := getMaximumSumOfHeights(maxHeight)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}


```
3. 
```
package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)


/*
 * Complete the 'countInvestablePeriods' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY price
 *  2. INTEGER max_price
 *  3. INTEGER min_price
 */

func countInvestablePeriods(price []int32, max_price int32, min_price int32) int64 {
    // Write your code here
    p_int := make([]int, 0)
    for i := 0; i < len(price); i++ {
        p_int[i] = int(price[i])
    }
    maxp_int := int(max_price)
    minp_int := int(min_price)
    res := make([]int, len(p_int))
    cnt := 0
    for _, v := range p_int {
        if v > minp_int && v < maxp_int {
            res = append(res, v)
        } else if v < minp_int || v > maxp_int {
            if len(res) < 2 {
                res = nil
            } else {
                cnt += countSubarray(res, maxp_int, minp_int)
                res = nil
            }
        }
    }
    cnt += countSubarray(res, maxp_int, minp_int)
    return int64(cnt)
}

func countSubarray(arr []int, max int, min int) int {
    max_cnt := 0
    min_cnt := 0
    max_map := make([]int, len(arr))
    min_map := make([]int, len(arr))
    cnt := 0
    for idx, v := range arr {
        if v == max {
            max_cnt += 1
            max_map = append(max_map, idx)
        } else if v == min {
            min_cnt += 1
            min_map = append(min_map, idx)
        }
    }
    if max_cnt == 0 || min_cnt == 0 {
        return 0
    }
    cnt += (factorial(max_cnt) / factorial(max_cnt-1) * factorial(1)) * (factorial(min_cnt) / factorial(min_cnt-1) * factorial(1))
    
    return cnt
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func factorial(num int) int{
   if num == 1 || num == 0{
      return num
   }
   return num * factorial(num-1)
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    priceCount, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)

    var price []int32

    for i := 0; i < int(priceCount); i++ {
        priceItemTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
        checkError(err)
        priceItem := int32(priceItemTemp)
        price = append(price, priceItem)
    }

    max_priceTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)
    max_price := int32(max_priceTemp)

    min_priceTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)
    min_price := int32(min_priceTemp)

    result := countInvestablePeriods(price, max_price, min_price)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

```
4. 
```

```

### 100. Same Tree 同樣的樹 [題目](https://leetcode.com/problems/same-tree/)
### a. recursive
1. 
```
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
```
### :heavy_check_mark: 1539. Kth Missing Positive Number 第K個消失的正整數 [題目](https://leetcode.com/problems/kth-missing-positive-number/)
1. 
```
func findKthPositive(arr []int, k int) int {
    my_map := make(map[int]int)
    res := make([]int, 0)
    for _, v := range arr {
        my_map[v] = v
    }
    for i := 1; i < 10000; i++ {
        if _, exist := my_map[i]; !exist {
            res = append(res, i)
        } 
    }
    // fmt.Println(res)
    return res[k-1]
}
```



## 20230307 (Day1)
### 1. Number of 1 Bits [題目](https://leetcode.com/problems/number-of-1-bits/description/)
### a. / 2 (or n >> 1)
1. 
```
func hammingWeight(num uint32) int {
    cnt := 0 
    for num != 0 {
        if num & 1 == 1 {
            cnt++
        }
        num /= 2 // num = num / 2
    }
    return cnt
}
```
2. 
```
func hammingWeight(num uint32) int {
    cnt := 0
    for num != 0 {
       if num & 1 == 1 { // check the last digit of num
           cnt++
       }
       num >>= 1 // num = num >> 1
    }
    return cnt
}
```
### b. n & (n-1)
1. 
```
func hammingWeight(num uint32) int {
    cnt := 0
    for num != 0 {
        num = num & (num-1)
        cnt ++
    }
    return cnt
}
```



## 20230211 (Day1)
### 1. Two Sum 二和 [題目](https://leetcode.com/problems/two-sum/)
### a. 暴力解





