# 演算法第十二周

## 觀念題
### 第一題: Selection Problem
- 請以 prune and search 解 selection problem。
- 在以下 25 個數字中，要找出第 14 小的數。
- 25 個數字依序為：
15,18,12,10,12,4,6,14,10,1,3,5,1,5,20,3,4,10,7,5,1,15,2,4,8。
- 分組方式為：第一組為第 1 到 5 個數字，第二組為第 6 到 10 個，依此類推。
- 解法
1. 先分組(5個一組)
2. 排序
3. 每組找一個中位數
4. 找到中位數的中位數(MOM)
5. 最後分成三個集合(S1 S2 S3)
- 答案
1. 請問第一回合找到的 p 值為多少？
- 找到的p(MOM)是**5**
3. 請問第一回合，被刪去幾個數字？刪去的數字為何？
- 第一回合中刪掉了**9+3=12**個數字
- 分別是`1 1 3 1 4 3 3 2 3 5 5 5`
### 第二題: 若上題是要找第 4 小的數
- 解法
1. 先分組(5個一組)
2. 排序
3. 每組找一個中位數
4. 找到中位數的中位數(MOM)
5. 最後分成三個集合(S1 S2 S3)
- 答案
1. 請問第一回合找到的 p 值為多少？
- 找到的p(MOM)是**5**
2. 請問第一回合，被刪去幾個數字？刪去的數字為何？
- 第一回合中刪掉了**13+3=16**個數字
- 分別是`5 5 5 10 12 6 10 7 8 18 14 20 10 15 15`

### 第3題: Simplified Linear Programming with Two Variables
- 請用prune and search解Simplified Linear Programming with Two Variables。
- 6個限制條件依序為：
y≧x+1, y≧2x-4, y≧-x-3 ,y≧-2x+3, y≧4x-7, y≧-x+3
- 找滿足條件最小y值的點。(請說明步驟及計算結果)
- 解法
1. 首先先畫出限制
2. 將線兩兩一組，找出其交點(A,B,C)
3. 找到中位數=>其中位數$x_m$的鉛直線就是$X_m$
4. 找到$F(x)$，即$X_m$的全部交點的最大值點
- 這邊的例子是D點
5. 而$g_{min}$與$g_{max}$都是正號 => $X_o$在左邊
6. 因此從右邊找可以看到$X_4$與$X_3$延伸到左邊$X_3在下$ => 刪除
- 快樂圖解
<iframe src="https://www.geogebra.org/classic/ghbqm9cu?embed" width="800" height="600" allowfullscreen style="border: 1px solid #e4e4e4;border-radius: 4px;" frameborder="0"></iframe>
- 答案
1. 第一回合，每兩條件依序分組(條件1,2分一組，條件3,4分一組，依此類推)，求$𝑋_𝑚$為多少？
- 以我的圖來說$X_m$是$X=5$
2. $𝑋_𝑜$是在$𝑋_𝑚$的左或右方？
- 在左方
3. 第一回合，被刪除的條件為何？
- 使用Case 6a
- 將延伸到左總是比較小的剪枝
- 以我的例子來說可以看到$X_3$往左延伸比$X_4$小，因此$X_3$會被剪枝
## 程式題

### 第4題: 前k個常出現的單字
[leetcode 692](https://leetcode.com/problems/top-k-frequent-words/description/)
- 程式碼
:::spoiler C++

    struct node{
        int frequence;
        string str;
        node(int f, string s){
            frequence = f;
            str = s;
        }
    };
    bool operator <(node a, node b){
        if (a.frequence == b.frequence){
            return a.str>b.str;
        }
        return a.frequence < b.frequence;
    }
    class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            vector<string> res;
            unordered_map<string,int> frequce;
            for (auto word: words){
                frequce[word] += 1;
            }
            priority_queue<node> heap; 
            for (auto i: frequce){
                heap.push(node(i.second,i.first));
            }
            while (k--){
                res.push_back(heap.top().str);
                heap.pop();
            }
            return res;
        }
    };

