Leetcode in Golang

Leetcode, Codility , GeekforGeeks algorithms exercises written in Golang.

https://kimi0230.github.io/LeetcodeGolang/

leetcode Content

• Leetcode in Golang
• leetcode Content
  • Data Structure
    • Array \& String
    • Matrix
    • Linked List
    • HashSet \& HashMap
    • Stack \& Queue
    • Heap \& Priority Queue
      • Heap 有幾個特色：
      • heap sort
    • Disjoint Set Union
    • Trie
    • Binary Indexed Tree
    • Design Data Structures
  • Algorithm
    • Greedy
    • Sort
    • Multiple Pointers
    • Backtracking (回溯法). DFS
    • DFS \& BFS
    • Dynamic Programming
    • Sliding Window
    • Sweep Line
    • Rolling Sum
    • Two Pointers
    • Bit Manipulation∂
    • Union Find
    • Breadth First Search
    • Binary Search
    • Minimax
  • Graph
    • Graph
    • Topological Sort
    • Tree
    • Tree Traversal
    • Binary Search Tree
    • Compputational Geometry
  • Selected Topics
    • Mathematics
    • Random
    • Bitwise Manipulation
• GeeksforGeeks Content
• Codility Content
• Reference

Data Structure

Array & String

Matrix

Linked List

HashSet & HashMap

Stack & Queue

Heap & Priority Queue

Heap 總是能讓整棵樹當中最大或最小值維持在root節點上

Heap 有幾個特色：

• 常見架構是像 binary tree 那樣
• 保持 balanced
• max heap 的 root 是最大值；min heap 的 root 則是最小值
• 雖然是 tree，卻很適合放在 array 中處理

heap sort

根據定義 heap 的 root 一定是最大(假設是 max heap)，也就是說，無序數列經過 heapify 再作 n 次 root deletion 取出最大值，就可以得到排序的結果。 最後就得到 heap sort 的 worst case 時間複雜度 O(nlogn) 的結果。 可是 quick sort 的 worst case 時間複雜度是 O(n²)，怎麼 quick sort 的時間複雜度比較糟糕卻比較受歡迎？ google 的結果是說 heap sort 比較不利於 caching 對於 spatial locality 機制，蠻有道理的阿。

• https://www.zhihu.com/question/23873747
• https://rust-algo.club/sorting/heapsort/index.html

Disjoint Set Union

Trie

Binary Indexed Tree

Design Data Structures

Algorithm

Greedy

Sort

Multiple Pointers

Backtracking (回溯法). DFS

DFS. 解決一個回溯問題, 實際上就是一個決策樹的遍歷過程. 算是一個暴力的窮舉算法

1. 路徑：也就是已經做出的選擇。
2. 選擇列表：也就是你當前可以做的選擇。
3. 結束條件：也就是到達決策樹底層，無法再做選擇的條件。
4. https://www.bilibili.com/video/BV1P5411N7Xc

result = []
def backtrack(路徑, 選擇列表):
    if 滿足結束條件:
        result.add(路徑)
        return

    for 選擇 in 選擇列表:
        做選擇(前序)
        backtrack(路徑, 選擇列表)
        撤銷選擇(後序)

DFS & BFS

找最短路徑用BFS, 其他時用DFS用得多一些, 因為遞迴較好寫

假設有棵滿的二叉樹,節點數為 N. 對DFS來說空間複雜度就是遞迴, 最壞的情況就是樹的高度 O(log N) BFS算法, Queue每次都會存二叉樹一層的節點, 最壞的情況下空間複雜度應該就是樹的最下層的數量, 也就是 N/2. 空間複雜度 O(N)

DFS（深度優先搜索）通常使用堆棧（Stack）來實現。在DFS中，您首先處理一個節點，然後將其子節點按某種順序推入堆棧中，接著繼續處理堆棧頂部的節點，直到堆棧為空。 BFS（廣度優先搜索）則使用隊列（Queue）來實現。在BFS中，您首先處理一個節點，然後將其子節點按某種順序排隊，接著繼續處理隊列的前端節點，直到隊列為空。

Dynamic Programming

動態規劃問題的一般形式就是求最值, 最長遞增子序列, 最小編輯距離等. 核心問題是窮舉

1. 重疊子問題
   1. memory table
   2. DP table
2. 最優子結構
3. 狀態轉移方程式
   1. 這問題的 base case (最簡單情況) 是什麼?
   2. 這問題有什麼狀態
   3. 對於每個狀態, 可以做出什麼選擇, 使得狀態發生改變
   4. 如何定義 dp 數組/函數的含義來表現狀態和選擇?

# 初始化 base case
dp[0][0][...] = base
# 進行狀態轉移
for 狀態1 in 狀態1的所有取值：
    for 狀態2 in 狀態2的所有取值：
        for ...
            dp[狀態1][狀態2][...] = 求最值(選擇1，選擇2...)

Sliding Window

維護一個窗口, 不斷滑動

void slidingWindow(string s, string t){
    unordered mapneed, window;
    for (char c:t) need[c++]
    int left = 0 , right = 0
    int valid = 0

    // 先移動 right 再移動 left. 直到right到達 string的末端
    while(right < s.size()){
        // c是將移入窗口的字符
        char c = s[right]
        // 右移窗口 
        right++
        // 進行窗口內數據的一系列更新
        // ...

        /*** 用來debug 輸出位置 ***/
        printf("window: [%d, %d)\n",left,right)
        /************************/

        // 判斷左側窗口是否收縮
        while(window needs shrink){
           // d是將移出窗口的字符
           // 左移窗口 
            left++
            // 進行窗口內數據的一系列更新
            // ...
        }
    }
}

