<style>
.text-center {
text-align: center;
font-size: 24px;
font-weight: bold;
}
</style>
<p class="text-center">
朱禹澄Leetcode刷題筆記
</p>
## **INFO**
刷題過程的紀錄，主要以較為簡單python為主，學習脈絡參考NeetCode的Roadmap。我將做過的題目統整，作為供自己及大家參考與複習的資源。此外，為增進觀看體驗，若使用手機載具建議使用==橫向觀看==。每一題的筆記架構主要分為五大部分:**(下方三角形點按即可展開查看)**
:::success
- **學到的東西**
- **題目名稱、說明及答題日期**
- **題目說明**
- **程式碼(僅供參考)、運行速度及使用空間效率比較**
- **我遇到的困難和盲點**
:::
## **ROADMAP**
```mermaid
graph LR;
ARRAYS_AND_HASHING-->TWO_POINTERS;
TWO_POINTERS-->LINKED_LIST;
TWO_POINTERS-->SLIDING_WINDOWS;
TWO_POINTERS-->BINARY_SEARCH;
ARRAYS_AND_HASHING-->STACK;
LINKED_LIST-->TREES;
BINARY_SEARCH-->TREES;
TREES-->TRIES
TREES-->HEAP/PRIORITY_QUEUE
TREES-->BACK_TRACKING
```
## **SYMBOL**
- **easy**::star:, **medium**::muscle:, **hard**::boom:
- **well-done**::rocket:, **good**::100:, **excecutable**::heavy_check_mark:
- **need review**::small_red_triangle:
## ==**ARRAYS & HASHING**==
### **:star:217. Contains Duplicate**
:::info
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
:::
:::spoiler 練習紀錄 **press**
- [ ] 2024/05/08 1hr
- [ ] 2024/05/19 5min
:::
:::spoiler 學到的東西
* differences between set & List
* ==hash table== TC is **$O(1)$ when searching** **cf.** **list** search: **$O(n)**$
* my_set = ==set$()$== ,or my_set = =={}== **cf.** my_tuple = ==$()$==, my_dict = {}
* $O(nlogn)$ & $O(n)$ --> **$O(nlogn)$** (==take the **more influential one**==)
:::
:::spoiler 說明
:::success
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
:::
:::spoiler 程式碼(共三解)
:::warning
**Sol1:利用排序，順向跟右邊鄰居比大小:100:** O(n*logn)
Runtime: Beats 10.08% of users with Python
Memory: Beats 95.48% of users with Python
```python=
class Solution(object):
def containsDuplicate(self, nums):
nums.sort() #O(n*logn)
for i in range(len(nums)-1): #O(n)
if nums[i] == nums[i+1]:
return 1
return 0
```
**:small_red_triangle:Sol2:利用hash set(一種集合，內部元素不能重複):100:** $O(n)$
Runtime: Beats 80.48% of users with Python
Memory: Beats 24.63% of users with Python
```python=
class Solution(object):
def containsDuplicate(self, nums):
hashset = set()
for num in nums: #O(n)
if num in hashset: #O(1)
return 1
hashset.add(num)
return 0
```
**Sol3:利用創建一個新串列(test)，把未重複的append進去，若有重複則return 1 :heavy_check_mark:** $O(n^2)$
Time Limit Exceeded 70 / 75 testcases passed
```python=
class Solution(object):
def containsDuplicate(self, nums):
# list = [] 不應該用list當作串列的名稱
test = []
for num in nums: #O(n)
if num not in test: #O(n)
test.append(num)
else:
return 1
return 0
```
:::
:::spoiler 錯誤
:::danger
與Sol1 1比較
```python=
class Solution(object):
def containsDuplicate(self, nums):
nums.sort()
for i in range(len(nums)-1):
if nums[i] < nums[i+1]:
return 0
return 1
```
:::warning
return之後就會跳出迴圈了!
:::
***
### **:star:242. Valid Anagram**
:::info
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
:::
:::spoiler 練習紀錄
- [x] 2024/05/09 1hr
- [ ] 2024/05/19 10min
:::
:::spoiler 學到的東西
```python=
count_s[char] = count_s.get(char, 0) + 1
```
* **ADD** d[key] = value -> add new pair of elements in d
* **GET** d[key] = value -> value of the key (KeyValue may happen)
* **GET** d.get(key, k) -> the value of key or a default value(默認值) "k"
* $O(n)$ + $O(n)$ -> $O(n)$
:::
:::spoiler 說明
:::success
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:利用字典來判斷各字串的元素種類與個數:100: $O(n)$**
Runtime: Beats 65.36% of users with Python
Memory: Beats 80.33% of users with Python
```python=
class Solution(object):
def isAnagram(self, s, t):
if len(s) != len(t):
return False
# 創兩個空字典
count_s = {}
count_t = {}
# 統計s中每個字母出現的次數
for char in s:
count_s[char] = count_s.get(char, 0) + 1
#賦予key(char)一個值(原本char的值+1)(若char不存在則默認為0+1)
#char對應的值 = 原本的值 + 1
#字典名稱[鍵] = 值
#get() 函数用於返回指定键的值。
#字典.get(鍵的名稱 , 若沒有該鍵則賦予該變亮的默認值)
#統計t中每個字母出現的次數
for char in t:
count_t[char] = count_t.get(char, 0) + 1
# 檢查兩個字典是否相同
return count_s == count_t
```
:::
:::spoiler 錯誤
:::danger
在清除i時會把內部所有跟i一樣值的都清掉假i此時等於a
又new_t="aaabc", s="ab"
則for i in s:
if i in new_t:
new_t = new_t.replace(i, "")
跑完後new_t = "c"
```python=
class Solution(object):
def isAnagram(self, s, t):
new_s = s
new_t = t
if len(s) != len(t):
return 0
for i in s:
if i in new_t:
new_t = new_t.replace(i, "")
else:
return 0
return len(new_t) == 0
for j in t:
if j in s:
new_s = new_s.replace(j, "")
else:
return 0
return len(new_s) == 0
```
:::
***
### **:star:1.Two Sum**
:::info
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
:::
:::spoiler 練習紀錄
- [ ] 2024/05/09 1hr
- [x] 2024/05/21 15min
:::
:::spoiler 學到的東西
* ==d[key] = value== -> **add new pair** of elements in the dictionary d
* ==Hash Map== -> a **valid presentation of Hash Table**
* ==for i, elemnet in list==: -> i/**index**, element/**element** in the list
:::
:::spoiler 說明
:::success
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:利用HashMap把為配對成功的加入字典中(鍵為數字值為索引):rocket:$O(n)$**
Runtime: Beats 92.64% of users with Python
Memory: Beats 77.37% of users with Python
```python=
class Solution(object):
def twoSum(self, nums, target):
# 建立哈希表，用來記錄每個數字的索引
hash_map = {}
# 遍歷列表，查找目標數字
for i, num in enumerate(nums):
complement = target - num
# 如果補數已經存在於哈希表中，則返回答案
if complement in hash_map:
return [hash_map[complement], i]
# 否則，將當前數字添加到哈希表中
hash_map[num] = i
# 如果找不到解，則返回 None
return None
```
:::
:::spoiler 錯誤
:::danger
index() 方法来得到原始 nums 中索引。但是，因為有重複元素，所以 index() 方法只會返回第一个匹配的索引。
例如list = [6,6]->list.index(6) = 0 而非等於1
```python=
class Solution(object):
def twoSum(self, nums, target):
answer = []
sortednums = sorted(nums)
pivot_index = 0 # 初始化 pivot_index
# 找到 target/2 左右的數值
for i in range(len(sortednums) - 1):
if sortednums[i] <= 0.5 * target < sortednums[i + 1]:
pivot_index = i
break
# 固定右邊的值，從左邊區間開始加
left = 0
right = pivot_index + 1
while left < pivot_index + 1:
total = sortednums[left] + sortednums[right]
if total == target:
ans1 = nums.index(sortednums[left])
ans2 = nums.index(sortednums[right])
answer.append(ans1)
answer.append(ans2)
return answer
elif total < target:
left += 1
else:
right += 1 # 將右邊固定的邊界加一
if right >= len(nums): # 當 right 超過列表範圍時，結束迴圈
break
return None
```
:::warning
注意雙重迴圈的語法(break, continue)!
break 是停止該迴圈內該round下面的代碼
:::
***
## ==**TWO POINTERS**==
### :muscle:**15.Three sum**
:::info
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
:::
:::spoiler 練習紀錄
- [ ] 2024/05/10 2hr
- [ ] 2024/05/21 35min
:::
:::spoiler 學到的東西
```python=
if left < right and nums[left] == nums[left + 1]:
vs.
while left < right and nums[left] == nums[left + 1]:
```
* **if** -> ==做完就走人==，不管下一個情況是怎樣
* **while** -> ==做到就算結束後**下一個不滿足條件為止**==，每次做完**持續檢查**
* 加入==left < right== 避免移完左pointer跑到右邊(必須得加) 例如:**[0,0,0]** left會一直往右邊跑
* Conclusion: Don't forget the ==global(partial large)statement== when using ==nested while loop==
:::
:::spoiler 說明
:::success
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:固定一數字，藉由total和target間的關係調整另外兩數:rocket:$O(n^2)$**
Runtime: Beats 76.27% of users with Python
Memory: Beats 76.03% of users with Python
```python=
class Solution(object):
def threeSum(self, nums):
nums.sort()
res = []
length = len(nums)
for i in range(length-2): # 2 indices for left & right
if i > 0 and nums[i] == nums[i-1]:
continue #avoid duplicate triplets
left = i + 1
right = length - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total > 0:
right -= 1
elif total < 0:
left += 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1 #avoid duplicate triplets
left += 1
right -= 1
return(res)
```
:::
:::spoiler 錯誤
:::danger
1.判斷完直接return，導致若有大於一組解的情況會出錯。(第一組解產生時迴圈就終止了)
```python=
...
else:
res.append([nums[i], nums[left], nums[right]])
return(res)
while nums[left] == nums[left]:
left += 1
while nums[right] == nums[right-1]:
right -= 1 #avoid duplicate triplets
...
```
2.出現duplicate triplets的情況
推測是由於i在跑迴圈加1的時候遇到的值是一樣的，導致可能重複一次解
解決方案:用if判斷nums[i],nums[i+1]是否相等，若是，則continue(跳過該迴圈下面的程式碼，直接進行下一round(i+1))
```python=
if nums[i] == nums[i-1]:
continue #avoid duplicate triplets
```
但是這樣還是會有問題:
```python=
if i > 0 and nums[i] == nums[i-1]:
continue #avoid duplicate triplets
```
if nums[i] == nums[i-1]: 會檢查到nums[-1]變成在跟list中最後一個元素比較。所以，我們應該要避免i == 0時的檢查情況，故需要加入i > 0這個必要條件
:::
***
### **:star:125.Valid Palindrome**
:::info
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
:::
::: spoiler 練習紀錄
- [ ] 2024/05/12 1hr
- [x] 2024/05/22 6min
:::
:::spoiler 學到的東西
* **2 pointers** make $O(n^2)$ to **$O(n)$**
* ==isalpha()== 只有==字母==(**不含數字**)
* ==isalnum()== 只有==字母和數字==
:::
:::spoiler 說明
:::success
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
Constraints:
1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.
:::
:::spoiler 程式碼
:::warning
**Sol1:利用two pointers從兩邊往中間查找:100:$O(n)$**
Runtime: Beats 47.26% of users with Python
Memory: Beats 18.06% of users with Python
```python=
class Solution(object):
def isPalindrome(self, s):
cleaned_s = ''.join(c.lower() for c in s if c.isalnum()) #只有字母和數字
length = len(cleaned_s)
left = 0
right = length - 1
while left < right:
if cleaned_s[left] == cleaned_s[right]:
right -= 1
left += 1
else:
return 0
return 1
```
:::
:::spoiler 錯誤
:::danger
non-alphanumeric characters:只有英文字母和數字
- isalpha() 只有字母(不含數字)
- isalnum() 只有字母和數字
:::
***
## ==**STACK**==
### **:star:20.Valid Parentheses**
:::info
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
:::
:::spoiler 練習紀錄
- [ ] 2024/05/13 1hr
- [ ] 2024/05/22 20min
:::
:::spoiler 學到的東西
* **if ==KEY== in dict**: check whether the variable is **one of the key in the dictionary**
* if check[i] in stack ==**and check[i] == stack[-1]**==: add the requirement when do the pop action
:::
:::spoiler 說明
:::success
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:利用stack堆疊，及pop和字典查找來檢查對應關係:rocket: $O(n)$**
Runtime: Beats 93.82% of users with Python
Memory: Beats 84.71% of users with Python
```python=
class Solution(object):
def isValid(self, s):
check = {")": "(" , "]": "[" , "}": "{"}
stack = []
for i in s:
if i in check:
if check[i] in stack and check[i] == stack[-1]:
stack.pop()
else:
stack.append("*")
else:
stack.append(i)
return not stack
```
:::
:::spoiler 錯誤
:::danger
```python=
s = "(){}[]"
mapping = {a:b, c:d, d:e}
stack = []
for char in s
if char in mapping:
...
else:
stack.append(char)
```
for char in mapping是指**char這個元素屬於mapping字典中的鍵(key)的情況**。所以如果此時char是字典裡的值，則會進入else裡被append到stack裡等待被pop出來比較
所以如果把mapping這個字典的鍵值互換會出現問題
```python=
mapping = {"(": ")", "[": "]", "{": "}"}`
```
這樣會變成先從"("開始，他是key所以會去跟stack pop出來的元素比較。但問就是")"根本就還沒出現
所以結論是要先讓value被append到stack list裡，再輪到代表key的元素與前面一round被append到的value做對應 ~~真麻煩~~
***
錯誤:只單單判斷下一個會導致大包小的正確情況({[]})被忽略
```python=
class Solution(object):
def isValid(self, s):
res = []
for i in s:
res.append(i)
for i, char in enumerate(res[:-1]):
# [:-1]表示去除掉最後一個元素
# 使用 enumerate() 獲取索引和元素，並遍歷到倒數第二個元素
next_char = res[i+1] # 獲取相鄰的下一個元素
if char == "(":
if next_char != ")":
return False
elif char == "[":
if next_char != "]":
return False
elif char == "{":
if next_char != "}":
return False
return True
```
原本正確的是:只要不要完整的夾住一個落單的就好，利用的方法是先把它存在一個stack list裡面，如此一來解決了大包小被忽略的情況，
stack list的情況:大1 ->大1小1 -> ->大1(小1小2配對，後進的小1先被pop出來) -> null(大1大2，最先進來的大1最後也因為跟大2這個value配對被pop出來了) -> not stack == True
:::
***
## ==**BINARY SEARCH**==
### **:star:704. Binary Search**
:::info
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
:::
:::spoiler 練習紀錄
- [ ] 2024/05/14 15 min
- [ ] 2024/05/23 12 min
:::
:::spoiler 學到的東西
```python=
while left <= right:
```
* 若沒有加上"="，==只有一個數字的串列==(例:**nums=[0]**)==沒辦法跑while loop的邏輯==，導致其return -1
:::
:::spoiler 說明
:::success
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.
:::
:::spoiler 程式碼
:::warning
**Sol1:binary search 一次捨去掉一半:100: $O(log_2n)$**
Runtime: Beats 76.15% of users with Python
Memory: Beats 60.37% of users with Python
```python=
class Solution(object):
def search(self, nums, target):
start = 0
end = len(nums) - 1
while start <= end:
mid = start + (end - start) // 2
mid_value = nums[mid]
if mid_value == target:
return mid
elif mid_value > target:
end = mid - 1
else:
start = mid + 1
return - 1
```
:::
:::spoiler 錯誤
:::danger
把mid的賦值放在迴圈外匯導致迴圈內沒有辦法實現該邏輯。因此下次我在做的時候要特別小心關鍵變數賦值的位置
```python=
def search(self, nums, target):
...
mid = start + (end - start) // 2
mid_value = nums[mid]
while start <= end:
if mid_value == target:
return mid
...
```
:::
***
## ==**SLIDING WINDOW**==
### **:star:121. Best Time to Buy and Sell Stock**
:::info
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
:::
:::spoiler 練習紀錄
- [ ] 2024/05/15 55 min
- [ ] 2024/05/23 15 min
:::
:::spoiler 學到的東西
```python=
max_profit = 0
buy = prices[0]
```
* Find the maximun by ==defining and initializing varibles==, then ==**constantly assign new values** under certain circumstances or statements.==
* Variable **names** = **Value** going to assign
* if a<b, ==max(a, b) -> b== (choose the **relatively large** one)
* ==if price < min_price: min_price = price== <--> ==min_price = min(min_price, price)==
:::
:::spoiler 說明
:::success
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104
:::
:::spoiler 程式碼(共三解)
:::warning
**Sol1:傻傻地做兩個for loop的查找, so TC: $O(n^2)$:heavy_check_mark:**
Time Limit Exceeded
198 / 212 testcases passed
```python=
class Solution(object):
def maxProfit(self, prices):
def find_max(prices, start):
new_prices = []
for j in range(start, length):
new_prices.append(prices[j])
new_prices.sort()
return new_prices[-1]
# new_prices = []
check = []
length = len(prices)
start = 0
for i in range(0, length - 1): #預留一個給最後賣出的點
start += 1
profit = find_max(prices, start) - prices[i]
if profit > 0:
check.append(profit)
check.sort()
if not check:
return 0
else:
return check[-1]
```
這個嘗試很好、很直覺，但是time complexity非常糟$O(n^2)$而且其實上面程式碼其實可以簡化成以下:
```python=
class Solution(object):
def maxProfit(self, prices):
max_profit = 0
length = len(prices)
for i in range(length - 1): # 遍歷所有的價格，注意到最後一天不能作為買入點，所以到倒數第二天為止即可
for j in range(i + 1, length): # 對於每個買入點，找到其之後的每一天作為賣出點
profit = prices[j] - prices[i] # 計算利潤
max_profit = max(max_profit, profit) # 更新最大利潤
return max_profit
```
**Sol2:善用max,min函式即時更新，只用到一個for loop, so TC: $O(n)$:100:**
Runtime: Beats 43.00% of users with Python
Memory: Beats 88.32% of users with Python
```python=
class Solution(object):
def maxProfit(self, prices):
max_profit = 0 #往後可篩掉小於0的情況
min_price = float('inf') #初始值先設定為無窮大
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, (price - min_price))
return max_profit
```
**Sol3:與第二個解法相似，只用到一個for loop, so TC: $O(n)$:rocket:**
Runtime: Beats 70.70% of users with Python
Memory: Beats 69.60% of users with Python
```python=
class Solution:
def maxProfit(self, prices) :
max_profit = 0
lowest = prices[0]
for price in prices:
if price < lowest:
lowest = price
max_profit = max(max_profit, price - lowest)
return max_profit
```
:::
:::spoiler 錯誤
:::danger
錯誤1:並沒有在每次呼叫函式時清空上一次的列表，會導致結果不正確
```python=
class Solution(object):
def maxProfit(self, prices):
def find_max(prices, start):
for j in range(start, length):
new_prices.append(prices[j])
new_prices.sort()
return new_prices[-1]
new_prices = []
...
```
應該要把new_prices = []放在函式內上方
```python=
def find_max(prices, start):
new_prices = []
for j in range(start, length):
...
```
另外，找最大值的部分並不需要額外花時間把列表排序完後抓最後一個，可以直接使用max()來更新最大值就可
錯誤2:函式放置的位子
函式必須在其被呼叫之前被定義，在main中呼叫到b函式時，b函式還沒有被定義，所以會被報錯
```python=
def main():
value = b()
def b():
...
```
下次我可以這樣寫:
```python=
def main():
def b():
...
value = b()
```
或是:
```python=
def b():
...
def main():
value = b()
```
:::
***
## ==**LINKED LIST**==
### **:star:206. Reverse Linked List**
:::info
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
:::
:::spoiler 練習紀錄
- [x] 2024/05/25 1 hr
- [x] 2024/06/30 15 min
:::
:::spoiler 學到的東西
* Linked list, a ==**node based** data structure.==
* Linked list, **Nodes** linked to each other, ==consists of **value and address** of the next element.==
* '**Head**' is the ==**first node of the linked list**==, containing both the value and the address.
* When you ==return head==, you will ==get **the whole linked list**==, as ==each node in the list is **linked one by one**==.
* "==a.next = b==" means that to you ==**append the address** of b into the nodes== containing the value of the element a
* You can ==access the singly linked list **only** by calling the first node==. If you **start visiting from the middle one**, you will end up **getting an incomplete list**.
```mermaid
graph LR;
linked_list-->Nodes;
Nodes---value;
Nodes---pointer;
value-->the_current_element;
pointer-->the_address_of_the_next_element;
```
:::
:::spoiler 說明
:::success
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
:::
:::spoiler 程式碼
:::warning
**Sol1:反轉next指針，new_list一路從None串到最後一個數字:rocket: $O(n)$**
Runtime: Beats 92.42% of users with Python
Memory: Beats 76.64% of users with Python
```python=
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def reverseList(self, head):
current = head
new_list = None
while current: #(while current != None)
next_node = current.next #要先把原本順序的下一個存在這不然下一行就被覆蓋掉了(方向返就不能把current往下推了)
current.next = new_list
new_list = current
current = next_node
return new_list
```
:::
:::spoiler 錯誤
:::danger
要先把原本順序的下一個(順向的指針)存在next_code裡，不然下一行就被覆蓋掉了
(方向反就不能把current往下推了)
```python=
while current: #(while current != None)
# next_node = current.next
current.next = new_list
new_list = current
current = next_node
return new_list
```
忘記更新new_list，只有變動(忽略了變數宣告的本意)卻在記憶體內失蹤了
new_list = current
```python=
class Solution(object):
def reverseList(self, head):
current = head
new_list = None
while current:
next_node = current.next
current.next = new_list
# new_list = current
current = next_node
return new_list
```
:::
***
### **:star:21. Merge Two Sorted Lists**
:::info
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
:::
:::spoiler 練習紀錄
- [x] 2024/05/31 1 hr
- [ ] 2024/07/01 30 min
:::
:::spoiler 學到的東西
```python=
dummy = ListNode()
result = dummy
```
* We need to ==set a ==**dummy variable**==(aka a pointer) to push on== and **an actual variable**(result) to record the node== we've been through. One is responsible for ==traversing==, and one is responsible for ==recording the value==
* ==**ListNode()**== is a function that you can **create an empty node**
* Similar to reversing a linked list, we also ==**saved the original pointer** into a variable==, and ==make the current node **point to the relatively small one** between list1 and list2==
* Use ==**list1 = list1.next**== to visit all the element in two lists
:::
:::spoiler 說明
:::success
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
:::
:::spoiler 程式碼
:::warning
**Sol1:創一個空節點然後再從兩個linked list中拿出元素比大小，把小的加上去:rocket: $O(n+m)$**
Runtime: Beats 33.88% of users with Python
Memory: Beats 89.53% of users with Python
```python=
class Solution(object):
def mergeTwoLists(self, list1, list2):
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val > list2.val:
new_list2 = list2.next
tail.next = list2
list2 = new_list2
else:
new_list1 = list1.next
tail.next = list1
list1 = new_list1
tail = tail.next #將 tail 指向新加入的節點。
if list1:
tail.next = list1
elif list2:
tail.next = list2
return dummy.next
```
:::
:::spoiler 錯誤
:::danger
原本想說把list2合併到list1裡，但是linked list一旦串起來就不能再改變順序了，因此我要保證每次在串的時候都要是正確的(因為不能中途insert進去)，所以我應該要先判斷兩者當前的值(list1.val和list2.val)，再跟head連接(hed.next = ...)
:::
***
### **:star:141. Linked List Cycle**
:::info
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
:::
:::spoiler 練習紀錄
- [x] 2024/06/02 11 min
:::
:::spoiler 學到的東西
* It will ==add the **WHOLE NODE** in the set==, not only the value, but the pointer as well
* **Floyd’s Cycle-Finding Algorithm**: if there is a cycle, ==the fast one will ultimataly meet with the slow one(倒追一圈)==
:::
:::spoiler 說明
:::success
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Constraints:
The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.
:::
:::spoiler 程式碼
:::warning
**Sol1:創一個hashset把traverse過的都加進去，然後砍掉頭，直到中止為止，如果是環狀則不會(用while current not in hashset來避免traverse第二圈第三圈的問題)::rocket: $O(n+m)$** **Space Complexity:$O(n)$**
Runtime: Beats 83.74% of users with Python
Memory: Beats 11.27% of users with Python
```python=
class Solution(object):
def hasCycle(self, head):
if head == None:
return 0
current = head
hashset = set()
while current not in hashset:
next_node = current.next
hashset.add(current)
current = current.next
while not current:
return 0
return 1
```
==**Follow up: Can you solve it using $O(1)$ (i.e. constant) memory?**==
**:small_red_triangle:Sol2: Floyd’s Cycle-Finding Algorithm(快慢指針):rocket:$O(n+m)$
Space Compexity:$O(1)$**
Runtime: Beats 51.03% of users with Python
Memory: Beats 88.40% of users with Python
```python=
class Solution(object):
def hasCycle(self, head):
if not head:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
```
:::
:::spoiler 錯誤
:::danger
忘記判斷空節點的存在，所以如果current = None時要add到hashset裡面就會有問題。
```python=
if head == None:
return 0
```
:::
***
## **==TREES==**
### **:star:226. Invert Binary Tree**
:::info
Given the root of a binary tree, invert the tree, and return its root.
:::
:::spoiler 練習紀錄
- [x] 2024/06/09 50 min
- [x] 2024/08/31 15 min :eye:
- [ ] 2024/09/01 10 min
:::
:::spoiler 學到的東西
* Binary tree, a ==**hierarchical node based** data structure.==, is just ==a linked list with an additional pointer==
* Similar to linked lists, ==binary trees== will also ==**store the currrent value and the address**== **(left-child and right-child)**
* **Binary Search Tree(BST)** is one of binary tree, which ==adds a condition that **left-child < current < right-child**==
* ==The time complexity== for **adding**, **searching**, or **deleting** ==in a BST is $O(logn)$.==
* **DFS**(depth-first search) vs. **BFS**(Breadth-first search)
* assign **2** variables' value **in parallel** -> ==a,b = 1,2==
:::
:::spoiler 說明
:::success
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:深度優先(Depth-First-Search)(DFS)利用Stack特性(Lasr in, First out)(LIFO)來儲存要處理的節點，透過append加入後，藉由pop把其取出 :rocket: $O(n)$**
由於堆疊（stack)是後進先出（LIFO），先壓入的子節點會在稍後處理。因此，確保了當前節點的右子節點會先於左子節點被處理，保證了深度優先搜尋的遍歷順序。
Runtime: Beats 87.96% of users with Python
Memory: Beats 97.38% of users with Python
```python=
class Solution(object):
def invertTree(self, root):
while not root:
return None
stack = [root]
# repeatedly do until all the pointer have done
while stack:
current = stack.pop()
current.left, current.right = current.right, current.left
if current.left:
stack.append(current.left)
if current.right:
stack.append(current.right)
return root
```
**:small_red_triangle:Sol2:深度優先(Depth-First-Search)(DFS)利用recursion。先把新樹的左半邊由上往下鏡像，再把右半邊由上往下鏡像:rocket: $O(n)$**
Runtime: Beats 77.52% of users with Python
Memory: Beats 16.75% of users with Python
```python=
def invertTree(self, root):
if not root:
return None
# swap
root.left, root.right = root.right, root.left
# do it recursively
self.invertTree(root.left)
self.invertTree(root.right)
return root
```
:::
:::spoiler 錯誤
:::danger
原本思考的解法偏向廣度優先的策略，但是差就差在不知道該如何便利下去，因為每下去一層，就會一變為二，那current到底是要賦於給誰?
***
接續處理導致需要先命名變數儲存起來，再交換。程式碼不簡潔且會浪費記憶體空間。
```python=
right_child = current.right
left_child = current.left
current.left = right_child
current.right = left_child
```
透過同時進行的併行賦值(多重賦值)，同時交換避免了在交換期間的臨時狀態問題
```python=
current.left, current.right = current.right, current.left
```
:::
***
### **:star:104. Maximum Depth of Binary Tree**
:::info
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
:::
:::spoiler 練習紀錄
- [x] 2024/06/10 1hr30min
- [x] 2024/08/31 1hr :eye:
- [ ] 2024/09/01 15 min
:::
:::spoiler 學到的東西
* The key to **solving rcursive problems** is to **==store the results in the function's return value==** **instead of external variables**(==external variable cannot be passed during recursion==)
* Typical example of ==**DFS** implemented by using **recursion**.==
* How **recursion** works: ==A function **calls itself**== to solve smaller instances of the same problem ==until reaching a **base case**.==
* **queue.popleft()** -> **FIFO**
* **Queue**==(First in first out)== vs. **Stack**==(Last in first out)==
* Self
:::
:::spoiler 說明
:::success
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:深度優先(DFS)遞迴(Recursion)把樹一直切分，左端點當作新的root，往左不行往右，往右也不行就加一 :rocket: $O(n)$**
想成流水，從最高的root往下流(優先走左邊)，左邊右邊都堵住後加一(DFS)(LIFO)
Runtime: Beats 50.59% of users with Python
Memory: Beats 81.27% of users with Python
```python=
class Solution(object):
def maxDepth(self, root):
if not root:
return 0
else:
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
```
**:small_red_triangle:Sol2:廣度優先(BFS) 利用Queue紀錄當前深度:rocket: $O(n)$**
想成流水，每往下一層樓架一個木板在樓梯上防堵，直到整層樓淹滿再往下(BFS)(FIFO)
Runtime: Beats 61.62% of users with Python
Memory: Beats 54.08% of users with Python
```python=
class Solution(object):
def maxDepth(self, root):
if not root:
return 0
queue = collections.deque()
queue.append((root, 1))
max_level = 0
while queue:
node, level = queue.popleft()
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
max_level = max(max_level, level)
return max_level
```
:::
:::spoiler 錯誤
:::danger
原本想要沿用昨天invert binary tree的方法，但是實際想想，會發現用stack是在拚運氣，如果猜錯又會回去找，這樣層數就錯了
```python=
if not root:
return 0
current = root
stack = [root]
layer = 1
while stack:
current = stack.pop()
if current.left or current.right:
layer += 1
if current.left:
stack.append(current.left)
if current.right:
stack.append(current.right)
return layer
```
the 'father' variable cannot be pass through function calling
```python=
def maxDepth(self, root):
# base case
if not root:
return None
count = 1
if root.left:
# record the father just in case the child has no child
father = root
root = root.left
count += 1
self.maxDepth(root)
elif root.right:
father = root
root = root.right
count += 1
self.maxDepth(root)
# neither have left pointer nor right pointer
else:
root = father
self.maxDepth(root)
return count
```
錯誤：
1. Var 'count' cannot be iterate -> **self.count**. Besides, it will **be repeatedly initialize during every function call**
2. It should **return 0** instead of None when **meeting the base case**
3. **Don't have to check the 'root.left' and 'root.right' is exist or not** at all, cuz when they are inputted in the function, they will be gone **==through the base case and checked first==**, if they are **not exist**, we simply **just return 0**
4. **Make good use of the ==return value in recursion==, ==don't need a external var== to do the iteration**
```python=
class Solution(object):
def maxDepth(self, root):
# base case
if not root:
return None
count = 0
if root.left:
self.maxDepth(root.left)
elif root.right:
self.maxDepth(root.right)
else: # neither have left pointer nor right pointer
return count + 1
return count
```
:::
***
### **:star:543. Diameter of Binary Tree**
:::info
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
:::
:::spoiler 練習紀錄
- [x] 2024/06/12 1hr30min
- [ ] 2024/08/31 40 min :eye:
- [ ] 2024/09/02 10 min
:::
:::spoiler 學到的東西
* Using self allows instance variables to ==be accessed and modified **throughout the entire class**==, enabling data sharing and **consistency across different methods**.
* ==Traverse every node during **every recursion**==, avoid losing some nodes
:::
:::spoiler 說明
:::success
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:深度優先(DFS)遞迴(Recursion)把樹一直切分，左端點當作新的root，往左不行往右，往右也不行就加一，traverse每一個節點檢查diameter(left + right) 最後return最大值(像流水一樣的遞迴演算法會確保每一個節點都被traverse到):rocket: $O(n)$**
思路:路線一定是一個倒V字型，左邊往上，**到端點**，再往下。那我是不是紀錄最頂點的左邊跟右邊的深度然後持續更新就好了
Runtime: Beats 50.59% of users with Python
Memory: Beats 81.27% of users with Python
```python=
class Solution(object):
def diameterOfBinaryTree(self, root):
self.diameter = 0
def maxDiameter(root):
if not root:
return 0
else:
leftMax = maxDiameter(root.left)
rightMax = maxDiameter(root.right)
self.diameter = max(self.diameter, leftMax + rightMax)
return max(leftMax, rightMax) + 1
maxDiameter(root)
return self.diameter
```
:::
:::spoiler 錯誤
:::danger
原本想說把root的左邊跟右邊深度取出來然後相加就是答案，結果沒有想到極度不平衡的清況，例如左邊萎縮，右邊自己走就會走出最遠距離。
極端例子例如:
這樣的解法對一半:對的地方在於檢查了最有可能是頂點的點(root)其左邊右邊深度相加，錯的地方在於peak有可能不是在root上，所以應該是在左recursion的時候，檢查每一個點的左右相加，然後不斷比大小並取代。
```python=
class Solution(object):
def diameterOfBinaryTree(self, root):
if not root:
return 0
left, right = root.left, root.right
leftMax, rightMax = 0, 0 #float('-inf'), float('-inf')
def LmaxDepth(left):
if not left:
return 0
else:
max_left = LmaxDepth(left.left)
max_right = LmaxDepth(left.right)
return max(max_left, max_right) + 1
def RmaxDepth(right):
if not right:
return 0
else:
max_left = RmaxDepth(right.left)
max_right = RmaxDepth(right.right)
return max(max_left, max_right) + 1
leftMax = LmaxDepth(root.left)
rightMax = RmaxDepth(root.right)
return leftMax + rightMax
```
:::
***
### **:star:110. Balanced Binary Tree**
:::info
Given a binary tree, determine if it is height-balanced.
Height-Balanced:
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
:::
:::spoiler 練習紀錄
- [x] 2024/06/14 1 hr
- [ ] 2024/09/02 20 min
:::
:::spoiler 學到的東西
* By ==using **Pruning** or **Early Exit in Recursion**== can find the attribute you want ==anywhere in the whole tree **no matter how many times** it appears.==
* ==**Checking statement**==: one for the ==**initial case** (0th round of loop)== + one for ==**the general, latter cases** (>=1th round of loop)==
:::
:::spoiler 說明
:::success
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:因為函數輸出的是跟節點返回的值 所以如果根節點返回的值是-1 則整個function的output就會是-1，透過這個特徵分辦該樹是否有某處是imbalance的:rocket: $O(n)$**
思路: 邏輯就是只要任何一顆樹有不平衡的情況，所有上面的節點都會被感染，感染到最上面的root最後就可以看到並判斷內部是不是有沒有平衡的地方
Runtime: Beats 100.00% of users with Python
Memory: Beats 52.83% of users with Python
```python=
class Solution(object):
def isBalanced(self, root):
if not root:
return 1
def maxDepth(node):
if not node:
return 0
else:
maxLeft = maxDepth(node.left)
maxRight = maxDepth(node.right)
if maxLeft == -1 or maxRight == -1 or abs(maxLeft - maxRight) > 1:
return -1
#該節點代表-1 以上面的節點來看下面的該節點就會是node.left 此時maxLeft == -1
return max(maxLeft, maxRight) + 1
return maxDepth(root) != -1
```
:::
:::spoiler 錯誤
:::danger
解法中
```python=
if abs(maxLeft - maxRight) > 1:
```
未加上確認子樹是否為添加上記號(-1)的小樹，因此應該改成
```python=
if maxLeft == -1 or maxRight == -1 or abs(maxLeft - maxRight) > 1:
```
當爸爸樹發現小樹有問題時，自己也會被做記號，如此一來阿公樹也會被做記號，阿公的阿公的阿公也會
錯誤：
1. **A tree is balanced** if the depth **difference between the left and right subtrees of every node does not exceed 1.**
2. To **check if a tree is balanced**, we must **verify the depth difference at ==every node==**, not just the overall maximum depth difference between the left and right subtrees.
```python=
def isBalanced(self, root):
self.left, self.right = 0, 0
def maxDepth(root):
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
self.left = max(self.left, left_depth)
self.right = max(self.right, right_depth)
return max(left_depth, right_depth) + 1
```
:::
### **:star:100. Same Tree**
:::info
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
:::
:::spoiler 練習紀錄
- [x] 2024/06/26 20min
:::
:::spoiler 學到的東西
* TreeNode is not iterable
:::
:::spoiler 說明
:::success
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints:
The number of nodes in both trees is in the range [0, 100].
$-10^4$ <= Node.val <= $10^4$
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:用三種情況概括兩個物件空或非空的狀態(文氏圖的交集情況):rocket: $O(n)$**
Runtime: Beats 86.38% of users with Python
Memory: Beats 31.35% of users with Python
```python=
class Solution(object):
def isSameTree(self, p, q):
if not p and not q: #兩者為空的情況
return True
if not p or not q: #其中一個為空(扣掉上面and篩掉的聯集情況)
return False
return (p.val == q.val) and \
self.isSameTree(p.left, q.left) and \
self.isSameTree(p.right, q.right)
#判斷時三者有一個是False就會是False
```
:::
:::spoiler 錯誤
:::danger
應該是比較數值，而不是整個節點
```python=
if (p.left == q.left) and (p.right == q.right):
p, q = p.left, q.left
```
當到達leaf node時，node.left, node.right == None
```python=
if p and q:
if (p.left.val == q.left.val) and (p.right.val == q.right.val):
```
再比較的時後仍要注意唯一的那個節點值一不一樣
```python=
if not p.left and not q.left and not p.right and not q.right:
~~return True~~
return (p.val == q.val)
```
結論:我應該先確定好，會有哪幾種狀況，再一一破解，而不是用錯的方法再慢慢補條件
:::
### **:star:572. Subtree of Another Tree**
:::info
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
:::
:::spoiler 練習紀錄
- [x] 2024/06/27 1hr(fail)
:::
:::spoiler 學到的東西
* check and ==divide all the possibilities== **first**
* Recursion:
```python=
def recursion():
if 中止條件(base case):
return False
if 目標條件:
return True
return 目標條件 and recursion(遞迴原動力) # (bool判斷式)
```
:::
:::spoiler **遞迴大家族**
```python=
def maxDepth(self, root):
if not root:
return 0
else:
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
```
```python=
def maxDiameter(root):
if not root:
return 0
else:
leftMax = maxDiameter(root.left)
rightMax = maxDiameter(root.right)
self.diameter = max(self.diameter, leftMax + rightMax)
return max(leftMax, rightMax) + 1
```
```python=
def findValue(root, target):
if not root:
return None
if root.val == target:
return root
left = findValue(root.left, target)
if left:
return left
return findValue(root.right, target)
```
```python=
# 判斷兩棵樹是否相同
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.val == q.val) and \
isSameTree(p.left, q.left) and \
isSameTree(p.right, q.right)
```
:::
:::spoiler 說明
:::success
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Constraints:
The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
$-10^4$ <= root.val <= $10^4$
$-10^4$ <= subRoot.val <= $10^4$
:::
:::spoiler 程式碼
:::warning
**:small_red_triangle:Sol1:用三個遞迴函式，功能分別為:
1.findValue()找到小樹頭節點對應到的大樹位置
2.isSameTree()判斷兩者是否為完全相同的樹
3.traverse()遍歷大樹中所有節點，因為數值一樣不代表就是那個對的節點
:rocket: $O(n)$**
Runtime: Beats 71.59% of users with Python
Memory: Beats 13.63% of users with Python
```python=
class Solution(object):
def isSubtree(self, root, subRoot):
# 在主树中找到与子树根节点值相同的节点
def findValue(root, target):
if not root:
return None
if root.val == target:
return root
left = findValue(root.left, target)
if left:
return left
return findValue(root.right, target)
# 判斷兩棵樹是否相同
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.val == q.val) and \
isSameTree(p.left, q.left) and \
isSameTree(p.right, q.right)
# 遍历主树并检查是否存在与子树相同的子树
def traverse(root, subRoot):
if not root:
return False
if isSameTree(root, subRoot):
return True
return traverse(root.left, subRoot) or traverse(root.right, subRoot)
return traverse(root, subRoot)
```
:::
:::spoiler 錯誤
:::danger
```python=
class Solution(object):
def isSubtree(self, root, subRoot):
# 先找到目標子樹的頭節點
def findValue(root, target):
if not root:
return None
if root.val == target:
return root
left = findValue(root.left, target)
if left:
return left
return findValue(root.right, target)
# 判斷兩棵樹是否相同
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.val == q.val) and \
isSameTree(p.left, q.left) and \
isSameTree(p.right, q.right)
# 在主樹中查找子樹的頭節點
new_root = findValue(root, subRoot.val)
# 判斷從找到的頭節點开始的子树是否和子樹相同
return isSameTree(new_root, subRoot) if new_root else 0
```
我的思路是:先用一個函式找到大樹中值是小樹頭節點值的位子，再用另外一個函式判斷兩者下面的部分一不一樣。
但是，我忽略了一個關鍵的情況:
小數對應到的1要是大樹的leaf node但是因為查找會先從大樹頭節點開始，**導致雖然值對，但是位置錯的情況**
因此，我們要traverse過整棵大樹，不能一看到可能的人選(值一樣但是不是該節點)就打住了
```python=
# 遍歷整個大樹並檢查是否存在與小樹相同的子樹
def traverse(root, subRoot):
if not root:
return False
if isSameTree(root, subRoot):
return True
return traverse(root.left, subRoot) or traverse(root.right, subRoot)
return traverse(root, subRoot)
```
:::
Sign in with Wallet
Connect another wallet