https://leetcode.com/problems/guess-number-higher-or-lower/
經典題
In and Out
In: n
n代表 欲pick的輸入在1~n間(inclusive 1,n)
def guessNumber(self, n: int) -> int:
但是 Test case為兩個數字 n,pick
Out: pick
API說明
會使用到guess(...)
這個API
參數為n,也就是內部程式會將pick 與 n 比大小
pick 比 n 大,回傳-1
pick 比 n 小,回傳1
pick, n 兩者一樣則回傳0
Notice: Brute Force 會超時
常用解
如果 mid 剛好 hit(命中) pick 則回傳 mid
如果pick比mid大,則代表pick落在右區間,
把 low 移到 mid 右邊,也就是 low = mid + 1,
如果pick比mid小,則代表pick落在左區間,
把 high 移到 mid 左邊,也就是 high = mid - 1,
PS: 因 1~n 為照序排好的情況,因此可做Binary Search
https://leetcode.com/problems/diameter-of-binary-tree/
等我更了解後,再來記錄!