# 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. 暴力解
Sign in with Wallet
Connect another wallet