Introduction binary search的精隨就是在一個排序過的數列裡面，找出所要的值。因為每次都切半，所以可以時間複雜度達到O(logN)。相較於暴力破解法，例如答案在1~N之內，==如果測試函數可以讓你知道數字是往更大或更小的方向，就可以用binary search。== remove special case(答案不在可能的範圍內) 因為繼續使用binary search，如果答案比範圍內的還大，會得到left = sz。(還可以判斷) 如果答案比範圍內的還小，會得到left = 0。(無法判斷) 定義出答案可能出現的範圍left和right。 因為計算mid的方法，right必須是範圍最大值+1。 決定中間點，mid = left + (righ - left) / 2; 避免有overflow的問題。
2/6/20231908. Game of Nim 給你一個vector<int> piles，讓alice和bob輪流玩這個遊戲，每次可以從任意非零的stack中移除最少1個最多全部piles[i]，不能移動的那個palyer就是輸。返回alice使否會贏。這邊的前提是player都是optimal，也就是palyer會選對自己最有利的狀態。 這題算是萬用題。怎麼說。因為任何題目都可以使用暴力破解，也就是列舉所有的可能性。最後再透過memorization來降低複雜度。 這邊的暴力破解就是列舉所以可能的state，一個一個去嘗試，直到有結果。 因為player是optimal的，如果你是player一定會選一個對自己最有利的狀況，也就是會下一手讓對手沒機會贏的狀態。也就是這個nextState對手沒機會贏。 isNextPlayerWin(vector<int>& nextState)定義為，使用nextState這個狀態，對方是否有機會贏。只要一有機會就是return true。因為這樣才能判斷是否是一定可以贏的狀態。 class Solution { string getKey(const vector<int>& piles) {
1/30/2023Introduction 131. Palindrome Partitioning 給你一個string找出所有可能的切割方法，讓切割出來的substring都是palindrome。例如: s = "aab"，則返回[["a","a","b"],["aa","b"]] backtracking 可以視為queue裡面有每個可能的答案， 最後條件滿足就把答案存起來， pop掉最後一個，繼續從這個狀態尋找下一個可能 從上面的答案可以知道，一開始我的candidate可能是"a"或是"aa" 所以必須設計一個演算法可以找出candidate的可能性。
1/22/2023C++ Container ref : https://srhuang.github.io/c++/2019/11/15/cplusplus-004.html Name Brief Iterators Capacity Element Access Modifiers Others
1/18/2023