# 演算法作業HW1
## 觀念題
### 1. 本週影片中提到的NP-complete問題有哪些？
1. 0/1 knapsack problem (背包問題)
2. Traveling salesperson problem (旅行推銷員問題)
3. Partition problem (分區問題)
4. Art gallery problem (美術館問題)

---
### 2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。
- Clique problem(分團問題)
- 分團問題是問一個圖中是否有大小是k以上的團。任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個團。如下圖的1、2、5即為最大的團。
- input：下圖
- output：3

---
## 程式題：二元搜尋(Binary Search)應用
### 3. 二元搜尋應用：當數字可以重覆
- 題目：在排序好的數列中，其中數字有可能重覆，請修改原程式，可以回傳==最小的index值==。
- **解題思路**：多設一個變數"goal = -1"存放目標index值，使搜尋繼續往左，若無則回傳-1。
- **code**：

def search(nums, target):
    left = 0
    goal = -1
    right = len(nums) - 1
    while left <= right:
        mid = (right + left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            goal = mid
            right = mid - 1
    return goal


data1 = [1, 3, 3, 6]
data2 = [1, 2, 3, 6, 6, 6, 7, 8, 9]
print(search(data1, 3))
print(search(data1, 2))
print(search(data1, 6))

- **output**：
花費時間：25分鐘
完成程度：自己想的

---
### 4. 二元搜尋應用：找數字該插入的位置
- [Leetcode 35](https://leetcode.com/problems/search-insert-position/description/)
- **解題思路**：把找不到的數字插入指標left在的位置。
- **code** ：

class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (right + left)//2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return left

花費時間：15分鐘
完成程度：自己想的

---
### 5. 二元搜尋應用：找到最早出問題的版本
- [Leetcode 278](https://leetcode.com/problems/first-bad-version/)
- **解題思路**：其實就是找ex:0,0,0,1,1,1,1的第一個1，跟第三題找重複數字的第一個字類似，只是換成布林值而已。
- **code**：

class Solution(object):
    def firstBadVersion(self, n):
        left = 1
        right = n
        while left <= right:
            mid = (left + right)//2
            if isBadVersion(mid):
                right = mid - 1 
            else:
                left = mid + 1
        return left


花費時間：10分鐘
完成程度：自己想的

---
### 6. 二元搜尋應用：開根號後的整數部分
- [Leetcode 69](https://leetcode.com/problems/sqrtx/)
- **解題思路**：跟第三題插入位置有點類似，只是輸出不是index值，是插入位置左邊的整數（所以最後return right）。
- **code**：

class Solution(object):
    def mySqrt(self, x):
        left = 0
        right = x
        while left <= right:
            mid = (left + right)//2
            if mid*mid == x:
                return mid
            elif mid*mid > x:
                right = mid - 1
            else:
                left = mid + 1
        return right


花費時間：20分鐘
完成程度：自己想的

---
## 本周心得
在上NP-complete的時候，發現有些NP難題如0/1 knapsack problem以及Traveling salesperson problem，我在上學期修習operations research的時候就有遇過，只是沒有使用程式輔助，都用手算（我是應數系的）；二元搜尋法也是有在資料結構學過，所以覺得沒有特別困難。線上上課滿好的！可以照自己喜好的速度來上課，但是功課滿花時間的😅