###### tags: `演算法作業`
# 演算法作業 HW01
## 觀念題
### 1.本週影片中提到的NP-complete問題有哪些？
- 0/1 Knapsack problem
- traveling salesperson problem
- partition problem
- art gallery problem
### 2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。
- Job sequencing
- 設一計算機有許多方案，每個方案有兩個屬性，一個是完成方案所需的時間t，另一個是方案的權重w(優先級)，時間與權重都用正整數定義。要求設計一種完成任務的先後順序，使得所有任務代權完成時間之和最小。
(任務代權完成時間 = 任務權重w * 任務完成時的時間(包含等待時間) )
輸入 : 方案數量,各個方案的權重所需時間。
輸出 : 完成任務的先後順序。

- Ans : 兩種順序方案
1. T1,T2 : 5*2+(5+3)*1 = 18
2. T2,T1 : 3*1+(3+5)*2 = 19 所以選擇方案2. T2,T1
## 程式題(二元搜尋(Binary Search)應用)
### 3. 二元搜尋應用：當數字可以重覆
- 程式碼 :

#include<iostream>
#include<vector>
#include<sstream>
using namespace std;
    
int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size()-1;
    int mid =0;
    while(left < right){
        mid = left + (right-left)/2;
        if(nums[mid] >= target){
            right = mid;
        }else{
            left = mid +1;
        }
    }
    if(nums[left] == target){
        return left;
    }else{
        return -1;
    }
}
int main()
{
    int num,target;
    vector<int> nums;
    string line;

    while(1){
        getline(cin,line);
        istringstream iss(line);
        while( iss>>num ){
            nums.push_back(num);
        }
        cin>>target;
        cin.get();
        cout<<search(nums,target)<<endl<<endl;
        nums.clear();
    }
    return 0;
}

- 測試輸出輸入的畫面 :

- 花費的時間 : 1小時
- 完成的程度 : 完全靠自己(main 靠Google研究)
- 解題思路 :
- 當找到Target的時候不能確定是不是最小index，此時找到的值要保存下來，繼續往左邊尋找是否還有更小的index。
- 跳出迴圈後要確認是找到最小index還是找不到Target。
### 4. 二元搜尋應用：找數字該插入的位置(LeetCode 35)
- 程式碼 :

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

- 測試輸出輸入的畫面 : 

- 花費的時間 : 30分
- 完成的程度 : 完全靠自己
- 解題思路 :
- 當找不到Target時，最後left和right都會落在同一個位置。
- 當此位置"大於"Target，表示Target要插入此位置，此時left不變。
- 當此位置"小於"Target，表示Target要插入此位置+1，此時left+1。
- 所以最後return left。
### 5. 二元搜尋應用：找到最早出問題的版本(LeetCode 278)
- 程式碼 :

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        int mid = 1;
        while(left < right){
            mid =left + (right-left) / 2; //(left + right)/2 -> overflow
            if( isBadVersion(mid) ){
                right = mid;
            }else{
                left = mid +1; 
            }
        }
        return right;
    }
};

- 測試輸出輸入的畫面 : 

- 花費的時間 : 30分
- 完成的程度 : 完全靠自己
- 解題思路 :
- 當遇到isBadVerdion()是true，此時找到的不一定是最先錯誤的，此時找到的值要保存下來，繼續往左邊尋找是否還有更早的錯誤版本。
### 6. 二元搜尋應用：開根號後的整數部分(LeetCode 69)
- 程式碼 :

#include<iostream>
#include<vector>
using namespace std;
int sqrt(int );

int main()
{
    int num;
    while(cin>>num){
        cout<<sqrt(num)<<endl<<endl;;
    }
    return 0;
}
int sqrt(int x)
{
    int left = 0,right = x;
    int mid = 0;
    if(x <= 1 ){
        return x;
    }
    while(left < right){
        mid = left + (right-left)/2;
        if(mid*mid > x){
            right = mid;
        }else if(mid*mid < x){
            left = mid +1;
        }else{
            return mid;
        }
    }
    return right-1;
}

- 測試輸出輸入的畫面 :

- 後來發現是leetcode69 補上

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int mid = 0 ;
        if(x <= 1){
            return x;
        }
        while(left < right){
            mid = left + (right-left)/2;
            //mid * mid ->overflow
            if( mid > x/mid ){
                right = mid ;
            }else if( mid < x/mid ){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return left-1;
    }
};


- 花費的時間 : 30分
- 完成的程度 : 完全靠自己
- 解題思路 :
- 當數值剛好是某數的平方，會直接return 。
- 當最終找不到準確某數的平方，left和right會正好停在"上取整數(根號Target)"。
- 所以最後要left-1或right-1。
## 心得
### 7. 本週心得
老師講解完整且說明易理解，聲音部分有點小聲，但還是能夠聽清。
作業可以盡量給leetcode嗎? 不能完全確定自己寫的對不對，而且作業有點多。