Sweep Line

Rolling Sum

Two Pointers

只要array有序, 就應該想到雙指針技巧 分為兩類 1. "快,慢指針" 2. "左,右指針"

1. 快,慢指針: 主要解決 linkedlist 問題, 典型的判斷 linkedlist 是否包含環
2. 左,右指針: 主要解決array(或 string)中的問題, 如二分搜尋.

https://labuladong.gitee.io/algo/2/21/57/

Bit Manipulation∂

Union Find

Breadth First Search

• DFS 算法可以被認為是回溯算法, BFS算法都是用Queue這種數據結構, 每次將一個截短周圍的所有節點加入Queue.
• BFS 找到的路徑一定是最短的, 但是代價是空間複雜度比DFS大. BFS vs DFS
• 優化: 雙向 BFS 優化, 在 while 開始時做一個判斷. 讓每次都選擇較小的集合進行擴散, 那麼佔用的空間增長速度就會慢一些, 盡可能以最小的空間代價產生 curDepth 和 nextDepth 的交集 無論單向的 BFS 或是 雙向BFS, 優化過的BFS 空間複雜度都是一樣的

// 計算從起點 start 到 終點 target 的最點距離
int BFS(Node start, Node targe){
    Queue q; // 核心數據結構
    Set visited; // 避免走回頭路

    q.offer(start); // 將起點加入 Queue
    visited.add(start);
    int step = 0; // 紀錄擴散的步數

    while(q not empty) {
        int sz = q.size();
        // 當前 Queue 中的所有節點向四周擴散
        for (int i = 0 ; i < sz; i++) {
            Node cur = q.poll();
            // 這裡判斷是否到達終點
            if (cur is target) {
                return step;
            }

            // 將cur 的相鄰節點加入 Queue
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        // 在這裡更新步數
        step++
    }
}

Binary Search

分析二分搜尋技巧: 不要出現 else, 而是把所有情況用 else if 寫清楚. 計算 mid 時需要防止溢出

int binarySearch(int[] nums, int target){
    int left = 0 , right = ...;
    while(...) {
        int mid = left + (right - left)/2
        if (nums[mid] == target){
            ...
        } else if (nums[mid] < target){
            left = ...
        } else if (nums[mid] > target){
            right = ...
        }
    }
    return ...;
}

將搜尋區間全部統一成兩端都閉, 方便記憶 [letf,right]

func Search(nums []int, target int) int {
    lenght := len(nums)
    if lenght <= 0="" 1="" {="" return="" -1="" }="" left,="" right="" :="0," lenght-1="" for="" left="" <="right" mid="" +="" if="" nums[mid]="=" target="" else="" 找右邊=""> target {
            // 找左邊
            right = mid - 1
        }
    }
    // 都沒找到
    return -1
}

// 有點類似 nums 小於 target的元素有幾個
func LeftBound(nums []int, target int) (index int) {
    lenght := len(nums)
    if lenght <= 0="" {="" return="" -1="" }="" left,="" right="" :="0," lenght-1="" for="" left="" <="right" 除以2="" mid="" +="" (right-left)="">>1
        mid := int(uint(right+left) >> 1)
        if nums[mid] == target {
            // 要繼續找左邊, 所以把右邊變小
            right = mid - 1
        } else if nums[mid] < target {
            // 找右邊
            left = mid + 1
        } else if nums[mid] > target {
            // 找左邊
            right = mid - 1
        }
    }
    // 都沒找到 注意: left越界情況
    if left >= lenght || nums[left] != target {
        return -1
    }
    return left
}

// 有點類似 nums 大於 target的元素有幾個
func RightBound(nums []int, target int) (index int) {
    lenght := len(nums)
    if lenght <= 0="" {="" return="" -1="" }="" left,="" right="" :="0," lenght-1="" for="" left="" <="right" 除以2="" mid="" +="" (right-left)="">>1
        mid := int(uint(right+left) >> 1)
        if nums[mid] == target {
            // 注意:要繼續找右邊, 所以把左邊變大=mid+1
            left = mid + 1
        } else if nums[mid] < target {
            // 找右邊
            left = mid + 1
        } else if nums[mid] > target {
            // 找左邊
            right = mid - 1
        }
    }
    // 都沒找到 注意:right越界情況
    if right < 0 || nums[right] != target {
        return -1
    }
    return right
}

for left ：

• 此方法在迭代終止時，left 和 right 指針指向同一個位置。
• 此方法會包括最後一個可能的候選解，在某些情況下可能更容易理解和實現。
• 在應對邊界情況時可能更為方便，例如當 left 和 right 指向同一位置時，這時可能需要進一步處理。

for left < right {}：

• 此方法在迭代終止時，left 和 right 指針指向相鄰位置。
• 此方法會排除最後一個可能的候選解，當要求嚴格小於或大於某個值時可能更合適。

• 在一些情況下，可能會更高效，因為在每次循環中只需要比較一次 left 和 right，而不需要再處理當兩者相等時的情況。

  func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
  
    for left < right {
        mid := int(uint(right+left)>>1)
        if nums[mid]==target{
            return mid
        }else if (nums[mid]

Minimax

Graph

Graph

Topological Sort

Tree

Tree Traversal

Binary Search Tree

Compputational Geometry

Selected Topics

Mathematics

Random

Bitwise Manipulation

GeeksforGeeks Content

Codility Content

Reference

• leetcode
• leetcode-cn
• halfrost
• anakin
• wufenggirl
• GeeksforGeeks
• Codility
• GitHub: labuladong/fucking-algorithm(labuladong 算法小抄)
• https://cses.fi/
• https://github.com/neetcode-gh/leetcode