Where the dream began.
Hashing
1. Two Sum
Brute Force
func twoSum(nums []int, target int) []int { left := 0 for left < len(nums) { right := left + 1 for right < len(nums) { if nums[left] + nums[right] == target { return []int{left, right} } right++ } left++ } return []int{}}Hash Table
func twoSum(nums []int, target int) []int { hashMap := make(map[int]int) for i := 0; i < len(nums); i++ { wanted := target - nums[i] if index, ok := hashMap[wanted]; ok { return []int{index, i} } hashMap[nums[i]] = i } return nil}49. Group Anagrams
Sorting + Hash Table
func groupAnagrams(strs []string) [][]string { var ans [][]string hashMap := make(map[string][]string)
for _, str := range strs { s := []byte(str) sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) sortedStr := string(s) hashMap[sortedStr] = append(hashMap[sortedStr], str)
} for _, part := range hashMap { ans = append(ans, part) } return ans}Store Letter-Count Vectors
func groupAnagrams(strs []string) [][]string { hashMap := make(map[[26]int][]string) for _, str := range strs { cnt := [26]int{} for _, b := range str { cnt[b-'a']++ } hashMap[cnt] = append(hashMap[cnt], str) } var ans [][]string for _, v := range hashMap { ans = append(ans, v) } return ans}128. Longest Consecutive Sequence
Sorting
func longestConsecutive(nums []int) int { sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] }) cur := 1 maxNum := 1 if len(nums) == 0 { return 0 } if len(nums) == 1 { return 1 }
pre := nums[0] for i := 1; i < len(nums); i++ { if nums[i] == pre { continue } if nums[i] == pre + 1 { cur++ } else if nums[i] > pre + 1 { maxNum = max(cur, maxNum) cur = 1 } pre = nums[i] } return max(maxNum, cur)}The official solution doesn’t mention sorting, yet sorting is faster and uses less memory. What’s that about?
Deduplicate with a Hash Table
func longestConsecutive(nums []int) int { numSet := make(map[int]bool) for _, num := range nums { numSet[num] = true } longestStreak := 0 for num := range numSet { if !numSet[num - 1] { currentNum := num currentStreak := 1 for numSet[currentNum + 1] { currentNum++ currentStreak++ } if longestStreak < currentStreak { longestStreak = currentStreak } } } return longestStreak}Two Pointers
283. Move Zeroes
Swap with Two Pointers
func moveZeroes(nums []int) { left := 0
for right := 0; right < len(nums); right++ { if nums[right] != 0 { nums[left], nums[right] = nums[right], nums[left] left++ } }}11. Container With Most Water
Two Pointers + Greedy
func maxArea(height []int) int { left, right := 0, len(height) - 1 var s, ans int for left < right { s = (right - left)*min(height[left], height[right]) if s > ans { ans = s } if height[left] >= height[right] { right-- } else { left++ } } return ans}15. 3Sum
Fix One Number, Use Two Pointers for the Other Two
func threeSum(nums []int) [][]int { var ans [][]int sort.Slice(nums, func(i, j int) bool { return nums[i] <= nums[j] }) for i := 0; i < len(nums)-2; i++ { if i > 0 && nums[i - 1] == nums[i] { continue } x := nums[i] left := i + 1 right := len(nums) - 1
for left < right { y := nums[left] + nums[right] if y + x == 0 { ans = append(ans, []int{x, nums[left], nums[right]}) for nums[right] == nums[right - 1] && left < right { right-- } for nums[left] == nums[left + 1] && left < right { left++ } left++ right-- } else if y + x > 0 { right-- } else if y + x < 0 { left++ } } } return ans}This can be optimized a little.
Add Pruning and Clean Up the Syntax
func threeSum(nums []int) [][]int { slices.Sort(nums) length := len(nums) ans := make([][]int, 0) for i, num := range nums { if num > 0 { break } if i > 0 && nums[i - 1] == num { continue } target := -num left, right := i + 1, length - 1 for left < right { sum := nums[left] + nums[right] if sum > target { right-- } else if sum < target { left++ } else { for left < right && nums[left] == nums[left + 1] { left++ } for left < right && nums[right] == nums[right - 1] { right-- } ans = append(ans, []int{num, nums[left], nums[right]}) left++ right-- } } } return ans}slices.Sort versus sort.Slice:
The former uses generics and avoids a closure, giving better performance.
nSum
func nSum(nums []int, n int, start int, target int) [][]int { res := [][]int{} length := len(nums)
if n < 2 || length-start < n { return res }
if n == 2 { left, right := start, length-1 for left < right { sum := nums[left] + nums[right] if sum == target { res = append(res, []int{nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] { left++ } for left < right && nums[right] == nums[right-1] { right-- }
left++ right-- } else if sum < target { left++ } else { right-- } } return res }
for i := start; i < length; i++ { if i > start && nums[i] == nums[i-1] { continue }
if nums[i]*n > target { break }
if nums[length-1]*n < target { break }
sub := nSum(nums, n-1, i+1, target-nums[i])
for _, arr := range sub { res = append(res, append([]int{nums[i]}, arr...)) } }
return res}42. Trapping Rain Water
Sir, All I Know Is Two Pointers
func trap(height []int) int { l := len(height) left := 0 right := l - 1 leftMax := 0 rightMax := 0 ans := 0
for left < right { leftMax = max(leftMax, height[left]) rightMax = max(rightMax, height[right]) if height[left] < height[right] { ans += leftMax - height[left] left++ } else { ans += rightMax - height[right] right-- } } return ans}Sliding Window
3. Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters
Hashing + Sliding Window
func lengthOfLongestSubstring(s string) int { hashMap := make(map[byte]bool) left := 0 maxLen := 0
for right := 0; right < len(s); right++ { for hashMap[s[right]] { delete(hashMap, s[left]) left++ } hashMap[s[right]] = true if right - left + 1 > maxLen { maxLen = right - left + 1 } } return maxLen}4ms
Clean Up the Implementation
func lengthOfLongestSubstring(s string) int { res, left := 0, 0 cnt := [128]int{} for right := 0; right < len(s); right++ { cnt[s[right]]++ for cnt[s[right]] >= 2 { cnt[s[left]]-- left++ } res = max(res, right-left+1) } return res}0ms
438. Find All Anagrams in a String
Fixed-Length Window, 26 Letters
func findAnagrams(s string, p string) []int { sLen, pLen := len(s), len(p) if sLen < pLen { return []int{} } ans := []int{} var sCount, pCount [26]int for i, ch := range p { sCount[s[i]-'a']++ pCount[ch-'a']++ } if pCount == sCount { ans = append(ans, 0) }
for i, ch := range s[:sLen - pLen] { sCount[ch-'a']-- sCount[s[i+pLen]-'a']++ if sCount == pCount { ans = append(ans, i + 1) } } return ans}Substrings
560. Subarray Sum Equals K
Brute Force + Prefix Sums
func subarraySum(nums []int, k int) int { n := len(nums) sum := make([]int, n+1)
for i := 0; i < n; i++ { sum[i+1] = sum[i] + nums[i] }
ans := 0 for i := 0; i < n; i++ { for j := i; j < n; j++ { if sum[j+1]-sum[i] == k { ans++ } } } return ans}Hash Table + Prefix Sums
func subarraySum(nums []int, k int) int { count := 0 prefix := 0 m := map[int]int{0: 1}
for _, num := range nums { prefix += num if v, ok := m[prefix-k]; ok { count += v } m[prefix]++ } return count}239. Sliding Window Maximum
Deque
func maxSlidingWindow(nums []int, k int) []int { n := len(nums) var ans []int deque := []int{} for i := 0; i < n; i++ { if len(deque) > 0 && deque[0] < i-k+1 { deque = deque[1:] } for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] { deque = deque[:len(deque)-1] } deque = append(deque, i) if i >= k-1 { ans = append(ans, nums[deque[0]]) } } return ans}But this version isn’t as fast as the following one.
func maxSlidingWindow(nums []int, k int) []int { if len(nums) == 0 || k == 0 { return []int{} }
n := len(nums) result := make([]int, 0, n - k + 1) deque := make([]int, 0 , k)
for i := 0; i < n; i++ { if len(deque) > 0 && deque[0] < i - k + 1 { deque = deque[1:] }
for len(deque) > 0 && nums[deque[len(deque) - 1]] < nums[i] { deque = deque[:len(deque) - 1] }
deque = append(deque, i)
if i >= k-1 { result = append(result, nums[deque[0]]) } }
return result}The difference is just result := make([]int, 0, n - k + 1) and deque := make([]int, 0 , k).
All because the capacity is allocated in advance.
make(type, size, cap)
The first takes 8 ms, while the second takes 1 ms.
Isn’t that something?
76. Minimum Window Substring
Sliding Window + Hash Table
func minWindow(s string, t string) string { need := make(map[byte]int) window := make(map[byte]int) for i := 0; i < len(t); i++ { need[t[i]]++ }
left, count := 0, 0 start, minLen := 0, len(s)+1
for right := 0; right < len(s); right++ { c := s[right] if _, ok := need[c]; ok { window[c]++ if window[c] == need[c] { count++ } } for count == len(need) { if right-left+1 < minLen { start = left minLen = right-left+1 } d := s[left] left++ if _, ok := need[d]; ok { if window[d] == need[d] { count-- } window[d]-- } } } if minLen == len(s) + 1 { return "" } return s[start : start + minLen]}29ms
func minWindow(s string, t string) string { n, m := len(s), len(t) if n < m { return "" } var c1, c2 [60]int tot := 0 for i := 0; i < m; i++ { idx := getIdx(t[i]) if c1[idx] == 0 { tot++ } c1[idx]++ } ans := "" for i, j := 0, 0; i < n; i++ { idx1 := getIdx(s[i]) c2[idx1]++ if c2[idx1] == c1[idx1] { tot-- }
for j < i { idx2 := getIdx(s[j]) if c2[idx2] > c1[idx2] { c2[idx2]-- j++ } else { break } }
if tot == 0 { if ans == "" || len(ans) > i-j+1 { ans = s[j : i+1] } } } return ans}
func getIdx(x byte) int { if x >= 'A' && x <= 'Z' { return int(x - 'A' + 26) } return int(x - 'a')}0ms
General Arrays
53. Maximum Subarray
Prefix Sums
func maxSubArray(nums []int) int { minPre := 0 curPre := 0 maxSum := nums[0] for _, x := range nums { curPre += x if curPre - minPre > maxSum { maxSum = curPre - minPre } if curPre < minPre { minPre = curPre } } return maxSum}Divide and Conquer
I don’t really have this down yet. I’ll come back to it later.
func maxSubArray(nums []int) int { return get(nums, 0, len(nums) - 1).mSum;}
func pushUp(l, r Status) Status { iSum := l.iSum + r.iSum lSum := max(l.lSum, l.iSum + r.lSum) rSum := max(r.rSum, r.iSum + l.rSum) mSum := max(max(l.mSum, r.mSum), l.rSum + r.lSum) return Status{lSum, rSum, mSum, iSum}}
func get(nums []int, l, r int) Status { if (l == r) { return Status{nums[l], nums[l], nums[l], nums[l]} } m := (l + r) >> 1 lSub := get(nums, l, m) rSub := get(nums, m + 1, r) return pushUp(lSub, rSub)}
func max(x, y int) int { if x > y { return x } return y}
type Status struct { lSum, rSum, mSum, iSum int}56. Merge Intervals
The Straightforward Approach
func merge(intervals [][]int) [][]int { var ans [][]int var left, right int sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) for i := 0; i < len(intervals); i++ { left = intervals[i][0] right = intervals[i][1] for i < len(intervals)-1 && intervals[i+1][0] <= right { right = max(intervals[i+1][1], right) i++ } ans = append(ans, []int{left, right}) } return ans}Sorting + In-Place Modification
func merge(intervals [][]int) [][]int { if (len(intervals) == 1) { return intervals } sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) res := make([][]int, 0) res = append(res, intervals[0]) for i := 1; i < len(intervals); i++ { if (res[len(res)-1][1] >= intervals[i][0]) { res[len(res)-1][1] = max(res[len(res)-1][1], intervals[i][1]) } else { res = append(res, intervals[i]) } } return res}189. Rotate Array
Three Reversals
func rotate(nums []int, k int) { k %= len(nums) reverse(nums) reverse(nums[:k]) reverse(nums[k:])}
func reverse(nums []int) { for i, n := 0, len(nums); i < n/2; i++ { nums[i], nums[n-1-i] = nums[n-1-i], nums[i] }}238. Product of Array Except Self
Prefix Products and Suffix Products
func productExceptSelf(nums []int) []int { l := len(nums) ans := make([]int, l)
ans[0] = 1 for i := 1; i < l; i++ { ans[i] = nums[i-1] * ans[i-1] }
R := 1 for i := l - 1; i >= 0; i-- { ans[i] = ans[i] * R R *= nums[i] } return ans}41. First Missing Positive
In-Place Hash Table
func firstMissingPositive(nums []int) int { l := len(nums) for i := 0; i < l; i++ { if nums[i] <= 0 { nums[i] = l + 1 } }
for i := 0; i < l; i++ { num := abs(nums[i]) if num <= l { nums[num - 1] = -abs(nums[num - 1]) // Mark the value } }
for i := 0; i < l; i++ { if nums[i] > 0 { return i + 1 } } return l + 1}
func abs(x int) int { if x < 0 { return -x } return x}Matrices
73. Set Matrix Zeroes
Two Flags
func setZeroes(matrix [][]int) { n, m := len(matrix), len(matrix[0]) // Handle the first row and first column in advance row0, col0 := false, false for _, v := range matrix[0] { if v == 0 { row0 = true break } }
for _, r := range matrix { if r[0] == 0 { col0 = true break } }
for i := 1; i < n; i++ { for j := 1; j < m; j++ { if matrix[i][j] == 0 { matrix[i][0] = 0 matrix[0][j] = 0 } } }
for i := 1; i < n; i++ { for j := 1; j < m; j++ { if matrix[i][0] == 0 || matrix[0][j] == 0 { matrix[i][j] = 0 } } }
if row0 { for j :=0; j < m; j++ { matrix[0][j] = 0 } }
if col0 { for i := 0; i < n; i++ { matrix[i][0] = 0 } }}One Flag
I don’t like this one.
It’s less intuitive than using two flags.
func setZeroes(matrix [][]int) { n, m := len(matrix), len(matrix[0]) col0 := false for _, r := range matrix { if r[0] == 0 { col0 = true } for j := 1; j < m; j++ { if r[j] == 0 { r[0] = 0 matrix[0][j] = 0 } } } for i := n - 1; i >= 0; i-- { for j := 1; j < m; j++ { if matrix[i][0] == 0 || matrix[0][j] == 0 { matrix[i][j] = 0 } } if col0 { matrix[i][0] = 0 } }}54. Spiral Matrix
Traverse in the Required Order
func spiralOrder(matrix [][]int) []int { ans := []int{} n, m := len(matrix[0]), len(matrix) top, bottom, left, right := 0, m - 1, 0, n - 1 for top <= bottom && left <= right { // Right for i := left; i <= right; i++ { ans = append(ans,matrix[top][i]) } top++ // Down for i := top; i <= bottom; i++ { ans = append(ans,matrix[i][right]) } right-- // Left if top <= bottom { for i := right; i >= left; i-- { ans = append(ans,matrix[bottom][i]) } bottom-- } // Up if left <= right { for i := bottom; i >= top; i-- { ans = append(ans,matrix[i][left]) } left++ } } return ans}48. Rotate Image
Fold Across the Diagonal, Then Reflect Each Row
func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n; i++ { for j := i; j < n; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } } for i := 0; i < n; i++ { for j := 0; j < n/2; j++ { matrix[i][j],matrix[i][n-1-j] = matrix[i][n-1-j],matrix[i][j] } }}240. Search a 2D Matrix II
Binary Search
I hadn’t used sort.SearchInts() before. Turns out it’s a standard binary search.
func searchMatrix(matrix [][]int, target int) bool { for _, row := range matrix { i := sort.SearchInts(row, target) if i < len(row) && row[i] == target { return true } } return false}Z-Shaped Search
Walk through matrix[x][y].
func searchMatrix(matrix [][]int, target int) bool { m, n := len(matrix), len(matrix[0]) x, y := 0, n-1 for x < m && y >= 0 { if matrix[x][y] == target { return true } if matrix[x][y] > target { y-- } else { x++ } } return false}Linked Lists
160. Intersection of Two Linked Lists
Intersection of Two Linked Lists
Two Pointers Meet
func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } pa, pb := headA, headB for pa != pb { if pa == nil { pa = headB } else { pa = pa.Next } if pb == nil { pb = headA } else { pb = pb.Next } } return pa}206. Reverse Linked List
Maintain cur & pre
func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } var pre *ListNode cur,next := head, head.Next for cur != nil { next = cur.Next cur.Next = pre pre = cur cur = next } return pre}234. Palindrome Linked List
Traverse and Convert to an Array
func isPalindrome(head *ListNode) bool { vals := []int{} for ; head != nil; head = head.Next { vals = append(vals, head.Val) } n := len(vals) for i, v := range vals[:n/2] { if v != vals[n-1-i] { return false } } return true}Reverse from the Middle with Fast and Slow Pointers
I understand it, but I still don’t want to write it.
func isPalindrome(head *ListNode) bool { if head == nil && head.Next == nil { return true }
slow, fast := head, head for fast.Next != nil && fast.Next.Next != nil { slow = slow.Next fast = fast.Next.Next }
var prev *ListNode cur := slow.Next for cur != nil { next := cur.Next cur.Next = prev prev = cur cur = next }
p1, p2 := prev, head for p1 != nil && p2 != nil { if p1.Val != p2.Val { return false } p1 = p1.Next p2 = p2.Next }
return true}141. Linked List Cycle
Fast and Slow Pointers
func hasCycle(head *ListNode) bool { slow, fast := head, head
for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next
if slow == fast { return true } }
return false}142. Linked List Cycle II
A Math Problem
func detectCycle(head *ListNode) *ListNode { slow, fast := head, head for fast != nil { slow = slow.Next if fast.Next == nil { return nil } fast = fast.Next.Next if fast == slow { p := head for p != slow { p = p.Next slow = slow.Next } return p } } return nil}21. Merge Two Sorted Lists
Use a Dummy Node and Append in Order
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { dummy := ListNode{} cur := &dummy for list1 != nil && list2 != nil { if list1.Val <= list2.Val { cur.Next = list1 list1 = list1.Next } else { cur.Next = list2 list2 = list2.Next } cur = cur.Next } if list1 != nil { cur.Next = list1 } else { cur.Next = list2 } return dummy.Next}2. Add Two Numbers
Ugly, but It Passes
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy := ListNode{} cur := &dummy curSum := 0 curVal := 0 carry := 0 for l1 != nil && l2 != nil { curSum = l1.Val + l2.Val + carry carry = curSum / 10 curVal = curSum % 10 cur.Next = &ListNode{ Val: curVal, Next: nil, } cur = cur.Next l1 = l1.Next l2 = l2.Next } if l1 != nil { for l1 != nil { curSum = l1.Val + carry carry = curSum / 10 curVal = curSum % 10 cur.Next = &ListNode{ Val: curVal, Next: nil, } cur = cur.Next l1 = l1.Next } } else { for l2 != nil { curSum = l2.Val + carry carry = curSum / 10 curVal = curSum % 10 cur.Next = &ListNode{ Val: curVal, Next: nil, } cur = cur.Next l2 = l2.Next } } if carry != 0 { cur.Next = &ListNode{ Val: carry, Next: nil, } } return dummy.Next}Optimized Version
Combine the three pieces of logic.
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} cur := dummy carry := 0
for l1 != nil || l2 != nil || carry != 0 { sum := carry
if l1 != nil { sum += l1.Val l1 = l1.Next } if l2 != nil { sum += l2.Val l2 = l2.Next }
cur.Next = &ListNode{Val: sum % 10} cur = cur.Next carry = sum / 10 }
return dummy.Next}19. Remove Nth Node From End of List
Remove Nth Node From End of List
Traverse, Then Locate the Node Directly
func removeNthFromEnd(head *ListNode, n int) *ListNode { length := getLength(head) dummy := &ListNode{Next: head} cur := dummy for i := 0; i < length-n; i++ { cur = cur.Next } cur.Next = cur.Next.Next return dummy.Next}
func getLength(head *ListNode) (length int) { for ; head != nil; head = head.Next { length++ } return}Two Pointers Spaced n Nodes Apart
func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{0, head} first, second := head, dummy for i := 0; i < n; i++ { first = first.Next } for ; first != nil; first = first.Next { second = second.Next } second.Next = second.Next.Next return dummy.Next}24. Swap Nodes in Pairs
Recursion
func swapPairs(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } newHead := head.Next head.Next = swapPairs(newHead.Next) newHead.Next = head return newHead}Iteration
func swapPairs(head *ListNode) *ListNode { dummy := &ListNode{Next: head} cur := dummy
for cur.Next != nil && cur.Next.Next != nil { node1 := cur.Next node2 := cur.Next.Next
node1.Next = node2.Next node2.Next = node1 cur.Next = node2 cur = node1 } return dummy.Next}25. Reverse Nodes in k-Group
I hate you.
Do It Step by Step
func reverseKGroup(head *ListNode, k int) *ListNode { dummy := &ListNode{Next: head}
pre := dummy end := dummy
for end.Next != nil { for i := 0; i < k && end != nil; i++ { end = end.Next } if end == nil { break }
start := pre.Next next := end.Next
end.Next = nil pre.Next = reverse(start) start.Next = next
pre = start end = pre }
return dummy.Next}
func reverse(head *ListNode) *ListNode { var pre *ListNode = nil curr := head for curr != nil { next := curr.Next curr.Next = pre pre = curr curr = next } return pre}138. Copy List with Random Pointer
Backtracking + Hash Table
func copyRandomList(head *Node) *Node { cachedNode = map[*Node]*Node{} return deepCopy(head)}
var cachedNode map[*Node]*Node
func deepCopy(node *Node) *Node { if node == nil { return nil } if n, has := cachedNode[node];has { return n } newNode := &Node{Val: node.Val} cachedNode[node] = newNode newNode.Next = deepCopy(node.Next) newNode.Random = deepCopy(node.Random) return newNode}A-A’-B-B’-C-C’
func copyRandomList(head *Node) *Node { if head == nil { return nil } for node := head; node != nil; node = node.Next.Next { node.Next = &Node{Val: node.Val, Next: node.Next} } for node := head; node != nil; node = node.Next.Next { if node.Random != nil { node.Next.Random = node.Random.Next } } headNew := head.Next for node := head; node != nil; node = node.Next { nodeNew := node.Next node.Next = node.Next.Next if nodeNew.Next != nil { nodeNew.Next = nodeNew.Next.Next } } return headNew}148. Sort List
Merge Sort
func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } slow, fast := head, head.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next }
mid := slow.Next slow.Next = nil
left := sortList(head) right := sortList(mid)
return merge(left, right)}
func merge(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} cur := dummy
for l1 != nil && l2 != nil { if l1.Val < l2.Val { cur.Next = l1 l1 = l1.Next } else { cur.Next = l2 l2 = l2.Next } cur = cur.Next }
if l1 != nil { cur.Next = l1 } if l2 != nil { cur.Next = l2 }
return dummy.Next}23. Merge k Sorted Lists
Divide and Conquer + Pairwise Merging
func mergeKLists(lists []*ListNode) *ListNode { if len(lists) == 0 { return nil } step := 1 for step < len(lists) { for i := 0; i+step < len(lists); i+= step*2 { lists[i] = mergeList(lists[i], lists[i+step]) } step *= 2 } return lists[0]
}
func mergeList(head1, head2 *ListNode) *ListNode { tmpNode := &ListNode{}
cur := tmpNode
for head1 != nil && head2!=nil { if head1.Val > head2.Val { cur.Next = head2 head2 = head2.Next } else { cur.Next = head1 head1 = head1.Next } cur = cur.Next }
if head1 != nil { cur.Next = head1 }
if head2 != nil { cur.Next = head2 }
return tmpNode.Next
}146. LRU Cache
Hash Table
type Node struct { key, value int prev, next *Node}
type LRUCache struct { size int capacity int cache map[int]*Node head, tail *Node}
func Constructor(capacity int) LRUCache { l := LRUCache{ capacity: capacity, cache: map[int]*Node{}, head: initNode(0,0), tail: initNode(0,0), } l.head.next = l.tail l.tail.prev = l.head return l}
func initNode(key, value int) *Node { return &Node{ key: key, value: value, }}
func (this *LRUCache) addToHead(node *Node) { node.prev = this.head node.next = this.head.next this.head.next.prev = node this.head.next = node}
func (this *LRUCache) removeNode(node *Node) { node.prev.next = node.next node.next.prev = node.prev}
func (this *LRUCache) moveToHead(node *Node) { this.removeNode(node) this.addToHead(node)}func (this *LRUCache) removeTail() *Node { node := this.tail.prev this.removeNode(node) return node}
func (this *LRUCache) Get(key int) int { if _, ok := this.cache[key]; !ok { return -1 } node := this.cache[key] this.moveToHead(node) return node.value}
func (this *LRUCache) Put(key int, value int) { if _, ok := this.cache[key]; !ok { node := initNode(key, value) this.cache[key] = node this.addToHead(node) this.size++ if this.size > this.capacity { removed := this.removeTail() delete(this.cache, removed.key) this.size-- } } else { node := this.cache[key] node.value = value this.moveToHead(node) }}
/** * Your LRUCache object will be instantiated and called as such: * obj := Constructor(capacity); * param_1 := obj.Get(key); * obj.Put(key,value); */Binary Trees
94. Binary Tree Inorder Traversal
Recursion
func inorderTraversal(root *TreeNode) []int { var inorder func(node *TreeNode) var ans []int inorder = func(node *TreeNode) { if node == nil { return } inorder(node.Left) ans = append(ans, node.Val) inorder(node.Right) } inorder(root) return ans}Iteration
func inorderTraversal(root *TreeNode) []int { stack := []*TreeNode{} var ans []int for root != nil || len(stack) > 0 { for root != nil { stack = append(stack, root) root = root.Left } root = stack[len(stack)-1] stack = stack[:len(stack)-1] ans = append(ans, root.Val) root = root.Right } return ans}104. Maximum Depth of Binary Tree
Recursion
func maxDepth(root *TreeNode) int { if root == nil { return 0 } return max(maxDepth(root.Left),maxDepth(root.Right)) + 1}Iteration
func maxDepth(root *TreeNode) int { if root == nil { return 0 } queue := []*TreeNode{} queue = append(queue, root) ans := 0 for len(queue) > 0 { sz := len(queue) for sz > 0 { node := queue[0] queue = queue[1:] if node.Left != nil { queue = append(queue, node.Left) } if node.Right != nil { queue = append(queue, node.Right) } sz-- } ans++ } return ans}226. Invert Binary Tree
Recursion
func invertTree(root *TreeNode) *TreeNode { if root == nil { return nil } root.Left, root.Right = root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root}101. Symmetric Tree
Recursion
func isSymmetric(root *TreeNode) bool { var isSymmetricNode func(node1 *TreeNode, node2 *TreeNode) bool isSymmetricNode = func(node1 *TreeNode, node2 *TreeNode) bool { if node1 == nil && node2 == nil { return true } if node1 == nil || node2 == nil { return false } return node1.Val == node2.Val && isSymmetricNode(node1.Left, node2.Right) && isSymmetricNode(node1.Right, node2.Left) } return isSymmetricNode(root,root)}Iteration
func isSymmetric(root *TreeNode) bool { return check(root.Left, root.Right)}
func check(p, q *TreeNode) bool { if p == nil && q == nil { return true } if p == nil || q == nil { return false } return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)}543. Diameter of Binary Tree
Maintain a Global Variable
var ans int
func diameterOfBinaryTree(root *TreeNode) int { ans = 0 depth(root) return ans}
func depth(node *TreeNode) int { if node == nil { return 0 }
left := depth(node.Left) right := depth(node.Right)
ans = max(ans, left+right) return max(left,right)+1}102. Binary Tree Level Order Traversal
Binary Tree Level Order Traversal
dfs
var ans [][]int
func levelOrder(root *TreeNode) [][]int { ans = [][]int{}
var dfs func(*TreeNode, int) dfs = func(node *TreeNode, level int) { if node == nil { return }
if level == len(ans) { ans = append(ans, []int{}) }
ans[level] = append(ans[level], node.Val)
dfs(node.Left, level+1) dfs(node.Right, level+1) }
dfs(root, 0) return ans}I’m not sure why I used DFS for this one either, but I just really like writing DFS.
bfs
func levelOrder(root *TreeNode) [][]int { ret := [][]int{} if root == nil { return ret } q := []*TreeNode{root} for i := 0; len(q) > 0; i++ { ret = append(ret, []int{}) p := []*TreeNode{} for j := 0; j < len(q); j++ { node := q[j] ret[i] = append(ret[i], node.Val) if node.Left != nil { p = append(p, node.Left) } if node.Right != nil { p = append(p, node.Right) } } q = p } return ret}108. Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree
Divide and Conquer
func sortedArrayToBST(nums []int) *TreeNode { return helper(nums, 0, len(nums)-1)}
func helper(nums []int, left, right int) *TreeNode { if left > right { return nil }
mid := (left+right+1)/2 root := &TreeNode{Val: nums[mid]} root.Left = helper(nums, left, mid -1) root.Right = helper(nums, mid+1, right) return root}98. Validate Binary Search Tree
check
func isValidBST(root *TreeNode) bool { var check func(node *TreeNode, min int64, max int64) bool
check = func(node *TreeNode, min int64, max int64) bool { if node == nil { return true }
if int64(node.Val) <= min || int64(node.Val) >= max { return false }
return check(node.Left, min, int64(node.Val)) && check(node.Right, int64(node.Val), max) }
return check(root, math.MinInt64, math.MaxInt64)}230. Kth Smallest Element in a BST
Inorder Traversal
func kthSmallest(root *TreeNode, k int) int { stack := []*TreeNode{} for { for root != nil { stack = append(stack, root) root = root.Left } stack, root = stack[:len(stack)-1], stack[len(stack)-1] k-- if k == 0 { return root.Val } root = root.Right }}