---
# System prepended metadata

title: '[AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) <br>  花花醬 Alog/DS 特輯'

---

# [AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) <br>  花花醬 Alog/DS 特輯

# SP1.  Disjoint-set/Union find Forest

- Disjoint-set/Union-find Forest

    Find(x): find the root/cluster-id of x
    Union(x, y): merge two clusters

    Check whether two elements are in the same set or not in O(1)*.

    Find: O(ɑ(n))* ≈ O(1)
    Union: O(ɑ(n))* ≈ O(1)
    Space: O(n)

    *: amortized
    ɑ(.): inverse Ackermann function

    Without optimization: Find: O(n)
    
- Two key optimizations:

    1) Path compression: make tree flat
    - 把所有partents node 都接到root上面
    ![](https://i.imgur.com/1S99my7.png)
    2) Union by rank: merge low rank tree to high rank one
    ![](https://i.imgur.com/3MPf1Sp.png)




```C++
// Author: Huahua
class UnionFindSet {
public:
    UnionFindSet(int n) {
        ranks_ = vector<int>(n + 1, 0);        
        parents_ = vector<int>(n + 1, 0);                
        
        for (int i = 0; i < parents_.size(); ++i)
            parents_[i] = i;
    }
    
    // Merge sets that contains u and v.
    // Return true if merged, false if u and v are already in one set.
    bool Union(int u, int v) {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv) return false;
        
        // Meger low rank tree into high rank tree
        if (ranks_[pv] < ranks_[pu])
            parents_[pv] = pu;           
        else if (ranks_[pu] < ranks_[pv])
            parents_[pu] = pv;
        else {
            parents_[pv] = pu;
            ranks_[pu] += 1;
        }
        
        return true;
    }
    
    // Get the root of u.
    int Find(int u) {        
        // Compress the path during traversal
        if (u != parents_[u])
            parents_[u] = Find(parents_[u]);        
        return parents_[u];
    }
private:
    vector<int> parents_;
    vector<int> ranks_;
};
```

Reference:
花花酱 LeetCode 399. Evaluate Division
花花酱 LeetCode 547. Friend Circles
```C++

```
花花酱 LeetCode 737. Sentence Similarity II
```C++

```
花花酱 LeetCode 684. Redundant Connection
```C++
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFindSet S(edges,size())

        for(const auto &edge : edges)
            if(!S.Unioin(edge[0], edge[1]))
                return edge;
                
        // Don't forget it
        return {};
    }
};


```

花花酱 LeetCode 685. Redundant Connection II
花花酱 LeetCode 839. Similar String Groups

# SP2.  Input Size and Time Complexity
![](https://i.imgur.com/9VHO8hT.png)
    < 10: O(n!) permutation
    < 15: O(2^n) combination
    < 50: O(n^4) DP
    < 200: O(n^3) DP, all pairs shortest path
    < 1,000: O(n^2) DP, all pairs, dense graph
    < 1,000,000: O(nlogn), sorting-based (greedy), heap, divide & conquer
    < 1,000,000: O(n), DP, graph traversal / topological sorting (V+E), tree traversal
    < INT_MAX: O(sqrt(n)), prime, square sum
    < INT_MAX: O(logn), binary search
    < INT_MAX: O(1) Math

# SP3.  Fenwick Tree / Binary Indexed Tree
- Array [2, 5, -1 ,3 ,6 ,7 ] , 求array中連續元素的總和
- naive implement
    - query: O(n) 很爛 就是直接算 不聰明
- DP
    - 第一次O(n) 建sum table
    - 之後query都是 O(1) : Sum(2,5) = Sum(5,0) - Sum(1,0)
    - 不能簡單update
    
- Fenwick tree was proposed to solve the prefix sum problem 
    - The idea is to store `partial sum in each node` and get total sum by travering the tree form leaf to root. The tree has height log(n)
        - Query:  O(log(n))
        - Update: O(log(n))
        - 
![](https://i.imgur.com/Qn4J5R8.png)

```C++
class FenwickTree {    
public:
    FenwickTree(int n): sums_(n + 1, 0) {}
    
    // update A[i] = delta
    void update(int i, int delta) {
        while (i < sums_.size()) {
            sums_[i] += delta;
            i += lowbit(i);
        }
    }
    
    // sum of elements from 0 to n-1
    int query(int i) const {        
        int sum = 0;
        while (i > 0) {
            sum += sums_[i];
            i -= lowbit(i);
        }
        return sum;
    }
private:
    // get low bits
    static inline int lowbit(int x) { 
        return x & (-x); 
    }
    vector<int> sums_;
};

```

307. Range Sum Query – Mutable
315. Count of Smaller Numbers After Self

# SP4.  Time/Space Complexity of Recursive Algorithms
- Master Theorem 為CS基本

## Analysis algorithm
- quick sort
 

- merge sort
    - Time Complexity
        - Best case o(nlgn)
    - Space Complexity
        - O(logn + n) : stack depth 看遞迴深度  + n(merge)
        - 要copy element 不一樣比較快

- Inorder Traversal
    - 請和quick sort比較 為何是o(n) 而不是 o(log(n))

- combination
    - binary string 不是0就是1 = 2^n -1 種組合
- permutation

- Summary
- Space Complexity : 遞迴深度

## DP with memorization
- 計劃遞歸（把結果存在memory)
- Time: 
    - (number of subproblems) * (exclusive time to slove each subproblem)
- Space:
    -  (max depth of call stack) * (space used by each subproblem)

- Fibonaci
- Cherry Pickup
- Burst Balloons

Reference:
http://zxi.mytechroad.com/blog/sp/time-space-complexity-of-recursion-functions-sp4/

# SP5.  Binary Search
Template: [l, r)
f():答案: O()
g():解在左邊還是右邊 :O(1) or O(n) or O(nlogn)

f(m) 不一定存在，如果沒有optimal 的話。
```python

"""
Returns the smallest number m such that g(m) is true.
"""
def binary_search(l, r):
  while l < r:
    m = l + (r - l) // 2
    if f(m): return m    # if m is the answer
    if g(m):
      r = m              # new range [l, m)
    else
      l = m + 1          # new range [m+1, r)
      
  return l               # or not found
```

![](https://i.imgur.com/50gzQE1.png)



- lower_bound(x) A[i] >= x
- upper_bound(x) A[i] >  x

```C++
#include <iostream>
#include <vector>
using namespace std;
 
int upper_bound(const vector<int>& A, int val, int l, int r) {
  while (l < r) {
    int m = l + (r - l) / 2;
    if (A[m] > val)
      r = m;
    else      
      l = m + 1;
  }
  return l;
}
 
int lower_bound(const vector<int>& A, int val, int l, int r) {
  while (l < r) {
    int m = l + (r - l) / 2;
    if (A[m] >= val)
      r = m;
    else
      l = m + 1;
  }
  return l;
}
 
int main() {
  vector<int> A{1, 2, 2, 2, 4, 4, 5};
  cout << lower_bound(A, 0, 0, A.size()) << endl; // 0
  cout << lower_bound(A, 2, 0, A.size()) << endl; // 1
  cout << lower_bound(A, 3, 0, A.size()) << endl; // 4
  cout << upper_bound(A, 2, 0, A.size()) << endl; // 4
  cout << upper_bound(A, 4, 0, A.size()) << endl; // 6
  cout << upper_bound(A, 5, 0, A.size()) << endl; // 7
}

```

![](https://i.imgur.com/0vfaPrP.png)
![](https://i.imgur.com/wIDKShA.png)
![](https://i.imgur.com/9ewK93q.png)



## Practices
69. Sqrt(x)
```C++

```
704. Binary Search
```C++
```
378. Kth Smallest Element in a Sorted Matrix

```C++
    int kthSmallest(vector<vector<int>>& A, int k) {
        priority_queue<int> q;
        for(auto vec:A){
            for(auto c:vec){
                q.push(c);
                if(q.size()>k)  q.pop();
            }
        }
        return q.top();
        
    }
```

:::info
#5楼 2018-02-06 21:33 DennisHCR
我不太明白后面两种解为什么返回left?left不一定是矩阵里的数字吧？还是我漏掉了什么？
支持(0) 反对(0)
   #6楼 [楼主] 2018-03-29 07:52 Grandyang
@ DennisHCR
这是个好问题，left和right最终会相等，并且会变成数组中第k小的数字。举个例子来说吧，比如数组为:
[1 2
12 100]
k = 3
那么刚开始left = 1, right = 100, mid = 50, 遍历完 cnt = 3，此时right更新为50
此时left = 1, right = 50, mid = 25, 遍历完之后 cnt = 3, 此时right更新为25
此时left = 1, right = 25, mid = 13, 遍历完之后 cnt = 3, 此时right更新为13
此时left = 1, right = 13, mid = 7, 遍历完之后 cnt = 2, 此时left更新为8
此时left = 8, right = 13, mid = 10, 遍历完之后 cnt = 2, 此时left更新为11
此时left = 11, right = 12, mid = 11, 遍历完之后 cnt = 2, 此时left更新为12
循环结束，left和right均为12，任意返回一个即可。


:::

```C++
    int l = A[0][0], r = A[A.size()-1][A.size()-1];
        while(l < r){
            unsigned int m = l + (r-l)/2;
            unsigned int total  = 0;
            for(size_t  i= 0; i<A.size(); i++){
                int c = upper_bound(A[i].begin(), A[i].end(), m) - A[i].begin();
                total += c;
                //printf("total: %u c:%u \n",total,c);
            }
            //printf("l:%u r:%u m:%u total:%u \n",l ,r ,m ,total);
            if(total >= k)
                r = m;
            else
                l = m + 1;
        }
        return l;
    
    
```
875. Koko Eating Bananas
```C++
int minEatingSpeed(vector<int>& piles, int H) {
        int l = 1;
        int r = 0;
        for(auto c: piles)
            r = max(c,r);
        
        // [l,r)
        r++;
        
        while(l<r){
            int m = l + (r-l)/2;
            int h = 0;
            
            // h: hours
            // m: eat banana each hours
            for(auto p:piles)
                h += (p + m -1)/m;
            
            //printf("m:%u h:%u \n",m,h);
            
            if(h <= H)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
```

# SP6.  200期總結與展望


# SP7.  LeetCode Amortized Analysis
![](https://i.imgur.com/lc24ed5.png)

![](https://i.imgur.com/xvELqio.png)

- 聚合分析(aggregate method) : 硬功夫累計法，決定 n 個操作序列的耗費上界 T(n)，然後計算平均耗費為 T(n) / n。
- 記帳方法(accounting method) : 銀行會計(記帳)法，確定每個操作的耗費，結合它的直接執行時間及它在對運行時中未來操作的影響。通常來說，許多短操作增量累加成"債"，而通過減少長操作的次數來「償還」。
- 勢能方法(potential method) : 類似記帳方法，但通過預先儲蓄「勢能」而在需要的時候釋放。


Reference:
[Algorithm - 平攤分析 Amortized Analysis](https://mropengate.blogspot.com/2015/06/algorithm-amortized-analysis.html)

# SP8.  Dynamic Programming I
使用條件
- Optimal substructure
- overloapping subproblem
    - 2^n(exponetial) > n^k(polynomial)
    - 如果不考慮overlap就是divde and conquer
- No after affect
    - the optimal solution of a subproblem will not change when it was used to solve a bigger problem optimally.

```shell
                大->小 (Top Down)         大->小(Bottom up)
Recursive -> recursion & Memoziation -> Dynamic Programming
                不需要考慮（找mem）           要確定會不會重複算 
```
- DP精神：要考慮如何處理overlaping 沒有的話就是單純的divide and conquer(有overlap但不鳥他)
    - DP = recursion + re-use
    - Reference: [Difference between Divide and Conquer Algo and Dynamic Programming](https://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming)

## Fibonacci sequence
## LCS : Longest common subsequence
## Knapsack problem
## Floyd warshall
## Bellman Ford
## Leetcode
- LC62  : unique path
- LC926 : Flip String to Monotone
- LC845 : Longest Mountain in Array

# SP9.  Dynamic Programming II
![](https://i.imgur.com/xy9agUd.png)

- 花花整理的題庫分類

- 一維共四種
    - (1) 最多也最複雜
    ![](https://i.imgur.com/dyPrJo4.png)
    - (2) 1 + 2 + 3 + ... n (j)
    ![](https://i.imgur.com/qWKZo9g.png)
    - (3) 輸入 O(m) + O(n), two array/strings
    ![](https://i.imgur.com/h8To56J.png)
    - (4) 其實是(3)的變形 利用K作為break points
    ![](https://i.imgur.com/dNCdmpq.png)


- ＝維共兩種
    - Input O(mn)
    ![](https://i.imgur.com/TR3k1rv.png)
    - Input O(mn) 且需要K個steps
    ![](https://i.imgur.com/7pGLd8q.png)


# SP10. 0/1 Knaspack Problem
- NP-Complete 
    - 無法在Polynomial time找到答案
    - In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NP-complete problems is often denoted by NP-C or NPC.

Reference: [NP-Complete 輕鬆談演算法的複雜度分界](https://www.ycc.idv.tw/algorithm-complexity-theory.html)

- Why Can Use DP
    - O(nw) , 總共n個item 且Weight 最重為W 
        - Weight 範圍要非常小
        - n > 20, w<10^6 
## DFS解01背包問題 
## 0/1 knaspack prolem
C[i,k] : 取道item i, 且負重還有k的時候 , 可以拿的最大Value

```C++
 static int knapSackIterative(int W, int wt[], int val[], int n)
 {
     int[][] dp = new int[n+1][W+1];
 
     
     for(int i = 0; i<=n i++) // iteim
         for(int j = 0; j<= W j++) // weight
         {
             if(i==0 || j ==0)
                 dp[i][j] = 0;
         
             if(wt[i] > j)
                 dp[i][j] = dp[i-1][j] 
             else
                 // [FIXME] Check the condition 
                 dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wt[i]] + val[i]  );
         
             
         }
 }


 public static void main(String args[]) {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 30 };
        int W = 51;
        int n = val.length;
        System.out.println(knapSackIterative(W, wt, val, n));
    }

```
## Reduce Space Complexity
- Use a tmp array
- iterator j in reverse order
 
# SP11. 0/1 Knaspack Problem
# SP12. Binary Tree
- Inorder traversal :排序好的BST
- Balanced Tree
    - For all sub tree, |TL - TR| <=1
    - 很多Tree設計都是為了BST的平衡
        - AVL Tree, Red-Black Tree ...
- Preorder traversal vs heap stack relationship
    - tree node 在heap上面是不連續的
    - [FIXME] 看懂preorder traversal 過程中 stack 與 heap的關係圖
    - 避免有忘記free的問題 自己寫tree node的destructor

- Hot to create BST(unbalanced)

## Template
- 如何用左右子樹回傳的答案 去建構最後的答案 
![](https://i.imgur.com/YDA9Ai2.png)

- one tree or two tree
![](https://i.imgur.com/Khe0UxE.png)
![](https://i.imgur.com/lvJ9hKH.png)


## find the max val of a tree
```C++
// 左子樹最大 右子樹最大 在和自己比
int maxVal(root)
{
    if(!root) return INT_MIN;

    int max_left  = maxVal(root->left); 
    int max_right = maxVal(root->right)

    return Math.max(max_left,max_right,root->data);
}

```

# SP13. Recursion unrolling and performance measurement
## Combination and Permutation
```shell
Input: nums = [1,2,3]
Output:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]
```
![](https://i.imgur.com/qY4TPyy.png)

```C++
// Author: Huahua, running time: 4 ms
class Solution {
public:
  vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> cur;
    for (int i = 0; i <= nums.size(); ++i)
      dfs(nums, i, 0, cur, ans);
    return ans;
  }
private:  
  void dfs(const vector<int>& nums, int n, int s, 
           vector<int>& cur, vector<vector<int>>& ans) {
    if (n == cur.size()) {
      ans.push_back(cur);
      return;
    }
    for (int i = s; i < nums.size(); ++i) {
      cur.push_back(nums[i]);
      dfs(nums, n, i + 1, cur, ans);
      cur.pop_back();
    }
  }
};

```
## Recursion unrolling
### Combination
![](https://i.imgur.com/RCNuorN.png)

### Permutation
![](https://i.imgur.com/7DU8oRc.png)

## Performance measurement
- Backtracking
    - same set of inputs
    - absoulte running time
    - Diffetent version of programs running on the same hardware
    - Same version of program running on different hardwares

- Profiling
    - Relative running time
    - identify the hotspots(usually a few functions)
        - one of my program spent ~ 50% on sqrt
    - Optimize those hostpots an do benchmarking again

# SP14. Segment Tree
- 也是拿來求array中連續的元素總和 和fenwick tree運用一樣 但是偏重recursive方式去建tree
    - buildTree O(n)
    - update element's value O(logn)
        - we don't need to add new node in tree, kust update the original node's value.
    - rangeQuery  O(logn + k)
        - K is number of reported segment

## Build Tree
![](https://i.imgur.com/6VTA5Hm.png)

## Update Node value
- 不要加新的點

![](https://i.imgur.com/WvCTvN5.png)

## Range Query
![](https://i.imgur.com/IN6MJqS.png)


## 307. Range Sum Query – Mutable
```C++
// Author: Huahua, running time: 24 ms
class SegmentTreeNode {
public:
  SegmentTreeNode(int start, int end, int sum,
                  SegmentTreeNode* left = nullptr,
                  SegmentTreeNode* right = nullptr): 
    start(start),
    end(end),
    sum(sum),
    left(left),
    right(right){}      
  SegmentTreeNode(const SegmentTreeNode&) = delete;
  SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;
  ~SegmentTreeNode() {
    delete left;
    delete right;
    left = right = nullptr;
  }
  
  int start;
  int end;
  int sum;
  SegmentTreeNode* left;
  SegmentTreeNode* right;
};
 
class NumArray {
public:
  NumArray(vector<int> nums) {
    nums_.swap(nums);
    if (!nums_.empty())
      root_.reset(buildTree(0, nums_.size() - 1));
  }
 
  void update(int i, int val) {
    updateTree(root_.get(), i, val);
  }
 
  int sumRange(int i, int j) {
    return sumRange(root_.get(), i, j);
  }
private:
  vector<int> nums_;
  std::unique_ptr<SegmentTreeNode> root_;
  
  SegmentTreeNode* buildTree(int start, int end) {  
    if (start == end) {      
      return new SegmentTreeNode(start, end, nums_[start]);
    }
    int mid = start + (end - start) / 2;
    auto left = buildTree(start, mid);
    auto right = buildTree(mid + 1, end);
    auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);    
    return node;
  }
  
  void updateTree(SegmentTreeNode* root, int i, int val) {
    if (root->start == i && root->end == i) {
      root->sum = val;
      return;
    }
    int mid = root->start + (root->end - root->start) / 2;
    if (i <= mid) {
      updateTree(root->left, i, val);
    } else {      
      updateTree(root->right, i, val);
    }
    root->sum = root->left->sum + root->right->sum;
  }
  
  int sumRange(SegmentTreeNode* root, int i, int j) {    
    if (i == root->start && j == root->end) {
      return root->sum;
    }
    int mid = root->start + (root->end - root->start) / 2;
    if (j <= mid) {
      return sumRange(root->left, i, j);
    } else if (i > mid) {
      return sumRange(root->right, i, j);
    } else {
      return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
    }
  }
};

```

# SP15 SP16. 如何有效率的刷題
- 總共要刷多少？  
    - 分類每題10~20 (DP越多越好)
    - 共200~300
    - total 100 hr
- 如何刷題？
    - 每週分類刷：
        - week1: Tree/Linked List
        - week2: Search
        - week3: Dynamic Programming
    - run 1 : 5 min沒方向就看答案
    - run 2 : 寫一題不可過60min
    - run 3 : 15~20寫不出來 就看答案
- RTFS, RTFS, RTFS(Read The Fucking Source Code)
    - 前75%的 Top的有可能會優化太多 會看不懂
    - 學習看不同語言
        - Algo
        - DS
        - Template
        - Optimal    
- 培養的能力
    - 這題要用哪個演算法？
    - 給你region 可以推算出Time Complexity嘛？
    - Coding Style
        - naming
        - Tab
        - 換行
        - 括號
    - 完整的手寫實現，不要copy代碼，增強肌肉記憶

# SP17. Binary Search II
g(x) is a function taht exists m such that
g(x) > 0 (True) if x >=m
g(x) <=0        else

![](https://i.imgur.com/BCnbdTG.png)

```python
def binary_search(l, r)
    while l < r
    m = l + (r-l)
    if(g(m))
        r = m         # new range :[l,m)
    else
        l = m + 1;    # new range  :[m+1, r)

    return l;        # or not found 

```
r應該設n+1， 但是會有oveflow問題，(n = 2^32 - 1)
所以設r = n，如果找不到最後在return n 即可。 
![](https://i.imgur.com/Cxb7eUj.png)
![](https://i.imgur.com/gG47hC5.png)


# SP18. Minimuum spanning tree



