###### tags: `leetcode` `Daily contest`

[toc]

# Jan week3
- 1/15 ~ 1/21
### 2421. Number of Good Paths
`1/15` `Hard`


#### 要點:
- 問 tree 中所有的 GoodPaths 的數量
def(GoodPath) : 頭尾 node value 一樣，且頭尾所經過的 node 其 value 皆 <= 頭尾 value
#### 難點:
- 直觀想法(**TLE**)：
- 定義 subtree:
- return 值為 hash table
- 此 hash table 紀錄的東西為
- key : node value
- value : 紀錄有多少合法的 PATH 其起始 node value 為 key 的 path 能走到此點
- 另外每次都要 traverse 所有 child，紀錄each child 之間經過此 node 可產生多少條 goodpaths
- 問題: 每次都要查看每個 childnode 的table，假設每個每個 node 的 value 都不一樣，這樣childnode table size = n ，此演算法時間複雜度 O(n^2)

#### 解題想法:
** 當出現這種 Tree 的題目:若 root 可以隨意置換 則可能有其他的解法 (e.g. n號node拿來當tree root，其goodpaths數量不變(n屬於0~node.size)) **

- key point :

1. 如上圖。今有一 value 很大的 node L，因為不可能存在任何 goodpaths 其經過此 node，這時我們就可把問題(tree) 分解成較小的 subtree 來處理 (灰色)
2. 又從樹中找最大值，其至少要用 dfs 跑一次，所以利用 back propagation 概念 (bottom up)，依序找到值最小的 node，慢慢 union 成大一點的樹。這個動作其實就等同先建造灰色的 subtree，再去include 大 value 的點成新的 subtree
3. Union and Find

class union_set{
public:
    vector<int> setparent;
    vector<int> weight;
    int goods;
public:
    union_set(int size){
        goods=0;
        weight.resize(size, 1);
        setparent.resize(size, 0);
        for(int i=0;i<size;i++){
            setparent[i] = i;
        }
    }
    int find(int node){ // compression
        if(setparent[node] != node) setparent[node] = find(setparent[node]);
        return setparent[node];
    }
    void union_ab(int a, int b, vector<int>& vals){
        int seta = find(a);
        int setb = find(b);
        if(seta == setb) return; // in the same set
        if(vals[seta] > vals[setb]){ // union to big set parent
            setparent[setb] = seta;
        }else if(vals[seta] < vals[setb]){ // union to big set parent
            setparent[seta] = setb;
        }else{
            setparent[setb] = seta;
            goods += weight[seta]*weight[setb];
            weight[seta] += weight[setb];
        }
    }

};

class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        vector<vector<int>> adjlist(vals.size());
        for(auto &e : edges){
            adjlist[e[0]].push_back(e[1]);
            adjlist[e[1]].push_back(e[0]);
        }
        union_set us(vals.size());

        map<int, vector<int>> table;
        for(int i=0;i<vals.size();i++){
            table[vals[i]].push_back(i);
        }
        
        
        for(auto& [value, nodes] : table){ // first loop : 拿出所有 value 為 x 的 nodes;
            for(int& nodeidx : nodes){ // second loop : 所有 value 為 x 的 nodes 一個一個拿出來測試
                for(int& adjchild : adjlist[nodeidx]){ // 查看此 node 的 neighbor
                    if(vals[nodeidx] >= vals[adjchild]){ // 如果 此 node value 大於 neighbor 的 value 則 union
                        us.union_ab(nodeidx, adjchild, vals);
                    }
                }
            }
        }
        return us.goods + vals.size();
    }
};

e.g.
問:此 tree 的 GoodPaths

1. 初始化所有 node 各自為 set

2. 從 value 最小的 node 開始尋找其 neighbor，因其 neighbor value 皆比此 set 大，故無法 union

3. (value 2-1) 尋找其 neighbor，若 neighbor的set value 較此 node set 小，將小的 union 至大的 set

| <div style="width: 190pt">  | <div style="width: 190pt">  | <div style="width: 190pt">  | <div style="width: 190pt"> |
| --------------------------------------------------------------- |:---------------------------------------------------------------- | ----------------------------------------------------------------------------------- |:--------------------------------------------------------------- |
| 尋找其 neighbor | 若 neighbor的set value 較此 node set 小，將小的 union 至大的 set | 當遇到同樣的 setvalue 的 set 時計算總共可能產生的 pair 數量 (**goodpath+1x1**) | union 後，更新 set 個數 |

4. (value 2-2 右邊點)

5. (value 3-1 左下點) union

6. (value 3-2 左二上方點)

| <div style="width: 190pt">  | <div style="width: 190pt"> | <div style="width: 190pt"> |
| --------------------------------------------------------------- | ---------------------------------------------------------------- |:-------------------------------------------------------------- |
| 先union下方同 value set **goodpaths+1x1** | 左邊setvalue小於等於此setvalue，也可進行 union **goodpaths+2x1** | 最後union後的結果 |
7. (value 3-3 (左二下方)已經在同個set了不需要 union)
8. (value 3-4 與左方進行 union)

