## leetcode刷題記錄
### 不做筆記的簡單題
[2535\. Difference Between Element Sum and Digit Sum of an Array](https://leetcode.com/problems/difference-between-element-sum-and-digit-sum-of-an-array/)
[2540\. Minimum Common Value](https://leetcode.com/problems/minimum-common-value/)
[2544\. Alternating Digit Sum](https://leetcode.com/problems/alternating-digit-sum/)
[2549\. Count Distinct Numbers on Board](https://leetcode.com/problems/count-distinct-numbers-on-board/)
[2582\. Pass the Pillow](https://leetcode.com/problems/pass-the-pillow/)
---
#### [482\. License Key Formatting](https://leetcode.com/problems/license-key-formatting/)
- 題目解釋
將licens進行重新排序，並使用分隔符號分隔，每個分隔階段只能有k個字母，唯獨第一段不受限制(僅需大於1即可)，輸出需將所有字串字母轉為大寫。
- 解題思路
需要分隔，直接聯想split，第一個可以不用滿足k，所以可以採用倒敘方式進行字串加法。
- 程式碼
```python=0
class Solution:
def licenseKeyFormatting(self, s: str, k: int) -> str:
t = s.split("-")
t = ''.join(t) #進行合併 -> 5F3Z2e9w
count = 0
ans = []
for i in range(len(t)-1,-1,-1):
count += 1
if(count%k==0):
ans.append(t[-k:])
ans.append("-")
t = t[:-k]
if(len(t)<k):
ans.append(t)
break
ans = ans[::-1]
ans = ''.join(ans)
if(len(ans)!=0 and ans[0]=="-"):
return ans[1:].upper()
return ans.upper()
```
- 遇到問題
1. 因為不之原因測資修改，而跑出錯誤(明明預期跟output一樣)，後續查看discussion也有同樣問題，說明只要重置測資就可以。
2. 會有"---"、k=3的測資出現，此為輸出""即可(但題目沒有詳細說明，且測試時會一直卡住不過。
- 新學習
可以使用upper()或lower()將字串轉為大小寫
- 時間複雜度
- 空間複雜度
---
#### [495\. Teemo Attacking](https://leetcode.com/problems/teemo-attacking/)
- 題目解釋
攻擊方會每隔幾秒進行攻擊，被攻擊者則會持續幾秒中毒，最終要計算出被攻擊者中毒的時間。
- 解題思路
從測資來看會發現，如果攻擊間距小於攻擊發動的間隔，那被攻擊者中毒的秒數就會變少，所以從這點來看我們可以找出重疊的時間在哪，利用max方式進行找尋，如果不再範圍內那就用list進行記錄。
- 程式碼
```python=1
class Solution:
def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
a = []
l = timeSeries[0]
r = l + duration
for i in range(1,len(timeSeries)):
if(timeSeries[i]<=r):
r = max(timeSeries[i] + duration,r)
elif(timeSeries[i] > r):
a.append([l,r])
l = timeSeries[i]
r = l + duration
total = 0
a.append([l,r])
for [k,v] in a:
total += (v-k)
return total
```
#### [682\. Baseball Game](https://leetcode.com/problems/baseball-game/)
- 題目解釋
主要會遇到四種類型輸入，分別有+、D、C以及數字，這些都是使用字串進行存取，遇到數字要把數字放入陣列，遇到加號需要把最後兩位數字相加放入陣列，遇到D需要把最後一位乘上二放入陣列，最後遇到C則是把陣列中最後一位數字進行移除。
- 解題思路
遇到需要最後一位的數字，可使用陣列的pop()方式，將最後一位取出進行動作。
- 程式碼
```python=1
class Solution:
def calPoints(self, operations: List[str]) -> int:
ans = 0
stack = []
for i in range(len(operations)):
if(operations[i] == "+"):
temp = stack.pop()
temp2 = stack.pop()
stack.append(temp2)
stack.append(temp)
stack.append(temp + temp2)
elif(operations[i] == "D"):
temp = stack.pop()
stack.append(temp)
stack.append(temp * 2)
elif(operations[i] == "C"):
stack.pop()
else:
stack.append(int(operations[i]))
for i in range(len(stack)):
ans += stack[i]
return ans
```
- 遇到問題
原以為需要考量stack長度問題，但題目中已說明會確保這些問題不存在，因此沒多做考量。
- 新學習
無
- 時間複雜度
- 空間複雜度
#### [338\. Counting Bits](https://leetcode.com/problems/counting-bits/)
- 題目解釋
給定一個十進位數字n，將0~n轉換為二進位，並計算出二進位後的1佔有幾位。
- 解題思路
轉換為二進位直接使用bin()，計算特定出現的字元，可用count()進行計算。
- 程式碼
```python=1
class Solution:
def countBits(self, n: int) -> List[int]:
ans = []
for i in range(0,n+1):
ans.append(bin(i).count("1"))
return ans
```
- 遇到問題
無
- 新學習
1. bin()所花的時間複雜度為O(log n)
https://stackoverflow.com/questions/50793388/time-complexity-of-bin-in-python
https://github.com/python/cpython/blob/6405feecda6a5d5dd7a4240eb3054a2676ed29b1/Objects/longobject.c#L1851
2. count()所花的時間複雜度為O(n)
https://stackoverflow.com/questions/44812468/what-is-the-time-complexity-of-python-lists-count-function
- 時間複雜度
- 空間複雜度
[455\. Assign Cookies](https://leetcode.com/problems/assign-cookies/)
- 題目解釋
- 解題思路
- 程式碼
- 遇到問題
- 新學習
- 時間複雜度
- 空間複雜度
[338\. Counting Bits](https://leetcode.com/problems/counting-bits/)
- 題目解釋
計算出重複次數最多的數字的子集，例如[1,2,3,1,1]，1出現次數最多，那找出陣列中最小的子集，這個子集要能包含三個1，所以就會是選擇最前面跟最後面為[1,2,3,1,1]，但如果今天測資是[1,2,2,2,1,1]，1跟2出現同樣次數，那就找他們最小子集能夠包含1或是能夠包含2，所以答案會是[2,2,2]，最後輸出子集長度。
- 解題思路
首先是要找出出現次數，所以選用python提供的collections的Counter，他會直接輸出每一個元素出現的數字，但也能改用dict()迭代進行計算。
接著，是找出最小子集，所以可以觀察到只要計算出出現次數最頻繁的頭尾index，就能記錄出最小子集的長度為何。
- 程式碼
```python=1
from collections import Counter
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
x = Counter(nums)
a = dict()
b = dict()
for i in range(len(nums)):
if(a.get(nums[i])==None):
a[nums[i]]=i
for i in range(len(nums)-1,-1,-1):
if(b.get(nums[i])==None):
b[nums[i]]=i
large = 0
ans = float('inf')
x_sort= sorted(x.items(),key= lambda kv:kv[1],reverse=True)
for (k,v) in x_sort:
if(v>=large):
large = v
temp = b[k]-a[k] + 1
if(temp<ans):
ans = temp
else:
break
return ans
```
- 遇到問題
主要是需要思路清晰，很容易忽視其中需要的步驟。
- 新學習
無
- 時間複雜度
- 空間複雜度
#### [1828\. Queries on Number of Points Inside a Circle](https://leetcode.com/problems/queries-on-number-of-points-inside-a-circle/)
- 題目解釋
給定點的位置，以及給定圓心位置與圓的半徑大小，最後判斷每個圓裡面有多少個點。
- 解題思路
想到有個數學定理能夠解決這問題，此為勾股定理，(x1-x2)^2+(y1-y2)^2<r^2，x2跟y2為圓心，小於為圓內，等於為邊上。以此下去解題。
- 程式碼
```python=1
class Solution:
def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
# (x1-x2)^2+(y1-y2)^2<r^2，x2跟y2為圓心，小於為圓內，等於為邊上
ans = []
for x2,y2,r in queries:
total = 0
for x1,y1 in points:
if(((x1-x2)**2 + (y1-y2)**2)<= r**2):
total += 1
ans.append(total)
return ans
```
- 遇到問題
無
- 新學習
學習不要C style進行解題
- 時間複雜度
- 空間複雜度
#### [1329\. Sort the Matrix Diagonally](https://leetcode.com/problems/sort-the-matrix-diagonally/)
- 題目解釋
把陣列依照對角線進行排序
- 解題思路
可以知道對角線的座標相減為同個數字，那只需要把數字記錄下來，進行後續排序即可，接著，在進行讀取放入回陣列中。
- 程式碼
```python=1
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
a = defaultdict(list)
for i in range(len(mat)):
for j in range(len(mat[i])):
a[i-j].append(mat[i][j])
for i in a:
a[i].sort(reverse=True)
for i in range(len(mat)):
for j in range(len(mat[i])):
mat[i][j] = a[i-j].pop()
return mat
```
- 遇到問題
用想的很簡單，但實際上該如何把list用在dict中，後來找到原來defaultdict(list)可以進行使用，這樣就能在dict讀取時進行排序。
- 新學習
defaultdict(list)
- 時間複雜度
- 空間複雜度
#### [2433\. Find The Original Array of Prefix Xor](https://leetcode.com/problems/find-the-original-array-of-prefix-xor/)
- 題目解釋
已知前一個list的XOR prefix sum，那要如何知道原本的list?
- 解題思路
了解xor特性，5^7=2、5^2=7、2^7=5，看題目會知道例如list_xor=[5,2,7,3,1]，那5是原本跟0的xor數字可以先跳過，接著看2，2為5^x=2，所以x為7，接著7為2^x=7，所以x為5，再來3為7^x=3，x=4，以此類推，得出[5,7,5,4,2]
- 程式碼
```python=1
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
ans = [pref[0]]
if(len(pref)==1):
return ans
for i in range(1,len(pref)):
ans.append(pref[i-1]^pref[i])
return ans
```
- 遇到問題
有觀察到這個特性，但不太確定原因，所以寫了一下數學算式即可得知。
- 時間複雜度
- 空間複雜度
#### [1652\. Defuse the Bomb](https://leetcode.com/problems/defuse-the-bomb/)
- 題目解釋
給定list跟k，輸出前k個大小(k<0)，輸出list後k個大小(k>0)。
- 解題思路
因為每個list位置都得計算一次，所以一定會走遍整個list，因此我們可以先算出每k個的sum，算完之後在找出k會從哪個位置開始，進行輸出。
- 程式碼
```python=1
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
if(k == 0):
return [0] * len(code)
ans = []
count = abs(k)
for i in range(len(code)):
if (i+count) < len(code):
ans.append(sum(code[i:i+count]))
else:
ans.append(sum(code[i:len(code)])+sum(code[0:count-(len(code)-i)]))
if(k > 0):
ans.append(ans[0])
return ans[1:len(ans)]
elif(k < 0):
return ans[k:len(ans)]+ans[0:len(ans)+k]
```
- 新學習
不確定sum可不可以進行陣列計算，查詢之後是可以，以及花費的複雜度為O(n)，其中n的大小取決於所需要統計的陣列大小。
- 時間複雜度
O(N)
- 空間複雜度
O(N)
#### [1694\. Reformat Phone Number](https://leetcode.com/problems/reformat-phone-number/)
- 題目解釋
給定一串字串，裡面包含"-" 及" "，依照電話號碼數量進行分隔。
- 解題思路
先將"-"以及" "去除，接著依照固定格式進行判斷並加上分隔符號即可。
- 程式碼
```python=1
class Solution:
def reformatNumber(self, number: str) -> str:
ans = []
new_number = []
for i in number:
if(i != "-" and i != " "):
new_number.append(i)
new_number = "".join(new_number)
count = len(new_number)
i = 0
while(count > 4):
ans.append(new_number[i:i+3])
ans.append("-")
i = i + 3
count = count - 3
if(count == 0):
ans = ans[:-1]
elif(count == 1):
ans.append(new_number[i])
elif(count == 2):
ans.append(new_number[i:i+2])
elif(count == 3):
ans.append(new_number[i:i+3])
elif(count == 4):
ans.append(new_number[i:i+2])
ans.append("-")
ans.append(new_number[i+2:i+4])
ans_str = "".join(ans)
return ans_str
```
- 遇到問題
- 新學習
要注意split不能連用兩次，因為第二次已經是list了，複雜度為O(N)。
- 時間複雜度
O(N)
- 空間複雜度
O(N)
#### [113\. Path Sum II](https://leetcode.com/problems/path-sum-ii/)
- 題目解釋
DFS相關
- 解題思路
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
def dfs(root,path,num):
if(root == None):
return
num = num + root.val
if(root.left == None and root.right==None and num == targetSum):
res.append(path+[root.val])
if(root.left == None and root.right!=None):
dfs(root.right,path+[root.val],num)
if(root.left != None and root.right==None):
dfs(root.left,path+[root.val],num)
if(root.left != None and root.right!=None):
dfs(root.left,path+[root.val],num)
dfs(root.right,path+[root.val],num)
dfs(root,[],0)
return res
```
- 遇到問題
- 新學習
- 時間複雜度
- 空間複雜度
#### [199\. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)
- 題目解釋
BFS
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
import queue
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if(not root):
return ans
q = queue.Queue()
q.put(root)
while(q.qsize()):
l = q.qsize()
for i in range(l):
x = q.get()
if(x.left):
q.put(x.left)
if(x.right):
q.put(x.right)
if(i == (l-1)):
ans.append(x.val)
return ans
```
#### [230\. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
- 題目解釋
中序遍歷(inorder)
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
a = []
def dfs(root):
if(root.left):
dfs(root.left)
a.append(root.val)
if(root.right):
dfs(root.right)
dfs(root)
return a[k-1]
```
#### [96\. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)
卡特蘭數
- 解題思路
1,1,2,5,14,42,,,,
```python=1
class Solution:
def numTrees(self, n: int) -> int:
#catalan c2n取n/(n+1)=>c10取5/6
mosum = 1
sonsum = 1
for i in range(2*n,n,-1):
mosum *= i
for i in range(n,0,-1):
sonsum *= i
return int(int(mosum/sonsum)/int(n+1))
```
#### [171\. Excel Sheet Column Number](https://leetcode.com/problems/excel-sheet-column-number/)
- 題目解釋
計算出excel是第幾個column
- 解題思路
直接從後面倒數，然後看是第幾個就乘幾次26
- 程式碼
```python=1
class Solution:
def titleToNumber(self, s: str) -> int:
ans = 0
for i in range(len(s)-1,-1,-1):
ans = ans + (ord(s[i])-64)*(26**(len(s)-1-i))
return ans
```
#### [168\. Excel Sheet Column Title](https://leetcode.com/problems/excel-sheet-column-title/)
- 題目解釋
上一題倒過來解，但是要注意%之後會少一
- 解題思路
- 程式碼
```python=1
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
s = []
while(columnNumber!=0):
n = columnNumber%26
if(n == 0):
columnNumber = (columnNumber-26) / 26
else:
columnNumber = (columnNumber-n) / 26
if(n == 0):
s.append("Z")
else:
s.append(chr(int(n)+64))
s = "".join(s[::-1])
return s
```
#### [628\. Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/)
- 題目解釋
- 解題思路
用貪婪演算法，直接找出可能的最大值
- 程式碼
```python=1
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
if(len(nums)==3):
return nums[0]*nums[1]*nums[2]
nums.sort()
n = len(nums)
return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1])
```
#### [654\. Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/)
- 題目解釋
給定list建構binary tree
- 解題思路
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if(len(nums)==0):
return
def dfs(nums):
if(len(nums)==0):
return
mx = max(nums)
mxi = nums.index(mx)
a = TreeNode(mx)
a.left=dfs(nums[:mxi])
a.right=dfs(nums[mxi+1:])
return a
return dfs(nums)
```
#### [796\. Rotate String](https://leetcode.com/problems/rotate-string/)
- 題目解釋
- 解題思路
旋轉題目一律先想到將目標進行相加
- 程式碼
```python=1
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if(len(s)==len(goal) and goal in (s+s)):
return 1
return 0
```
#### [606\. Construct String from Binary Tree](https://leetcode.com/problems/construct-string-from-binary-tree/)
- 題目解釋
給定一個tree，根據輸入的部分輸出括號
- 解題思路
直接聯想到dfs，並在每個遞迴前用括號包住
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
ans = []
def dfs(root):
if(root == None):
ans.append("()")
ans.append(str(root.val))
if(root.left==None and root.right):
ans.append("()")
if(root.left):
ans.append("(")
dfs(root.left)
ans.append(")")
if(root.right):
ans.append("(")
dfs(root.right)
ans.append(")")
dfs(root)
s = "".join(ans)
return s
```
#### [872\. Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/)
- 題目解釋
對比兩棵樹的葉子，查看數字是否一樣
- 解題思路
直接使用dfs紀錄兩邊葉子
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
ans = []
ans2 = []
def dfs(root):
if(root==None):
return
if(root.right == None and root.left == None):
ans.append(root.val)
if(root.right):
dfs(root.right)
if(root.left):
dfs(root.left)
def dfs2(root):
if(root==None):
return
if(root.right == None and root.left == None):
ans2.append(root.val)
if(root.right):
dfs2(root.right)
if(root.left):
dfs2(root.left)
dfs(root1)
dfs2(root2)
return ans==ans2
```
#### [965\. Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)
- 題目解釋
找出是否有不一樣的數字存在tree中
- 解題思路
直接使用dfs紀錄所有節點
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
ans = []
def dfs(root):
if(root==None):
return
ans.append(root.val)
if(root.left):
dfs(root.left)
if(root.right):
dfs(root.right)
dfs(root)
for i in range(1,len(ans)):
if(ans[0]!=ans[i]):
return False
return True
```
#### [1022\. Sum of Root To Leaf Binary Numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/)
#### [108\. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)
- 題目解釋
給定sorting array建立出BST
- 解題思路
直接使用遞迴方式建樹，並從中找出每個array出現時的中間數
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
r = len(nums)-1
l = 0
def con(num,l,r):
if(l>r):
return None
medi = int((r-l)/2) + l
root = TreeNode(num[medi])
root.left = con(num,l,medi-1)
root.right = con(num,medi+1,r)
return root
return con(nums,l,r)
```
#### [173\. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)
- 題目解釋
將inorder寫成class形式
- 解題思路
先找出inoder的array，接著直接用array判斷即可
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.root = root
self.ans = []
def dfs(root):
if(root.left):
dfs(root.left)
self.ans.append(root.val)
if(root.right):
dfs(root.right)
dfs(self.root)
def next(self) -> int:
if(len(self.ans)!=0):
a = self.ans[0]
self.ans = self.ans[1:]
return a
def hasNext(self) -> bool:
if(len(self.ans)!=0):
return True
else:
return False
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
```
#### [341\. Flatten Nested List Iterator](https://leetcode.com/problems/flatten-nested-list-iterator/)
#### [637\. Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/)
- 題目解釋
計算每一層的節點數值並輸出平均
- 解題思路
直接使用bfs進行遍歷
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
import queue
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
q = queue.Queue()
q.put(root)
ans = []
while(q.qsize()):
temp = 0
n = 0
l = q.qsize()
for i in range(l):
x = q.get()
if(x.right):
q.put(x.right)
if(x.left):
q.put(x.left)
temp += x.val
n += 1
ans.append(temp / n)
return ans
```
#### [623\. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/)
- 題目解釋
給定val跟depth並從中插入至tree中
- 解題思路
使用level travelsal 進行判斷與插入，但要注意有例外，如果當插入的為根節點，那原先節點要插入至左邊。
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
import queue
class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if(depth == 1):
x = TreeNode(val)
x.left = root
return x
q = queue.Queue()
q.put(root)
n = 1
while(q.qsize()):
l = q.qsize()
n += 1
for i in range(l):
x = q.get()
if(n == depth):
if(x.left):
temp = x.left
x.left = TreeNode(val)
x.left.left = temp
else:
print(x.val)
x.left = TreeNode(val)
if(x.right):
temp = x.right
x.right = TreeNode(val)
x.right.right = temp
else:
x.right = TreeNode(val)
else:
if(x.left):
q.put(x.left)
if(x.right):
q.put(x.right)
return root
```
#### [143\. Reorder List](https://leetcode.com/problems/reorder-list/)
- 題目解釋
照題目意思將linkedlist位置進行變換
- 解題思路
找出規律，會發現是把arr中的內容最後面->最前面->最後面...等於是實作一個array把前後元素拿出來替換。
- 程式碼
```python=1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if(head.next == None):
return
a = []
pre = head
aft = head.next
while(pre):
a.append(pre.val)
pre = pre.next
a = a[1:]
n = 1
while(aft):
if(n%2==0):
aft.val = a[0]
if(len(a)>1):
a = a[1:]
else:
aft.val = a.pop()
aft = aft.next
n += 1
```
#### [225\. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)
- 題目解釋
實作stack
- 解題思路
實作stack
- 程式碼
```python=1
class MyStack:
def __init__(self):
self.stac = []
def push(self, x: int) -> None:
self.stac.append(x)
def pop(self) -> int:
r = self.stac[-1]
self.stac = self.stac[:-1]
return r
def top(self) -> int:
return self.stac[-1]
def empty(self) -> bool:
if(len(self.stac)==0):
return True
return False
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
```
#### [921\. Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/)
- 題目解釋
判斷如果要達成符合規則的括號，最小需添加的次數
- 解題思路
直接使用stack進行判斷，如果遇到右括號，前面一個是左括號直接pop掉
- 程式碼
```python=1
class Solution:
def minAddToMakeValid(self, s: str) -> int:
a = []
for i in s :
if(len(a)!= 0):
x = a.pop()
if(i == ")" and x=="("):
pass
else:
a.append(x)
a.append(i)
else:
a.append(i)
return len(a)
```
#### [856\. Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/)
- 題目解釋
需依照題目給的規則下去計算括弧中最後得出的分數
- 解題思路
使用Stack進行判斷，如果前一個為數字則相加之後如果為"("則進行乘2，如果一開始則遇到括弧直接放入數字1，最後再計算陣列中的總合。
- 程式碼
```python=1
class Solution:
def scoreOfParentheses(self, s: str) -> int:
stac = []
for i in s:
temp = 0
if(i == ")"):
x = stac[-1]
if(x=="("):
stac.pop()
stac.append(1)
else:
temp = 0
while(stac[-1]!="("):
x = stac.pop()
temp += x
stac.pop()
stac.append(temp*2)
elif(i == "("):
stac.append("(")
return sum(stac)
```
- 新學習
可以改用[-1]先查看stack的尾端，再決定要不要pop()
#### [1381\. Design a Stack With Increment Operation](https://leetcode.com/problems/design-a-stack-with-increment-operation/)
- 題目解釋
(實作題)依照題目定義實作出兩種基本stack操作，以及增加increment函式
- 解題思路
無
- 程式碼
```python=1
class CustomStack:
def __init__(self, maxSize: int):
self.stac = []
self.maxSize = maxSize
def push(self, x: int) -> None:
if(len(self.stac)<self.maxSize):
self.stac.append(x)
def pop(self) -> int:
if(len(self.stac)!=0):
ans = self.stac[-1]
self.stac = self.stac[:-1]
return ans
else:
return -1
def increment(self, k: int, val: int) -> None:
for i in range(0,min(k,len(self.stac))):
self.stac[i] += val
# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)
```
#### [1441\. Build an Array With Stack Operations](https://leetcode.com/problems/build-an-array-with-stack-operations/)
- 題目解釋
給定一個target並且限制最大數量，看如何push跟pop能夠達到跟target一樣
- 解題思路
觀察法可以直接發現，當有遺漏的數字，即可加入push pop，如果沒有遺漏則是push
- 程式碼
```python=1
class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
ans = []
num = 0
for i in range(1,min(n+1,target[-1]+1)):
if(target[num]==i):
ans.append("Push")
num+=1
else:
ans.append("Push")
ans.append("Pop")
return ans
```
#### [1544\. Make The String Great](https://leetcode.com/problems/make-the-string-great/)
- 題目解釋
如果相鄰的兩個字母為大小寫，則進行刪除
- 解題思路
直接使用stack解，遇到前一個為大小寫的直接pop掉
- 程式碼
```python=1
class Solution:
def makeGood(self, s: str) -> str:
stac = []
for i in s:
if(len(stac)== 0):
stac.append(i)
else:
if(abs(ord(stac[-1])-ord(i))==32):
stac.pop()
else:
stac.append(i)
stac = "".join(stac)
return stac
```
#### [2903\. Find Indices With Index and Value Difference I](https://leetcode.com/problems/find-indices-with-index-and-value-difference-i/)
- 題目解釋
需要找出index與value相差值在規定範圍內的index
- 解題思路
直接照題目規定，使用雙迴圈進行解題，一一找出符合規範的值
- 程式碼
```python=1
class Solution:
def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
ans = []
for i in range(len(nums)):
for n in range(i + indexDifference,len(nums)):
if(n<len(nums)):
if(abs(nums[i]-nums[n])>=valueDifference):
ans.append(i)
ans.append(n)
if(len(ans)==0):
return [-1,-1]
return ans
```
#### [701\. Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/)
- 題目解釋
將題目給定val插入至bst當中
- 解題思路
直接往下遞迴檢查，如果發現為空則插入node
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
def dfs(root,val):
if(root==None):
return TreeNode(val)
elif(val>root.val):
root.right = dfs(root.right,val)
elif(val<root.val):
root.left = dfs(root.left,val)
return root
return dfs(root,val)
```
#### [1266\. Minimum Time Visiting All Points](https://leetcode.com/problems/minimum-time-visiting-all-points/)-每日題目
- 題目解釋
找出到下一個points時需要多少步數能夠達到
- 解題思路
觀察法能夠看出只要找出相減後最大的值即為所需步數
- 程式碼
```python=1
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
total = 0
for i in range(1,len(points)):
total = total+max(abs(points[i][0]-points[i-1][0]),abs(points[i][1]-points[i-1][1]))
return total
```
#### [405\. Convert a Number to Hexadecimal](https://leetcode.com/problems/convert-a-number-to-hexadecimal/)
- 題目解釋
將十進位轉為十六進位
- 解題思路
包含負數，因此需要考量二補數，直接將補數先行加上負數進行計算
- 程式碼
```python=1
class Solution:
def toHex(self, num: int) -> str:
list_hex = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"]
ans = []
if(num<0):
x = 16**8
num = num + x
while(num>=16):
ans.append(list_hex[num%16])
num = num // 16
ans.append(list_hex[num])
ans = ans[::-1]
ans = "".join(ans)
return ans
```
####
- 題目解釋
分享餅乾，每個array代表因子，進行餅乾分配
- 解題思路
使用迴圈紀錄所在位置，遇到符合的將後退一格
- 程式碼
```python=1
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
i,j,ans = 0,0,0
g.sort()
s.sort()
while(j<len(s) and i<len(g)):
if(s[j]>=g[i]):
ans += 1
i += 1
j += 1
return ans
```
#### [830\. Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/)
- 題目解釋
找出連續出現三次以上的字母位置起始點跟終點
- 解題思路
直接紀錄位置一一判斷
- 程式碼
```python=1
class Solution:
def largeGroupPositions(self, s: str) -> List[List[int]]:
start,end = 0,1
ans = []
while(end<len(s) and start<len(s)):
if(s[start]==s[end]):
end += 1
else:
if((end-start)>=3):
end -= 1
ans.append([start,end])
start = end
end += 1
if((end-start)>=3):
end -= 1
ans.append([start,end])
return ans
```
#### [824\. Goat Latin](https://leetcode.com/problems/goat-latin/)
- 題目解釋
將字串進行轉換，如果第一個字母為子音，則對調到最後一個字母，每一個字後面都要加上ma，並依照字串數量加上a
- 解題思路
判斷子音及母音，並且計算出現的數量，之後就是進行字串的程式撰寫
- 程式碼
```python=1
class Solution:
def toGoatLatin(self, sentence: str) -> str:
s = sentence.split(" ")
alpha = ["a","e","i","o","u","A","E","I","O","U"]
num = 1
space = " "
ans = []
for i in s:
num += 1
if(i[0] in alpha):
st = i+"m"+"a"*num
else:
st = i[1:]+i[0]+"m"+"a"*num
ans.append(st)
ans.append(space)
ans = "".join(ans[:-1])
return ans
```
#### [859\. Buddy Strings](https://leetcode.com/problems/buddy-strings/)
- 題目解釋
判斷字串裡交換過一次之後可以等於目標字串即回傳True
- 解題思路
一定得交換一次，而且只能交換一次，因此需要考量一些情況，包含如果今天字母都只出現一次，s=abc、goal=abc，代表不管交換哪個都沒辦法再度等於abc
- 程式碼
```python=1
class Solution:
def buddyStrings(self, s: str, g: str) -> bool:
index = []
a = dict()
flag = 0
if(len(s)!=len(g) or len(s)==1):
return False
for i in range(len(s)):
if(s[i] not in a):
a[s[i]] = 1
else:
a[s[i]] += 1
flag = 1
if(s[i]!=g[i]):
index.append(i)
if(flag == 0 and len(index)==0):
return False
if(len(index)==0 or (len(index)==2 and s[index[0]]==g[index[1]] and s[index[1]]==g[index[0]])):
return True
else:
return False
```
#### [563\. Binary Tree Tilt](https://leetcode.com/problems/binary-tree-tilt/)
- 題目解釋
將左右子樹的總節點值進行相減並回傳
- 解題思路
使用遞迴方式，將值回傳
- 程式碼
```python=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTilt(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(root):
if(root==None):
return 0
left = dfs(root.left)
right = dfs(root.right)
self.ans += abs(left-right)
return left+right+root.val
dfs(root)
return self.ans
```
#### [598\. Range Addition II](https://leetcode.com/problems/range-addition-ii/)
- 題目解釋
給定矩陣大小，並給定後續需要陸續相加的矩陣位置，由內自外相加，最終回傳矩陣內最大值有幾個。
- 解題思路
找出重疊面積，也就是重疊的矩形，因為是由內到外，所以只需要紀錄每次最小的那個矩形即可，代表他重複最多次
- 程式碼
```python=1
class Solution:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
w = m
h = n
for i,j in ops:
w = min(i,w)
h = min(j,h)
return w*h
```
#### [1287\. Element Appearing More Than 25% In Sorted Array](https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/)
- 題目解釋
找出陣列中出現超過25%的值(只有唯一解)
- 解題思路
題目說過array是排序過的，那就代表有25%的區間是同一個值，因此使用指針指向，間隔25%找到一樣的值就回傳。
- 程式碼
```python=1
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
r = int(len(arr)//4)
l = 0
while(r<len(arr)):
if(arr[r]==arr[l]):
return arr[r]
r += 1
l += 1
return arr[r]
```
#### [541\. Reverse String II](https://leetcode.com/problems/reverse-string-ii/)
- 題目解釋
將固定數量的字串進行反轉
- 解題思路
直接使用python字串特性下去解題，並注意題目所說的條件
- 程式碼
```python=1
class Solution:
def reverseStr(self, s: str, k: int) -> str:
l = len(s)%(k)
temp = []
n = 1
for i in range(0,len(s)-l,k):
x = s[i:i+k]
if(n%2==1):
temp.append(x[::-1])
else:
temp.append(x)
n+=1
if(l<k):
x = s[len(s)-l:len(s)]
if(n%2==1):
temp.append(x[::-1])
else:
temp.append(x)
else:
x = s[-2*k:-l]
temp.append(x[::-1])
temp.append(s[l:-1])
ans = ''.join(temp)
return ans
```
#### [206\. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
- 題目解釋
反轉鏈結串列
- 解題思路
前中後節點進行儲存，並依序反轉
- 程式碼
```python=1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
post = None
while(cur):
post = cur.next
cur.next = pre
pre = cur
cur = post
return pre
```
#### [141\. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
- 題目解釋
查找鏈結串列是否有迴圈出現
- 解題思路
將節點數值往上加，發現超過原來範圍即為有迴圈出現
- 程式碼
```python=1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
while(head):
if(head.val >= 500000):
return True
head.val += 700000
head = head.next
return False
```
####
- 題目解釋
判斷是否為有效的括號規則
- 解題思路
使用堆疊進行判斷，找出互相對應的括號，必須要注意會有單括號的出現，如果只有一個open最後得判斷stack數量，反之只有一個close則得判斷中間pop時的stack數量。
- 程式碼
```python=1
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in s:
if(i == "(" or i == "[" or i == "{"):
stack.append(i)
else:
if(len(stack) == 0):
return False
if(stack[-1] == "(" and i ==")"):
stack.pop()
elif(stack[-1] == "[" and i =="]"):
stack.pop()
elif(stack[-1] == "{" and i =="}"):
stack.pop()
else:
return False
if(len(stack) != 0):
return False
return True
```
#### [1496\. Path Crossing](https://leetcode.com/problems/path-crossing/)
- 題目解釋
給定方位，並判斷是否會重複走到同一個點
- 解題思路
使用dict將東南西北進行紀錄，之後只需要使用set判斷是否為單一值即可
- 程式碼
```python=1
class Solution:
def isPathCrossing(self, path: str) -> bool:
dic = {"N":[0,1],"E":[1,0],"S":[0,-1],"W":[-1,0]}
cross = set()
dis = [0,0]
cross.add(tuple(dis))
for i in path:
dis[0] += dic[i][0]
dis[1] += dic[i][1]
if(tuple(dis) in cross):
return True
cross.add(tuple(dis))
return False
```
#### [92\. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/)
- 題目解釋
將Linked List進行範圍性的反轉並輸出
- 解題思路
用與Reverse Linked List I一樣的方式分成pre cur post，剩下僅需直接付值即可
- 程式碼
```python=1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
pre = None
cur = head
post = None
count = 1
ans = ListNode(1)
x = ans
flag = 0
while(cur):
if(count >= left and count <= right):
post = cur.next
cur.next = pre
pre = cur
cur = post
else:
if(pre and flag == 0):
while(pre):
ans.next = pre
ans = ans.next
pre = pre.next
flag =1
else:
ans.next = cur
ans = ans.next
cur = cur.next
count += 1
if(pre and flag == 0):
while(pre):
ans.next = pre
ans = ans.next
pre = pre.next
return x.next
```
#### [61\. Rotate List](https://leetcode.com/problems/rotate-list/)
- 題目解釋
旋轉linkedlist
- 解題思路
第一個迴圈計算數量，第二個迴圈將後半部分先記錄，第三個回圈則是補齊數量
- 程式碼
```python=1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if(not head or k == 0):
return head
temp = head
total = 0
while(temp):
temp = temp.next
total += 1
c = total - (k % total) + 1
if(total == 1 or k%total == 0):
return head
count = 1
cur = head
temp = head
while(temp):
if(c == count):
break
temp = temp.next
count += 1
count = 1
ans = temp
while(cur):
if(count < c):
while(temp.next):
temp = temp.next
temp.next = ListNode(cur.val)
temp = temp.next
cur = cur.next
count += 1
return ans
```
#### [238\. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)
- 題目解釋
將array內的內容改為其餘數字的乘積總和
- 解題思路
注意出現0時的狀況，並且記錄數量，如果大於2代表所有輸出為0，其餘數字僅需避開乘上0的情況
- 程式碼
```python=1
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
total = 1
zeroflag = 0
zerocount = 0
for i in nums:
if(i != 0):
total = total * i
else:
zeroflag = 1
zerocount += 1
if(zerocount >= 2):
return [0] * len(nums)
if(zerocount == len(nums)):
return nums
for i in range(len(nums)):
if(zeroflag == 1 and nums[i] != 0):
nums[i] = 0
elif(zeroflag == 1 and nums[i] == 0):
nums[i] = total
else:
nums[i] = total // nums[i]
return nums
```
#### [1897\. Redistribute Characters to Make All Strings Equal](https://leetcode.com/problems/redistribute-characters-to-make-all-strings-equal/)
- 題目解釋
經由互換字母之後是否可以讓所有word都長一樣
- 解題思路
使用dict紀錄所有字母出現次數，最後除上word長度即可
- 程式碼
```python=1
class Solution:
def makeEqual(self, words: List[str]) -> bool:
a = dict()
for i in words:
for j in range(len(i)):
if(i[j] in a):
a[i[j]] += 1
else:
a[i[j]] = 1
for x,y in a.items():
if y % len(words) != 0:
return False
return True
```
####
- 題目解釋
題目本身解釋不好，加上測試範例容易誤會，實際上是找出每個數字裡的最大數字，例如79最大為9，12最大為2，找出陣列中擁有相同最大數字並相加，最終將相加後最大數字輸出。
- 解題思路
分為兩個func，一個負責使用python套件count，找出最大數字為何，另一個則是去判斷相同者相加且最大數字總和為何。
- 程式碼
```python=1
class Solution:
def findmax(self,target: int) -> int:
num = [9,8,7,6,5,4,3,2,1]
for i in num:
if(str(target).count(str(i))>0):
return i
return 0
def maxSum(self, nums: List[int]) -> int:
ans = -1
temp = 0
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if(self.findmax(nums[i])==self.findmax(nums[j])):
ans = max(ans,nums[i]+nums[j])
return ans
```
#### [2807\. Insert Greatest Common Divisors in Linked List](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/)
- 題目解釋
給定linkedlist從中插入最大公因數
- 解題思路
最大公因數的解法先寫出，之後使用linkedlist的指標移動進行插入。
- 程式碼
```python=1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def gre(self,a,b):
if(a<b):
temp = a
while(temp>1):
if(b%temp==0 and a%temp==0):
return temp
temp -= 1
return temp
elif(a>b):
temp = b
while(temp > 1):
if(a%temp==0 and b%temp ==0):
return temp
temp -= 1
return temp
else:
return a
def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
a = head
if(a == None or a.next == None):
return a
while(a.next and a.next):
t = self.gre(a.val,a.next.val)
temp = a.next
a.next = ListNode(t)
a = a.next
a.next = temp
a = a.next
return head
```
#### [748\. Shortest Completing Word](https://leetcode.com/problems/shortest-completing-word/)
- 題目解釋
找出符合target字母的單字
- 解題思路
使用dict進行解題，中途如果為0，可以使用del進行刪除
- 程式碼
```python=1
class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
a = dict()
for i in licensePlate:
if(ord(i.lower())>=ord('a') and ord(i.lower())<=ord('z')):
if(i.lower() in a):
a[i.lower()] += 1
else:
a[i.lower()] = 1
minl = 25
ans = 0
for i in range(len(words)):
b = a.copy()
for j in range(len(words[i])):
if(words[i][j] in b):
b[words[i][j]] -= 1
if(b[words[i][j]] == 0):
del b[words[i][j]]
if(len(b) == 0 and len(words[i])<minl):
ans = words[i]
minl = len(words[i])
return ans
```
#### 2233. Maximum Product After K Increments
- 題目解釋
給定一段list，增加k次，使得陣列所有數字相成為最大
- 解題思路
可看出由小到大把最小數字往上加即可，但等於每次都需要重新排序，因此可以聯想到使用heap進行解題，每一次都把最小的pop，加完再push，最後，因為有可能數字太大，每次乘完都需要mod取餘數。
- 程式碼
```python=1
class Solution:
def maximumProduct(self, nums: List[int], k: int) -> int:
heapq.heapify(nums)
value = 10**9 + 7
for i in range(k):
temp = heapq.heappop(nums)
temp += 1
heapq.heappush(nums,temp)
total = 1
for i in range(len(nums)):
total = (total * nums[i]) % (10**9 + 7)
return total
```
<!-- ####
- 題目解釋
- 解題思路
- 程式碼
```python=1
```
- 遇到問題
- 新學習
- 時間複雜度
- 空間複雜度 -->
Sign in with Wallet
Connect another wallet