Day 28 Easy x 2
LeetCode 100 題
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
待優化的兩題
- Guess Number Higher or Lower
- Diameter of Binary Tree
LeetCode 374. Guess Number Higher or Lower
Source
https://leetcode.com/problems/guess-number-higher-or-lower/
use API-guess(n)
1.題意:
-
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 會超時
2.思路:
- Binary Search
設定兩個指針 low, high
初始為 low = 1, high= n
先猜答案落在 mid 位置,也就是1與n的中間,
如果 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
3.程式碼:
Result:
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
LeetCode 543. Diameter of Binary Tree
Source
https://leetcode.com/problems/diameter-of-binary-tree/
不easy的easy
等我更了解後,再來記錄!