---
# System prepended metadata

title: Jan week3
tags: [leetcode, Daily contest]

---

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

[toc]

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

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

![](https://i.imgur.com/EVhuZO4.png)
#### 要點:
- 問 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
    ![](https://i.imgur.com/LmdrS1W.png)
- 問題: 每次都要查看每個 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 :

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


```cpp
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];
        }
    }

};
```
```cpp
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
![](https://i.imgur.com/MNKKsY6.png)


1. 初始化所有 node 各自為 set
![](https://i.imgur.com/NIgaQpB.png =250x)

2. 從 value 最小的 node 開始尋找其 neighbor，因其 neighbor value 皆比此 set 大，故無法 union
![](https://i.imgur.com/fsIuLWy.png =250x)

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


| <div style="width: 190pt"> ![](https://i.imgur.com/AlMLE9p.png) | <div style="width: 190pt"> ![](https://i.imgur.com/0LBNXbb.png ) | <div style="width: 190pt"> ![](https://i.imgur.com/Q9FBtUn.png)                     | <div style="width: 190pt">![](https://i.imgur.com/cUFk5De.png ) |
| --------------------------------------------------------------- |:---------------------------------------------------------------- | ----------------------------------------------------------------------------------- |:--------------------------------------------------------------- |
| 尋找其 neighbor                                                 | 若 neighbor的set value 較此 node set 小，將小的 union 至大的 set | 當遇到同樣的 setvalue 的 set 時計算總共可能產生的 pair 數量 (**goodpath+1x1**) | union 後，更新 set 個數                                         |

4. (value 2-2 右邊點) 
![](https://i.imgur.com/9hQsEhw.png =250x)

5. (value 3-1 左下點) union
![](https://i.imgur.com/OWAvgWC.png =250x)

6. (value 3-2 左二上方點)
    
| <div style="width: 190pt"> ![](https://i.imgur.com/uyxebCB.png) | <div style="width: 190pt">![](https://i.imgur.com/ashBLqc.png)   | <div style="width: 190pt">![](https://i.imgur.com/vFyELSV.png) |
| --------------------------------------------------------------- | ---------------------------------------------------------------- |:-------------------------------------------------------------- |
| 先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"> ![](https://i.imgur.com/W7mR5OP.png =250x) | <div style="width: 190pt">![](https://i.imgur.com/39sP0fQ.png =250x) | <div style="width: 190pt">![](https://i.imgur.com/flHekPF.png =250x) |
| --------------------------------------------------------------------- | -------------------------------------------------------------------- |:-------------------------------------------------------------------- |
|                                                                       |                  **goodpath+=3x1**                                                |     結果                                                                 |

 
9. 4號選手 union 沒有加任何的 goodpath
![](https://i.imgur.com/hHtWhxg.png =250x)![](https://i.imgur.com/89aiTcN.png =250x)

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



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

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

#### 要點
- 偵測出要 insert 的 interval 他的起始值在哪，哪裡需要置換成新的 interval，其實這題看起來不難
- 但是插入 interval 的小細節，如何 implement 有點瑣碎
    
#### 難點
- 如何偵測出 interval 之間的 overlap 跟
- 何時要插入 interval 的前端
- 何時插入 interval 的後端
- 處理起來非常之瑣碎
    
#### 解題想法
1. 簡化每次個 iteration 需要做的檢查與處你
    
- traverse 所有的 interval
    - 當 **overlap** 沒有發生:
        - 檢查是否該把 NewInterval 插入
        - 把固有的 interval 插入 result
    - 當 **overlap** 發生:
        - **update NewInterval** 
        - 不用插入舊的 interval

```cpp
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. 題目
![](https://i.imgur.com/2TCEXo2.png =500x)
2. 沒有 overlap 但 NewInterval 不在 OldInterval 之前，所以只 insert OldInterval
![](https://i.imgur.com/4crPOZ3.png =500x)
3. 有 overlap
![](https://i.imgur.com/JqUey9q.png =500x)
4. 有 overlap 更新 NewInterval
![](https://i.imgur.com/3Xk34li.png =500x)
5. 有 overlap 更新 NewInterval
![](https://i.imgur.com/k23W531.png =500x)
6. 有 overlap 更新 NewInterval
![](https://i.imgur.com/wV19ck3.png =500x)
7. 沒 overlap 且在新的 interval 之前 insert NewInterval
![](https://i.imgur.com/Eeab7f4.png =500x)
7. insert 舊的 Interval
![](https://i.imgur.com/7iXOxdC.png =500x)


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

```cpp
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 發生
![](https://i.imgur.com/oEHQegU.png)

2. 若 (len_a+len_b) < max_dix 表示 overlap 沒有發生
    
![](https://i.imgur.com/kkjYUli.png)


##### update newInterval
- 更新兩個 intervals 疊在一起後所產生新的 interval
- key point: 由於 update interval 只會發生在 overlap 情況之下
```cpp
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 找出最大與最小
![](https://i.imgur.com/2qwAtAB.png)


    
### 926. Flip String to Monotone Increasing
`1/17`  `Medium`
    
![](https://i.imgur.com/Xnl2XE8.png)
#### 要點
- 最少翻轉幾次就能達成 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 上去
    
    