| <div style="width: 190pt">  | <div style="width: 190pt"> | <div style="width: 190pt"> |
| --------------------------------------------------------------------- | -------------------------------------------------------------------- |:-------------------------------------------------------------------- |
| | **goodpath+=3x1** | 結果 |

9. 4號選手 union 沒有加任何的 goodpath

所以此題 goodpath 為 7+9 = 16 (題目定義 node 本身也算是一條 goodpath)

### 57. Insert Interval
`1/16` `Medium`


#### 要點
- 偵測出要 insert 的 interval 他的起始值在哪，哪裡需要置換成新的 interval，其實這題看起來不難
- 但是插入 interval 的小細節，如何 implement 有點瑣碎

#### 難點
- 如何偵測出 interval 之間的 overlap 跟
- 何時要插入 interval 的前端
- 何時插入 interval 的後端
- 處理起來非常之瑣碎

#### 解題想法
1. 簡化每次個 iteration 需要做的檢查與處你

- traverse 所有的 interval
- 當 **overlap** 沒有發生:
- 檢查是否該把 NewInterval 插入
- 把固有的 interval 插入 result
- 當 **overlap** 發生:
- **update NewInterval**
- 不用插入舊的 interval

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int n = intervals.size();
    vector<vector<int>> answer;
    bool interval_insert = false; //newinterval 還沒插入過
    for(int i=0;i<n;i++){
        if(!overlap(intervals[i], newInterval)){
            if(!interval_insert && newInterval[1] < intervals[i][0]){
                answer.push_back(newInterval);
                interval_insert = true; //newinterval 插入過了
            }
            answer.push_back(intervals[i]);
        }else{
            newInterval = update_interval(newInterval, intervals[i]);
        }
    }
    if(!interval_insert) answer.push_back(newInterval); //newinterval 只會插入一次
    return answer;
}

圖例:
1. 題目
2. 沒有 overlap 但 NewInterval 不在 OldInterval 之前，所以只 insert OldInterval
3. 有 overlap
4. 有 overlap 更新 NewInterval
5. 有 overlap 更新 NewInterval
6. 有 overlap 更新 NewInterval
7. 沒 overlap 且在新的 interval 之前 insert NewInterval
7. insert 舊的 Interval

##### overlap detect
- 偵測兩個 interval 是否 overlap
- key point: (overlap 之長度差異)

bool overlap(vector<int>& a, vector<int>& b){
    int sum = (a[1]-a[0]) + (b[1]-b[0]);
    int range = max((b[1]-a[0]), (a[1]-b[0]));
    return range > sum ? false : true;
}

1. 定義 **len_a** 與 **len_b** : a, b 兩 intervals 長度
2. 定義 **max_dis** : 為 a, b 兩 interval 距離最遠的兩點可產生的最大距離

By 上面參數
1. 若 (len_a+len_b) >= max_dix 表示 overlap 發生

2. 若 (len_a+len_b) < max_dix 表示 overlap 沒有發生


##### update newInterval
- 更新兩個 intervals 疊在一起後所產生新的 interval
- key point: 由於 update interval 只會發生在 overlap 情況之下

vector<int> update_interval(vector<int>& oldinterval, vector<int>& overlap){
    vector<int> newinterval(2);
    newinterval[0] = min(oldinterval[0], overlap[0]);
    newinterval[1] = max(oldinterval[1], overlap[1]);
    return newinterval;
}

1. 可利用 min & max 找出最大與最小

### 926. Flip String to Monotone Increasing
`1/17` `Medium`

#### 要點
- 最少翻轉幾次就能達成 monotone increasing (遞增)

#### 難點
- 窮舉無敵! 也可從 bit operation 的想法去想幫助理解

#### 解題想法
1. 先計算把全部都翻成 1 需要多少次 flip (s中0的個數)
2. 接下來依序測試 monotone increasing 的每種可能
3. 計算最少的次數

e.g.
- 010110 最少需要 filp 幾次

1. 翻成 111111 需要 **3** 次 (0的個數)
2. bit operation (xor) 想法

| | | | | | | | |
|:---------- |:------ | ------ |:------ | ------ |:------ |:------ |:------ |
| | 010110 | 010110 | 010110 | 010110 | 010110 | 010110 | 010110 |
| **xor** | 000000 | 100000 | 110000 | 111000 | 111100 | 111110 | 111111 |
| **Flip** | 101001 | 001001 | 011001 | 010001 | 010101 | 010111 | 010110 |
| **Count** | 3 | 2 | 3 | 2 | 3 | 4 | 3 |
| **Target** | 111111 | 011111 | 001111 | 000111 | 000011 | 000001 | 000000 |

*上面 Result中為1的地方代表要 flip的地方*
*Count 代表總共 Flip的次數*
*下面 Target則代表 flip後的結果 (monotone increasing)*

3. 計算翻成全 1 要翻幾次後，
用 for loop 再跑一次即可知道最少 flip 次數，
所以當:
- 看到 0 需要把它 -1 回去
- 看到 1 需要把它 +1 上去