iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

FRIENDS系列 第 28

Day 28 Easy x 2

Day 28 Easy x 2

LeetCode 100 題

待優化的兩題

  1. Guess Number Higher or Lower
  2. 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)

tags: 經典題

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.思路:

tags: 常用解
  • 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.程式碼:

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:

        
        if guess(n)==0:
            return n
        low  = 1
        high = n
        
        while low<=high: # imp: = 
            print(low,high)
            mid = int((low+high)/2)
            print(mid)
            if guess(mid) == 0:
                return mid
                
            if guess(mid) == (-1):
                high = mid -1
            if guess(mid) == 1:
                low = mid+1
        #return -1        

Result:

LeetCode 543. Diameter of Binary Tree

Source

https://leetcode.com/problems/diameter-of-binary-tree/

不easy的easy

等我更了解後,再來記錄!


上一篇
Day 27: 暴力破解 WPA/WPA2 加密 wifi 密碼
下一篇
Day 29: Flutter Development
系列文
FRIENDS30

尚未有邦友留言

立即登入留言