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