# 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

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