DAY 28
0

# Day 28 Easy x 2

## 待優化的兩題

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/

### 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的中間，

PS: 因 1~n 為照序排好的情況，因此可做Binary Search

### 3.程式碼:

``````# The guess API is already defined for you.
# @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
``````

## LeetCode 543. Diameter of Binary Tree

### Source

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

FRIENDS30