# 演算法作業11

## 第1題: 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 個，依此類推。
### (A)請問第一回合找到的 p 值為多少？
### (B)請問第一回合，被刪去幾個數字？刪去的數字為何？

:::success

| 第1組 | 第2組 | 第3組 | 第4組 | 第5組 |
| ----- | ----- | ----- | ----- | ----- |
| 15 | 4 | 3 | 3 | 1 |
| 18 | 6 | 5 | 4 | 15 |
| 12 | 14 | 1 | 10 | 2 |
| 10 | 10 | 5 | 7 | 4 |
| 12 | 1 | 20 | 5 | 8 |

:::

:::success

| 第1組 | 第2組 | 第3組 | 第4組 | 第5組 |
| ------ | ----- | ----- | ----- | ----- |
| 15 | 4 | 3 | 3 | 1 |
| 18 | **6** | **5** | 4 | 15 |
| **12** | 14 | 1 | 10 | 2 |
| 10 | 10 | 5 | 7 | **4** |
| 12 | 1 | 20 | **5** | 8 |

| 第1組 | 第2組 | 第3組 | 第4組 | 第5組 |
| ------ | ----- | ----- | ----- | ----- |
| **12** | **6** | **5** | **5** | **4** |

### (A) $P:5$

:::

:::success

### S1 有9個
| S1 |
| --- |
| 1 |
| 1 |
| 1 |
| 2 |
| 3 |
| 3 |
| 4 |
| 4 |
| 4 |

### S2 有3個

| S2 |
| --- |
| 5 |
| 5 |
| 5 |

### S3 有13個

| S3 |
| --- |
| 6 |
| 7 |
| 8 |
| 10 |
| 10 |
| 10 |
| 12 |
| 12 |
| 14 |
| 15 |
| 15 |
| 18 |
| 20 |

### (B) 刪掉12個
刪掉的是S1+S2 共9+3 12個

| S1 |
| --- |
| 1 |
| 1 |
| 1 |
| 2 |
| 3 |
| 3 |
| 4 |
| 4 |
| 4 |

| S2 |
| --- |
| 5 |
| 5 |
| 5 |

($k'=2$)
:::

## 第2題：若上題是要找第 4 小的數

### (A)請問第一回合找到的 p 值為多少？
### (B)請問第一回合，被刪去幾個數字？刪去的數字為何？

:::success

| 第1組 | 第2組 | 第3組 | 第4組 | 第5組 |
| ------ | ----- | ----- | ----- | ----- |
| 15 | 4 | 3 | 3 | 1 |
| 18 | **6** | **5** | 4 | 15 |
| **12** | 14 | 1 | 10 | 2 |
| 10 | 10 | 5 | 7 | **4** |
| 12 | 1 | 20 | **5** | 8 |

| 第1組 | 第2組 | 第3組 | 第4組 | 第5組 |
| ------ | ----- | ----- | ----- | ----- |
| **12** | **6** | **5** | **5** | **4** |

### (A) 一樣是 $P:5$

:::

:::success
### S1 有9個
| S1 |
| --- |
| 1 |
| 1 |
| 1 |
| 2 |
| 3 |
| 3 |
| 4 |
| 4 |
| 4 |

### S2 有3個

| S2 |
| --- |
| 5 |
| 5 |
| 5 |

### S3 有13個

| S3 |
| --- |
| 6 |
| 7 |
| 8 |
| 10 |
| 10 |
| 10 |
| 12 |
| 12 |
| 14 |
| 15 |
| 15 |
| 18 |
| 20 |

### (B) 刪掉16個
刪掉的是S2+S3 共3+13 16個

| S2 |
| --- |
| 5 |
| 5 |
| 5 |

| S3 |
| --- |
| 6 |
| 7 |
| 8 |
| 10 |
| 10 |
| 10 |
| 12 |
| 12 |
| 14 |
| 15 |
| 15 |
| 18 |
| 20 |

:::

## 第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值的點。(請說明步驟及計算結果)

:::info
第一回合

感謝GeoGebra

:::

### (A)第一回合，每兩條件依序分組(條件1,2分一組，條件3,4分一組，依此類推)，求$𝑋_𝑚$為多少？

:::success

#### 第一組:
$y≧x+1, y≧2x-4$
$X_1=5$

#### 第二組:
$y≧-x-3 ,y≧-2x+3$
$X_2=6$

#### 第三組:
$y≧4x-7, y≧-x+3$
$X_3=2$

中位數是5
### $X_m$是$5$

:::

### (B)$𝑋_𝑜$是在$𝑋_𝑚$的左或右方？

:::success


碗上面的點$P(X_m,Y_m)$
斜率為正
$X_0$在$X_m$的左方

:::

### (C ) 第一回合，被刪除的條件為何？

:::success
所有$X_i$值比$X_m$大的，刪掉在同$X=X_m$的情況下，在下面的那條。
:::

## 第4題: 前k個常出現的單字

### 解題思路

丟進map給他記錄次數
排序後提出前K個
回傳答案

### 程式碼

class Solution {
public:
    static bool cmp(pair<string,int> &a, pair<string,int> &b)
    {
        if(a.second==b.second)
        {
            return a.first<b.first;
        }
        return a.second>b.second;
    }
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> m;
        for(auto p:words)
        {
            m[p]++;
        }
        vector<pair<string,int> > v;
        for(auto p:m)
        {
            v.push_back(p);
        }
        sort(v.begin(),v.end(),cmp);
        vector<string> ans;
        for(int i=0;i<k;i++)
        {
            ans.push_back(v[i].first);
        }
        return ans;
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

14分鐘

### 完成程度

完全自己解出

## 第5題: 找出星狀圖的中心點

### 解題思路

~~好水~~
就是比對第一個第二個的哪個一樣
直接回傳就好

### 程式碼

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        return (edges[0][0]==edges[1][0]||edges[0][0]==edges[1][1])?edges[0][0]:edges[0][1];
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

3分鐘

### 完成程度

完全自己解出

## 第6題: 用最少的箭射光氣球

### 解題思路

~~我不小心寫過了~~
簡單來說就是把左右邊排好
從起始點小的開始排
結束值不重要，反正跑的過程會把當中最小的取出來
如果當下這顆氣球的左邊`points[i][0]`超過了右界的值`r`
就換下一顆子彈射
而右界會越來越小(或不變)
大概是這樣的想法

順帶一提
如果cmp是用&(參照)可以節省很多時間
因為每次cmp是需要把vector複製一次再傳過去的
如果用參照就不用花那個時間了

### 程式碼

class Solution {
public:

    static bool cmp(vector<int> &a,vector<int> &b)
    {
        return a[0]<b[0];
    }
    
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int i,r=points[0][1],ans=1;
        for(i=1;i<points.size();i++)
        {
            if(points[i][0]>r)
            {
                ans++;
                r=points[i][1];
            }
            else
            {
                r=min(r,points[i][1]);
            }
        }
        return ans;
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

10分鐘

### 完成程度

完全自己解出

## 心得

已填