---
# System prepended metadata

title: Day 28 Easy x 2
tags: [經典題, 常用解]

---

# Day 28 Easy x 2

## LeetCode 100 題
![](https://i.imgur.com/aPXlyq3.png)

## 待優化的兩題
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.程式碼:
```python 
# 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:
![](https://i.imgur.com/cI5KnEn.png)

- 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

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





