Leetcode, Codility , GeekforGeeks algorithms exercises written in Golang.

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

• 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

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

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

根據定義 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

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

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

result = [] def backtrack(路徑, 選擇列表): if 滿足結束條件: result.add(路徑) return for 選擇 in 選擇列表: 做選擇(前序) backtrack(路徑, 選擇列表) 撤銷選擇(後序)

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

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

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

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

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...)

維護一個窗口, 不斷滑動

void slidingWindow(string s, string t){ unordered map<char,int>need, 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++ // 進行窗口內數據的一系列更新 // ... } } }

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

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

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

• 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<Node> q; // 核心數據結構 Set<Node> 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++ } }

分析二分搜尋技巧: 不要出現 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 ...; }

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