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:

• More info.(total solution):
  https://leetcode.com/problems/guess-number-higher-or-lower/solution/
• Next try optimize:
  • ★ Ternary Search or 其他更快的方法

LeetCode 543. Diameter of Binary Tree

Source

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

不easy的easy

等我更了解後，再来记录!