# **演算法作業 HW1**
<font size=5>**1. 本週影片中提到的NP-complete問題有哪些？**</font>
---
* Knapsack problem
* Traveling salesperson problem
* Partition problem
* Art gallery problem

<font size=5>**2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。**</font>
---
圖著色問題(Graph Coloring Problem)
* 定義：給定一個無向圖 **G = ( V , E )**，其中 **V** 為頂點集合，**E** 為邊集合，圖著色問題即為將 **V** 分為 **K** 個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。優化版本是希望獲得最小的 **K** 值。
* 舉例：
下圖是一個無向圖，用 **K** 個顏色將所有頂點上色，且相鄰點顏色不可相同，求最小值 **K** 。
經過計算，可以得出下圖其中一種可能，最小值 **K** 為 3。

<font size=5>**3. 二元搜尋應用：當數字可以重覆**</font>
---
數字可能重複，回傳找到最小index。
只要找到後不停止，繼續往左區間找就好了。
完全靠自己，花費時間：1分鐘。

#include<iostream>
#include<vector>
#include<sstream>
using namespace std;
//數字重複，回傳找到最小index
int binary_search(vector<int>nums,int target)
{
    int l=0,r=nums.size()-1,mid,ans=-1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(nums[mid]==target)//找到跟target相同的數
        {
            ans=mid;
            r=mid-1;//即使找到也繼續往左區間尋找
        }
        else if(nums[mid]>target)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return ans;
}
int main()
{
    vector<int>nums;
    string s;
    int num,t;
    
    cout<<"輸入數列：";
    getline(cin,s);
    stringstream s1;
    s1<<s;
    while(s1>>num)
    {
        nums.push_back(num);
    }
        
    cout<<"輸入要尋找的數：";
    cin>>t;
    
    cout<<binary_search(nums,t)<<endl;
    
    return 0;
}

執行結果：

<font size=5>**4. 二元搜尋應用：找數字該插入的位置**</font>
---
[35. Search Insert Position - LeetCode](https://leetcode.com/problems/search-insert-position/)
若找不到數字則回傳應該插入的位置。
如果while迴圈跑到最後還是找不到，直接回傳左邊界的index即可。
完全靠自己，花費時間：一分鐘。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(nums[mid]==target)
            {
                return mid;
            }
            else if(nums[mid]>target)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l;
    }
};


<font size=5>**5. 二元搜尋應用：找到最早出問題的版本**</font>
---
[278. First Bad Version - LeetCode](https://leetcode.com/problems/first-bad-version/)
這題只是第三題的變體而已，同樣是找到後繼續往左區間找。
要注意的是用int會爆。
完全靠自己，花費時間：一分鐘。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        long l=1,mid,ans;
        while(l<=n)
        {
            mid=(l+n)/2;
            if(isBadVersion(mid))
            {
                ans=mid;
                n=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return ans;
    }
};


<font size=5>**6. 二元搜尋應用：開根號後的整數部分**</font>
---
[69. Sqrt(x) - LeetCode](https://leetcode.com/problems/sqrtx/)
把x當右邊界r用二分搜下去找，找不到就回傳r。
一樣要注意用int會爆。
完全靠自己，完成時間：一分鐘。

class Solution {
public:
    int mySqrt(int x) {
        long l=1,r=x,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(mid*mid==x)
            {
                return mid;
            }
            else if(mid*mid>x)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return r;
    }
};


<font size=5>**7. 本週心得**</font>
---
有些題目因為做過了所以做蠻快的，還可以跟上，影片方面也沒什麼問題。

---
若有錯誤歡迎指正