演算法作業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)請問第一回合，被刪去幾個數字？刪去的數字為何？

第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組
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$

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^{\prime }=2$)

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

(A)請問第一回合找到的 p 值為多少？

(B)請問第一回合，被刪去幾個數字？刪去的數字為何？

第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$

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\geqq x+1,y\geqq 2x-4,y\geqq -x-3,y\geqq -2x+3,y\geqq 4x-7,y\geqq -x+3$

找滿足條件最小y值的點。(請說明步驟及計算結果)

第一回合

感謝GeoGebra

(A)第一回合，每兩條件依序分組(條件1,2分一組，條件3,4分一組，依此類推)，求

${𝑋}_{𝑚}$為多少？

第一組:

$y\geqq x+1,y\geqq 2x-4$

$X_1=5$

第二組:

$y\geqq -x-3,y\geqq -2x+3$

$X_2=6$

第三組:

$y\geqq 4x-7,y\geqq -x+3$

$X_3=2$

中位數是5

$X_m$是

$5$

(B)

${𝑋}_{𝑜}$是在

${𝑋}_{𝑚}$的左或右方？

碗上面的點

$P(X_m,Y_m)$
斜率為正

$X_0$在

$X_m$的左方

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

所有

$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分鐘

完成程度

完全自己解出

心得

已填