:::
- 執行結果
- 花費時間: 30分鐘
- 完成程度: 有參考別人
- [參考amrinders433的提示](https://leetcode.com/problems/top-k-frequent-words/description/comments/1567022)
- 思路
- 首先，使用雜湊的方式算出各詞彙的存在頻率
- 接下來，使用max_heap，一個一個加入
- BTW，C++有max_heap嗎
- 其實priority_queue就是，但是預設是min_heap，所以這時候要overload 一下operator，~~超級大毒瘤徐聖凱出動~~
- 所以只要自訂資料型態就好了啊

                struct node{
                    int frequence;
                    string str;
                    node(int f, string s){
                        frequence = f;
                        str = s;
                    }
                };
                bool operator <(node a, node b){
                    if (a.frequence == b.frequence){
                        return a.str>b.str;
                    }
                    return a.frequence < b.frequence;
                }

- 最後，根據max_heap的特性，最上面的一定是最大(由我定義)，因此直接pop k個拿來用
### 第5題: 找出星狀圖的中心點
[leetcode 1791](https://leetcode.com/problems/find-center-of-star-graph/description/)
- 程式碼
:::spoiler C++

    class Solution {
    public:
        int findCenter(vector<vector<int>>& edges) {
            // fast IO
            static auto __ = []()
            {
                std::ios_base::sync_with_stdio(false);
                std::cin.tie(nullptr);
                std::cout.tie(nullptr);
                return 0;
            }();
            int node = edges.size()+1;
            unordered_map<int,int> degree;
            for (auto edge: edges){
                int u = edge[0];
                int v = edge[1];

                degree[u]++;
                degree[v]++;
            }
            for(auto i=degree.begin(); i!=degree.end(); i++){
                if (i->second == node-1) return i->first;
            }
            return -1;
        }
    };

:::
- 執行結果
- 花費時間: 30分鐘
- 完成程度: 完全靠自己(但先前被爆雷了0.0)
- 思路
- 簡單來說，就是算出度
- 但是他是無向圖，其實沒差，把邊看成雙向的就好
- 接下來直接找哪個頂點出度是頂點的總量即可

:::info
###### 補充一下無腦解法，但是你的memory會爆哈哈
~~好嘛我看到第一反應就是這個阿，我是白癡嗚嗚嗚嗚嗚嗚嗚嗚，資料結構小丑4我~~

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int node = edges.size()+1;
        vector<vector<int>> graph(node+1,vector<int>(node+1,0));
        for (auto edge: edges){
            int u = edge[0];
            int v = edge[1];

            graph[u][v] = 1;
            graph[v][u] = 1;
        }

        for (int i=1; i<=node; i++){
            int degree = 0;
            for(auto edge: graph[i]) degree+= edge;
            if (degree == node-1) return i;
        }
        return -1;
    }
};

:::
### 第6題: 用最少的箭射光氣球
[leetcode 452](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/)
- 程式碼
:::spoiler C++

    static auto __ = []()
    {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        return 0;
    }();
    class Solution {
    public:
        int findMinArrowShots(vector<vector<int>>& points) {
            sort(points.begin(), points.end(), [](vector<int> a, vector<int> b){return a[0] < b[0];});
            int arrow = 1;

            int i = 0; 
            int end = points[0][1];
            for (int i=1; i<points.size(); i++){
                int END   = points[i][1];
                int START = points[i][0];

                if (START<=end){
                    end = min(end,END);
                }
                else{
                    end = END;
                    arrow++;
                }
            }
            return arrow;
        }
    };

:::
- 執行結果
- 花費時間: 45分鐘
- 完成程度: 靠自己
- 思路
- 其實就是greedy
- 我們首先先將開始的時間排序好
- 然後接下來每次迭代判斷新的線段起點的是不是在舊的線段內，如果在代表可以一起射，不在就arrow++
- 阿但是但是怎麼判斷在線段內
- 阿開始一定會比舊的小阿，所以只要判斷，舊的線段終點是不是小於新的線段的起點

:::info
**看到開IO加速還那麼後面真的很不爽**
- 後來查一下網路是因為我的lambda函數傳入時有複製的代價，但是如果改用`const auto&` 會快非常多
:::spoiler C++

    static auto __ = []()
    {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        return 0;
    }();
    class Solution {
    public:
        int findMinArrowShots(vector<vector<int>>& points) {
            sort(points.begin(), points.end(), [](const auto & a, const auto & b){return a[0] < b[0];});
            int arrow = 1;

            int i = 0; 
            int end = points[0][1];
            for (int i=1; i<points.size(); i++){
                int END   = points[i][1];
                int START = points[i][0];

                if (points[i][0]<=end){
                    end = min(end,points[i][1]);
                }
                else{
                    end = points[i][1];
                    arrow++;
                }
            }
            return arrow;
        }
    };

:::
- 執行結果
- 直接打敗99，讚讚讚

:::

## 心得
這周學了尋刪法，感覺跟期中考看到選擇題的我很像，策略都是找一定不對就刪除。我之前似乎就有看過選擇問題的做法了，但其實就非常好奇位甚麼他排序後還可以保持O(n)，原來是排序的時間趨近常數，因此可忽略，使我大開眼界。

這周程式題的部分，感覺前兩題是資料結構會出現的東西，果然資料結構要好好學，像我就爛沒學好，還要從新複習哭哭。最後一題第一個反應就是貪心，然後就出來了我好棒棒。