# 演算法導論 HW1
https://hackmd.io/@wang1234/Bkc-g3nyc
## 1. 本週影片中提到的NP-complete問題有哪些？
給定一些數字，將這些數字分成兩個集合，使得兩集合內數字的總和相等(當數字少時能以列舉配隊的方式去解決，但數字多時此方法便非常費時)
*NP-complete：當問題的規模變大時，演算法學者們找不到有效率的解法，(須經過嚴謹的演算法證明)*

## 2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。
Vertex Cover Problem(頂點覆蓋問題)：給定一個無向圖，頂點覆蓋問題是要找到最小頂點覆蓋(即用最少的頂點來覆蓋所有的邊)
輸入：undirected tree(無向樹)(是一種無向圖)，頂點集合V={A,B,C,D,E,F,G}，邊集合E={(A,B),(A,E),(B,C),(D,E),(E,F),(F,G)}
輸出：{B,E,G}
*參考資料來源:*
* https://www.chegg.com/homework-help/questions-and-answers/vertex-cover-graph-g-v-e-subset-vertices-s-cv-includes-least-one-endpoint-every-edge-e-giv-q51659546
* https://www.geeksforgeeks.org/introduction-and-approximate-solution-for-vertex-cover-problem/
* https://zh.wikipedia.org/zh-tw/%E8%A6%86%E7%9B%96_(%E5%9B%BE%E8%AE%BA)

## 3. 二元搜尋應用：當數字可以重覆
解題思路: 原程式裡一旦在list中找到key，就可直接輸出其index，但若是數字可以重覆，就要先將找到的index儲存至變數temp，然後繼續針對index比temp小的區塊繼續搜尋，讓temp去存更小的index，最後如果temp不等於初始值(即曾在list中找到key且更動了temp)，返回temp;否則，返回-1

def binary_search(data, key):
  temp = len(data)
  left, right = 0, len(data) - 1
  while left <= right:
    mid = (left + right) // 2
    if data[mid] < key:
      left = mid + 1
    elif data[mid] > key:
      right = mid - 1
    else:
      if mid < temp:
        temp = mid
        right = mid - 1
  if temp != len(data):
    return temp
  else:
    return -1

data = [1, 3, 3, 6]
key = 3
print(binary_search(data, key))

花30分鐘，完全靠自己

## 4. 二元搜尋應用：找數字該插入的位置
解題思路: 需修改的部分在當list中找不到target時的處理，while迴圈結束後所儲存的mid對應list的index位置，其值若小於target，表示target應在其後方(mid+1)的位置插入;其值若大於target，那mid便是target該插入的位置

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

花10分鐘，完全靠自己

## 5. 二元搜尋應用：找到最早出問題的版本
解題思路: 有1到n個版本，所以將1和n分別設為list的邊界，若從這些版本是否有出錯的情況來看此list為[False,False,...,False,True,True,...,True]，而要尋找的目標即是丟入isBadVersion()後第一個(號碼最小的)返還True的版本，由此可見，當isBadVersion(mid)返還True，應將搜尋上限拉至mid的前一位(mid-1);反之，返還False時，將搜尋下限拉至mid的後一位(mid+1)，但最終mid存的數值可能是最後一個False或者第一個True的版本，因此輸出前還需要一次判斷，如果是False，那就要輸出下一個，才能符合題所求

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

花20分鐘，完全靠自己

## 6. 二元搜尋應用：開根號後的整數部分
解題思路:
1. 利用對於所有大於等於0的整數x，√x<=x/2+1，由此，將搜索範圍設成0到int(1/2)+1
|||
*如果只把範圍設到int(1/2)，當x=1時會出錯*
2. 當x是完全平方數，便會在跑while迴圈時返還其平方根;但如果不是，就需要再次做比較來判斷，在mid的平方小於x時，返還mid;在mid的平方大於x時，返還mid-1

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

花30分鐘，完全靠自己(後續發現有問題時，借助網路上的工具驗證)

## 7. 本週心得
前2題反覆看了幾次影片，卻還是覺得自己寫出的內容不夠清晰、完整，程式題的部分可能因為相互有關連，除了在第3題花了較久的時間理解二元搜尋的程式，其餘4~6題修改程式時還算快速、直覺，但是寫解題思路相當費時