# Leetcode 筆記
###### tags: `Leetcode` `Job` `Algorithm`
* [共筆刷題 with 玫如 & 雅琦](https://hackmd.io/@ms0387120/rJ2BsR-1O/edit)
---
### Graph
* [Evaluate Division (Graph, 399)]()
> * Sol: Graph + DFS
> * [Code_CSDN](https://blog.csdn.net/fuxuemingzhu/article/details/82591165)
> * [REF_YT](https://www.youtube.com/watch?v=UwpvInpgFmo)
> * 時間複雜度較慢: O(E+q*e)
> * 先依照題目資料建立好 Graph ，若題目要求由A走向C，就把路徑列出來，在把經過的權重都相乘
> * 找不到路徑，就返回 -1
```python=
class Solution:
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
table = collections.defaultdict(dict)
# x: 起始節點; y: 終止節點
for (x, y), value in zip(equations, values):
table[x][y] = value # table[A][B] = k -> A/B = k
table[y][x] = 1.0 / value
# self.dfs(): 掃描所有的鍵圖(Graph)
# 拿出x&y，若沒有在圖裡面，就返回 -1
ans = [self.dfs(x, y, table, set()) if x in table and y in table else -1.0 for (x, y) in queries]
return ans
# dfs: 遞歸函數
def dfs(self, x, y, table, visited):
if x == y: # 若x==y，代表自己除自己，就是-1
return 1.0
visited.add(x) # SET visited: 確保不會重複返回節點，避免死循環
for n in table[x]:
if n in visited: # 就不做任何動作
continue
visited.add(n)
d = self.dfs(n, y, table, visited)
if d > 0:
return d* table[x][n]
return -1.0
```
### DFS&BFS
* [Number of Islands (DFS&BFS, 200)]()
```python=
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
"""
:type grid: List[List[str]]
:rtype: int
"""
m = len(grid) # m, n: 地圖的長寬
if m == 0:
return 0
n = len(grid[0])
ans = 0
# 雙層迴圈去遍歷所有位置
for y in range(m):
for x in range(n):
if grid[y][x] == '1': # 代表走道陸地，就用 dfs function開始遍歷該位置的上下左右位置
ans += 1
selfㄡ__dfs(grid, x, y, n, m)
return ans
def __dfs(self, grid, x, y, n, m):
if x<0 or y<0 or x>=n or y>=m or grid[y][x] == '0': # 若超出地圖邊界 or 走到海洋('0')不做任何動作直接return
return
grid[y][x] = '0' # 將陸地變成 '0'
self.__dfs(grid, x + 1, y, n, m) # 往上走
self.__dfs(grid, x - 1, y, n, m) # 往下走
self.__dfs(grid, x, y + 1, n, m) # 往左走
self.__dfs(grid, x, y - 1, n, m) # 往右走
```
### Linked List
* [Linked List Cycle II (LL, 142)]()
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if not fast or not fast.next:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return fast
```
* [Reorder List (LL, 143)]()
> * 轉成list後用index重新串成 LL
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 给定鍊表 1->2->3->4->5, 重新排列為 1->5->2->4->3.
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head: return
ltmp = []
cur = head
while cur: # 轉換成列表list
ltmp.append(cur)
cur = cur.next
n = len(ltmp) # list長度
# 藉由list的index，直接進行鏈接
for i in range(n // 2): # 處理
ltmp[i].next = ltmp[n - 1 - i]
ltmp[n - 1 - i].next = ltmp[i + 1]
ltmp[n // 2].next = None # 最后一個指向空
```
* [Palindrome Linked List (LL, Easy) (234, LL)]()
> * 存成list，再用 list == list[::-1] 判斷回文
```python=
# 題目: 判斷是不是一個回文LL
## Sol: 存成list,再用雙指針去判斷
# * Follow up: Could you do it in O(n) time and O(1) space?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
"""
:type head: ListNode
:rtype: bool
"""
vals = []
while head:
vals.append(head.val)
head = head.next # head 一道下一個指針
N = len(vals)
if (vals == vals[::-1]):
return True
else:
return False
```
* [Intersection of Two Linked Lists (160, LL)]()
* > 用環的方式思考,Ａ＆Ｂ互走若沒走到同個點，就是沒有intersection (巧解！)
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p1 = headA
p2 = headB
while p1 != p2:
if not p1: # 如果p1 已經走完(p1 為 None, not True)
# 交換到另一個ＬＬ做遍歷
p1 = headB
else: # 若有p1, 就繼續走到下一個點
p1 = p1.next
if not p2:
p2 = headA
else:
p2 = p2.next # 有p1, 就繼續走到下一個點
return p2
```
* [Add Two Numbers (2, LL)]()
> * 暴力解法
> * [Ref_CSDN](https://blog.csdn.net/fuxuemingzhu/article/details/79379626) 有另一個解法: 模擬加法
根據官方solution的方法，可以採用一個進位carry方便的完成一次遍歷得出結果，不過過程稍微麻煩。
```python=
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# 用字串的方法做處理
num1 = ''
num2 = ''
# 走遍 LL
while l1:
num1 += str(l1.val)
l1 = l1.next # 走到下一個點
# 走遍 LL
while l2:
num2 += str(l2.val)
l2 = l2.next
print('num1={} and num2={}'.format(num1, num2))
# num1=243 and num2=564
add = str(int(num1[::-1]) + int(num2[::-1]))[::-1]
print('add={}'.format(add)) # add=708
# 讓返回的東西也是 LL(題目要求，所以串回去)
head = ListNode(add[0])
answer = head
for i in range(1, len(add)):
node = ListNode(add[i])
print('node={}'.format(node))
# node=ListNode{val: 0, next: None}
# 下一個loop: node=ListNode{val: 8, next: None}
head.next = node
head = head.next
return answer
```
* [Linked List Cycle (141)]()
> * 題目只會給 head
> * O(1) conatant
> * 若是一個cycle,快慢一定會撞到
```python=
class Solution:
def hasCycle(self, head):
fast, slow = head, head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast == slow: # 兩指針撞到
return True
return False
```
* [Reverse Linked List (206)]()
```python=
# 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: ListNode) -> ListNode:
dummy = ListNode(float("-inf"))
# 代表while true
while head:
dummy.next, head.next, head = head, dummy.next, head.next
return dummy.next
```
## Tree
* [Binary Tree Level Order Traversal II (Tree, 107)]()
```python=
# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
# result: [3], [9, 20], [15, 7]
# return result[::-1]
if root is None:
return []
result, curr = [], [root] # curr是目前所遍歷到的 level，從root開始遍歷
# curr: 為當前走到的那一層的所有節點位置，而不是val
while curr:
# vals為輔助性list，來確保符合題意的 (return 為 from left to right)
next_level, vals = [], []
for node in curr:
vals.append(node.val) # node 是節點位置，要用 .val 才會是值
# 因為題目要求讀入要左到右，所以先判斷左子節點，在判斷右子節點
if node.left: # 該點有左子節點
next_level.append(node.left) # 加到下一層，為下一層要遍歷的節點
if node.right: # 該點有右子節點
next_level.append(node.right) # 加到下一層，為下一層要遍歷的節點
curr = next_level # 代表走到下一層
result.append(vals)
# result: [3], [9, 20], [15, 7]
# reuturn: result[::-1]
return result[::-1]
```
* [Minimum Depth of Binary Tree (Tree, 111)]()
```python=
# Leetcode 解答
# 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 minDepth(self, root: TreeNode) -> int:
"""
:type root: TreeNode
:rtype:int
"""
i = 0
# 下面那個 root 是讀入的 input
if root is None: # 代表left&right children不存在
return 0
# 若只有一個子節點
if root.left and root.right:
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1 # + 1 是加上 root 本身
else: # 帶有一邊的子樹長度為零(若return 這個會是錯的)，代表self.minDepth(root.left) 或 self.minDepth(root.right) 為零
return max(self.minDepth(root.left), self.minDepth(root.right)) + 1
```
* [Kth Smallest Element in a BST (Tree, 230)]()
```python=
# Def 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: TreeNode, k:int) -> int:
count=[] # 用來儲存 dfs 所遍歷的值(會從小到大)
self.dfs(root, count)
return count[k-1]
def dfs(self, node, count):
if not node:
return
self.dfs(node.left, count)
count.append(node.val)
self.dfs(node.right, count)
```
* [Serialize and Deserialize Binary Tree (Tree, 297)]()
> * 如果前序遍歷的過程中記錄下哪些位置是空節點的話，就是可以確定這棵樹的。LeetCode的官方樹的構建就是這樣的。因此，我們採用同樣的方法，只不過需要把空節點記錄下來。然後在反序列化時把它再變成空節點即可。
> * Runtime: 104 ms, faster than 95.59% of Python3 online submissions for Serialize and Deserialize Binary Tree.
> * Memory Usage: 18.6 MB, less than 90.79% of Python3 online submissions for Serialize and Deserialize Binary Tree.
```python=
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
vals = []
def preOrder(root):
if not root:
vals.append('#')
else:
vals.append(str(root.val))
preOrder(root.left)
preOrder(root.right)
preOrder(root)
return ' '.join(vals)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
vals = collections.deque(val for val in data.split())
def build():
if vals:
val = vals.popleft()
if val == '#':
return None
root = TreeNode(int(val))
root.left = build()
root.right = build()
return root
return build()
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
```
* [Binary Search Tree Iterator (Tree, 173)]()
> * stack
```python=
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
"""
:type root: TreeNode
"""
# 維護一個棧，從根節點開始，每次迭代地將根節點的左節點壓入棧，直到左節點為空為止。
self.stack = []
self.pushLeft(root)
# @return a boolean, whether we have a next smallest number
def hasNext(self):
return self.stack
# @return an integer, the next smallest number
def next(self):
# 調用next()方法時，彈出棧頂，如果被彈出的元素擁有右節點，則以右節點為根，將其左節點迭代壓棧。
top = self.stack.pop()
self.pushLeft(top.right)
return top.val
def pushLeft(self, node):
while node:
self.stack.append(node)
node = node.left
```
* [Convert Sorted List to Binary Search Tree (Tree, 109)]()
> * 先轉成list，再由中點分左右子樹去建平衡樹
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 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(object):
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if not head:
return None
nums = []
while head:
nums.append(head.val)
head = head.next
return self.sortedArrayToBST(nums)
def sortedArrayToBST(self,nums):
if not nums:
return None
mid=len(nums)//2
root=TreeNode(nums[mid])
root.left=self.sortedArrayToBST(nums[:mid])
root.right=self.sortedArrayToBST(nums[mid+1:])
return root
```
* [Convert Sorted Array to Binary Search Tree (108, Tree)]()
> * 以中間的值去分(因為已經排序好)，能把樹建的較平衡
```python=
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
_len = len(nums)
mid = _len // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
```
* [Lowest Common Ancestor of a Binary Search Tree (235, Tree)]()
* > * lowest node in T(Tree): 越靠近下面越low
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# EX: p=3, q=5
pointer = root
# 只要在 BST 裡面，就持續判斷
while pointer:
if p.val > pointer.val and q.val > pointer.val:
pointer = pointer.right # 就移到右邊子樹
elif p.val < pointer.val and q.val < pointer.val:
pointer = pointer.left # 就移到左邊子樹
else:
# 若p & q 都已經分別分到左右 or (p, q其中一個值 or 兩個值都跟root(pointer所在)一樣) 就return pointer.val
return pointer
```
* [Validate Binary Search Tree (98, Tree)]()
> * Sol: 遞歸解法
> * 定義一個輔助函數，要給這個輔助函數傳入當前要判斷的節點，當前要判斷的這個節點的取值下限和取值上限。然後使用遞歸即可，每次要計算下一個節點的時候都要根據這個節點是左孩子還是右孩子對其取值的區間進行更新。
> * Runtime: 44 ms, faster than 66.99% of Python3 online submissions for Validate Binary Search Tree.
> * Memory Usage: 16.4 MB, less than 79.28% of Python3 online submissions for Validate Binary Search Tree.
```python=
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.valid(root, float('-inf'), float('inf'))
def valid(self, root, min, max):
if not root:
return True
if root.val >= max or root.val <= min:
return False
# check 左子樹的最大值不會超過 root.val, 右子樹的最小值不會小於root.val
return self.valid(root.left, min, root.val) and self.valid(root.right, root.val, max)
```
* [Binary Tree Right Side View (199)]()
> * Hint: going level by level
```python=
# 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 rightSideView(self, root: TreeNode) -> List[int]:
result = []
level = [] # next level
queue = [root] # the level we currently on
while queue != [] and root is not None:
for node in queue:
if node.left:
level.append(node.left)
if node.right:
level.append(node.right)
# for-loop都跑完(跑到最後一個點)
result.append(node.val) # 確定加的是最右邊的點(因為跳出for-loop), 此時 node = 3
queue = level # 換到下一層
level = []
return result
```
* [Sum Root to Leaf Numbers (129)]()
> * Method: DFS
> [Ref_YT](https://www.youtube.com/watch?v=Gi0202QawRQ)
> [Code_YT](https://www.youtube.com/watch?v=tanL9EJVfrU)
```python=
# 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 sumNumbers(self, root: TreeNode) -> int:
if root == None:
return 0
# 因為在class裡面，所以都加上 self.
self.result = 0
self.findsum(root, 0)
return self.result
def findsum(self, root, val):
curr = val*10 + root.val
if root.left == None and root.right == None:
self.result += curr
# 因為已經更新到 result, 所以不用返回東西
return
# recursion
if root.left != None:
self.findsum(root.left, curr)
if root.right != None:
self.findsum(root.right, curr)
```
* [Binary Tree Paths (257)]()
> * Method 1: DFS (Better!)
> Runtime: 32 ms, faster than 72.32% of Python3 online submissions for Binary Tree Paths.
Memory Usage: 14.1 MB, less than 84.55% of Python3 online submissions for Binary Tree Paths.
```python=
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
"""
:tpye root:TreeNode
:rtype List[str]
"""
if not root:
return []
def tree_paths(node, path, res):
if not node:
return res
if not node.left and not node.right:
res.append(path)
return res
if node.left:
#若左節點不為空
tree_paths(node.left, path+f"->{node.left.val}", res)
if node.right:
tree_paths(node.right, path+f"->{node.right.val}", res)
return res
return tree_paths(root, f"{root.val}", [])
```
> * Method 2: DFS + Stack
> Runtime: 36 ms, faster than 40.16% of Python3 online submissions for Binary Tree Paths.
Memory Usage: 14.2 MB, less than 60.95% of Python3 online submissions for Binary Tree Paths.
```python=
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
"""
:tpye root:TreeNode
:rtype List[str]
"""
# DFS & stack
stack =[(root, "")] # 直接放進去parent: root, string用來更新每次路徑
res = [] # 這一定要有，因為要返回a list of string(:rtype List[str])
# Edge Case
if not root:
return []
# res: ["1->3", "1->2->5"]
# stack is not empty
while stack:
node, strr = stack.pop() # 從stack pop出來
# 若左右子節點都為空，就res append回去，因為已經走到最底
if not node.left and not node.right:
res.append(strr + str(node.val))
# 若還有左節點
if node.left:
# 按照上面對stack的設計，node.left會變成stack新的root
# strr + str(node.val) + "->" 會變成stack的 ""
stack.append((node.left, strr + str(node.val) + "->"))
# 同理
if node.right:
stack.append((node.right, strr + str(node.val) + "->"))
return res
```
* [Invert Binary Tree (226)]()
> * 這題簡單在 recursion 不用返回任何值
```python=
# 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 invertTree(self, root: TreeNode) -> TreeNode:
"""
:type root: TreeNode
:rtype TreeNode
"""
# Edge: 如果 root 沒有的時候，就向上層返回
if not root:
return
# Swap
temp = root.left # 儲存左節點
root.left = root.right
root.right = temp
# Recuesion: 每層樹要交換，交換完在往上一層(Recursion) ???
self.invertTree(root.left) # 先對 root.left 做遞歸
self.invertTree(root.right) # 再對 root.right 做遞歸
# Return: (:rtype TreeNode), 代表要求返回 TreeNode
return root
```
* [Binary Tree Level Order Traversal (102)]()
> * Sol_1: BFS, Time&Space: O(n)
> * pre-order: root-left-right, 考慮深度訊息depth, ans為另外空間存答案, 遞歸依定會先遍歷左子樹再右子樹
```python=
class Solution(object):
def levelOrder(self, root):
if root is None:
return []
queue = [root] # current level
next_queue = [] # next level
level = []
result = []
while queue != []:
for root in queue:
level.append(root.val) # 添加遍歷到的子節點值
if root.left is not None:
# 子節點的下層左節點若不為空，則加入下層next_queue.append
next_queue.append(root.left)
if root.right is not None:
next_queue.append(root.right)
result.append(level)
level = [] # clear level
queue = next_queue
next_queue = []
return result
```
> * Sol_2: DFS(深度搜索) + depth, 遞歸解法
> * DFS 不是按照層次遍歷的
```python=
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = [] # ans
self.level(root, 0, res) # 0為depth
return res
def level(self, root, level, res):
# 每次遞歸要保存節點的節點值res, level就是depth
# root 為空，就直接return，不做任何處理
if not root:
return
if len(res) == level:
res.append([]) # 動態添加ans新的行
res[level].append(root.val)
if root.left:
self.level(root.left, level + 1, res) # 先處理左子樹
if root.right:
self.level(root.right, level + 1, res) # 再處理右子樹
```
* [Binary Tree Postorder Traversal (145)]()
> * **Def of Postorder**: left, right, root
> * Note: recursion is easy, can you use iteratively?
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
if not root:
return []
result, stack = [], [(root, False)]
while stack:
curNode, visited = stack.pop()
if curNode:
if visited:
result.append(curNode.val)
else:
stack.append((curNode, True))
stack.append((curNode.right, False))
stack.append((curNode.left, False))
return result
```
* [Binary Inorder Traversal (94)]()
> * 影片有提供另一種方法: [Ref_YT](https://www.youtube.com/watch?v=RJhh3Jcc9zw&t=514s)
> * Runtime: 28 ms, faster than 85.77% of Python3 online submissions for Binary Tree Inorder Traversal.
> * Memory Usage: 14.3 MB, less than 49.64% of Python3 online submissions for Binary Tree Inorder Traversal.
```python=
# Recursion
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
```
* [Binary Tree Preorder Traversal (144)]()
* > Method)1: Recursion
```python=
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorderTraversal(self, root: TreeNode):
# without recursion
if root is None:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
```
* > Method_2: Iteration method, no recursion
```python=
class Solution:
# def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorderTraversal(self, root: TreeNode):
if root is None:
return []
# iteration method, no recursion
# stack: last in, first out
stack = [root]
result = []
while stack != []:
root = stack.pop()
result.append(root.val)
if root.right is not None:
stack.append(root.right)
if root.left is not None:
stack.append(root.left)
return result
```
* [Symmetric Tree (101)]()
> * Recursion (深度搜索)
```python=
# 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:
# 跟100. 給的東西不同@@
def isSymmetric(self, root: TreeNode) -> bool:
"""
:type root: TreeNode
:rtype: bool
"""
# 沒有子節點→root也算是對稱
if root is None:
return True
# 設立recursion help function: isSymmetricRecu()，來協助判斷是否對稱
# 比對root的左右子節點是否對稱
return self.isSymmetricRecu(root.left, root.right)
def isSymmetricRecu(self, left, right):
# 可以兩者為空
if left is None and right is None:
return True
# False: 結構上不對稱(left is None or right is None)，或者值不同(left.val != right.val)
if left is None or right is None or left.val != right.val:
return False
# 看左右節點的下一層子節點是否對稱 → 在call回來function: isSymmetric(self, left, right)
return self.isSymmetricRecu(left.left, right.right) and self.isSymmetricRecu(left.right, right.left)
```
* [Same Tree (100)]()
```python=
# Definition for a binary tree node. (leetcode會給定)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
# 從root往樹的下方判斷
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
"""
每次recursive: 判斷該節點本身&其左右子節點
:type p: TreeNode (某node左邊子節點的index)
:type q: Treenode (某node左邊子節點的index)
:rtype: bool
"""
# 代表左右兩個tree都已經走到 leaf(最後一個節點)
if p is None and q is None:
return True
if p is not None and q is not None:
# 判斷左右同個位置的節點值是否相同
# Tree 會搭配 recursive 方法
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
# 若都不是以上狀況，代表樹的左右分支結構不同→所以直接return False
return False
```
## Array
* [Move Zeroes (283)]()
```python=
# Notice j is the real index and i is actually the number of operation time.
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
length = len(nums)
i,j = 0,0
while(i < length):
if nums[j] == 0:
del nums[j]
nums.append(0)
i += 1
continue
j += 1
i += 1
* [Sort Colors (75)]()
> * mine: Success → 但效率不太好，且其實掃兩次XDD
> * Runtime: 48 ms, faster than 11.54% of Python3 online submissions for Sort Colors.
> * Memory Usage: 14.2 MB, less than 76.43% of Python3 online submissions for Sort Colors.
```python=
class Solution:
def sortColors(self, nums):
"""
Do not return anything, modify nums in-place instead.
"""
k = 0 # 外層指標
# 要開雙層迴圈: 內層是逐從左到右，兩兩比較
# 外層: 最左邊已經排好，下一次從次一個開始兩兩筆較
while k < len(nums):
# i: 內層指標
for i in range(1, len(nums)):
while nums[i-1] > nums[i]:
#if nums[i-1] > nums[i]:
nums[i-1], nums[i] = nums[i], nums[i-1]
#print(nums)
#print(k)
k+=1
return nums # 自己印出確認答案(題目要求in-place, 所以可以不用輸入這行)
```
### 正規解法: two pointer(zero, two) 且只遍歷一次
> * [Ref_YT](https://www.youtube.com/watch?v=aVOm2Kickys)
> * Runtime: 32 ms, faster than 77.82% of Python3 online submissions for Sort Colors.
> * Memory Usage: 14 MB, less than 98.67% of Python3 online submissions for Sort Colors.
```python=
class Solution:
#def sortColors(self, nums: List[int]) -> None:
def sortColors(self, nums):
"""
Do not return anything, modify nums in-place instead.
"""
if nums == None or len(nums) == 0:
return
zero = -1 # nums[0:zero] 都是放0
two = len(nums) # nums[two:len(nums)-1] 都是放2
i = 0 # 遍歷整個nums的指針
while (i < two):
if (nums[i] == 1):
i+=1
elif (nums[i] == 2):
two-=1 # 挪出一個空位放sensor到的2 (nums[i] == 2)
nums[i], nums[two] = nums[two], nums[i] # swap
else: # nums[i] == 0
zero+=1 # 挪出一個空位放sensor到的0 (nums[i] == 0)
nums[i], nums[zero] = nums[zero], nums[i] # swap
i+=1
```
* [Merge Sorted Array (88)]()
```python=
class Solution:
def merge(self, nums1, m, nums2, n):
nums1[m:] = nums2[:n] # 直接原地更改
nums1.sort()
print(nums1) # 可以用此來確定有沒有原地修改成功
```
* [Maximum Product Subarray (152)]()
> * mine: bug, substring可以很長，也可以為單一元素，改用以下sol
> * Runtime: 60 ms, faster than 38.08
of Python3 online submissions for Maximum Product Subarray.
> * Memory Usage: 14.5 MB, less than 41.20% of Python3 online submissions for Maximum Product Subarray.Runtime: 60 ms, faster than 38.08% of Python3 online submissions for Maximum Product Subarray.
```python=
class Solution:
def maxProduct(self, nums):
if nums == None or len(nums) == 0:
return 0
max_v = nums[0]
min_v = nums[0]
res = nums[0]
for i in range(1, len(nums)):
temp = max_v # 要記的另存，避免比較 min_v時被洗掉
# 已經考慮連乘的可能，因為乘積的最大和最小結果都存在max_v, min_v
max_v = max(max(max_v*nums[i], min_v*nums[i]), nums[i]) # nums[i]單一元素也算 substring
min_v = min(min(min_v* nums[i], temp*nums[i]), nums[i])
res = max(max_v, res)
return res
```
* [Product of Array Except Self (238)]()
> 總累乘 = 左累乘 * 右累乘 (不包括元素本身自己)
> * Runtime: 236 ms, faster than 81.73% of Python3 online submissions for Product of Array Except Self.
> * Memory Usage: 20.8 MB, less than 98.77% of Python3 online submissions for Product of Array Except Self.
> 
> 
```python=
class Solution:
def productExceptSelf(self, nums):
res = [1] * len(nums)
# left to right, 存取左邊累乘資料(由左到右遍歷)
res[0] = 1
for i in range(1, len(nums)):
res[i] = res[i-1]* nums[i-1]
# right to left, 存取左邊累乘資料(由右到左遍歷)
right = 1
# 因為不包含尾端，所以實際是從最後面跑到 index = 0 的位置
for i in range(len(nums)-1, -1, -1):
res[i] = res[i] * right # 左累乘 * 右累乘 = 總累乘
right = right * nums[i]
return res
```
* [Minimum Size Subarray Sum (209)]()
> Minimum Size Subarray 解法: Two pointer & Slinding Window
> [Ref_YT](https://www.youtube.com/watch?v=jp15K7dTCHc): Slinding Window解法
> Runtime: 68 ms, faster than 92.63% of Python3 online submissions for Minimum Size Subarray Sum.
> Memory Usage: 16.7 MB, less than 48.91% of Python3 online submissions for Minimum Size Subarray Sum.
>
```python=1
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
res = float('inf')
left = 0
total = 0
for i in range(len(nums)):
total += nums[i]
while (left <= i) and (total >= target):
res = min(res, i-left +1) # 比較並儲存最小的window寬度
total -= nums[left] # 左指針往右移時，總和要扣掉該元素
left += 1
return 0 if res == float('inf') else res
```
* [Merge Intervals (56)]()
```python=1
def merge(intervals):
result = []
intervals.sort(key=lambda x: x[0]) # 依照每個intervals的第一個數值去排序
i = 0
while i < len(intervals):
cur_start = intervals[i][0]
cur_end = intervals[i][1]
if result:
pre_start, prev_end = result[-1] # result[-1] 裡面是一個interval, ex: [1, 3]
# [[1, 4], [2, 3]]
hi = min(prev_end, cur_end) # min(4, 3) = 3
lo = max(pre_start, cur_start) # max(1, 2) = 2
# 以下為可merge的條件: 2 <= 3
if lo <= hi:
if cur_end > prev_end:
result[-1][1] = cur_end
# [[1, 3], [4, 6]]: 代表intervals是無法merge
# hi = 3, lo = 4
else:
# 所以就直接append進去
result.append(intervals[i])
else:
result.append(intervals[i])
i += 1 # 全部都遍歷完，就結束
return result
```
* [Insert Interval (57)]()
* > 講解影片超清楚 [Ref_YT](https://www.youtube.com/watch?v=E9IYRG_WYcM)
```python=1
class Solution(object):
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
result = []
i, n = 0, len(intervals)
# newInterval 與要比對的那個interval沒有重合(即newInterval最左邊[0]比 intervals最右邊沒有重合)
# 若有重合，就要跳出下面那個 while-loop
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# 若跳出overlap條件，就會跳出下面這個 while-loop
mI = newInterval;
while i < n and intervals[i][0] <= newInterval[1]:
# 以下為overlap時，更新新的newInterval(mI)
mI[0] = min(mI[0], intervals[i][0])
mI[1] = max(mI[1], intervals[i][1])
i += 1
## 把這個新的 mI 加到 result
result.append(mI)
## 前面都merge好後，剩下的要補貼上
while i < n:
result.append(intervals[i])
i += 1
return result
```
* [Patching Array (330)]()
> * 解題思路: [Ref_Web](https://www.cnblogs.com/grandyang/p/5165821.html)
> * Code: [Ref_Web](https://www.cnblogs.com/lightwindy/p/9563591.html)
> * Runtime: 60 ms, faster than 74.13% of Python3 online submissions for Patching Array.
> * Memory Usage: 14.6 MB, less than 16.08% of Python3 online submissions for Patching Array.
```python=1
class Solution:
def minPatches(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: int
"""
patch, miss, i = 0, 1, 0
while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]
i += 1
else:
miss += miss
patch += 1
return patch
```
* [Maximum Gap (164)]()
* > 另解: Bucket sort, Radix Sort(但效率都不甚好)
```python=1
def maximumGap(nums):
ans = 0
nums.sort() # 直接return sort好的 list
#print(len(nums))
if len(nums) < 2:
return 0
for i in range(len(nums)-1):
#print(i, ans)
ans = max(ans, nums[i+1] - nums[i])
return ans
```
* [Summary Ranges (228)]()
> * 是否有優化方法?
> * Runtime: 32 ms, faster than 57.56% of Python3 online submissions for Summary Ranges.
> * Memory Usage: 14.3 MB, less than 52.39% of Python3 online submissions for Summary Ranges.
> EX:
> [[0, 1, 2], [4, 5], [7]]
['0->2', '4->5', '7']
[[0], [2, 3, 4], [6], [8, 9, 9]]
['0', '2->4', '6', '8->9']
```python=1
def summaryRanges(nums):
if len(nums) == 0:
return []
if len(nums) == 1:
return [str(nums[0])]
# 遍歷每個，若該元素的下一個元素與該元素不連續，則這個list關閉，否則就繼續新增
ans_list = []
i = 0
while i < len(nums)-1:
tem = [nums[i]]
while (nums[i]+1) == (nums[i+1]):
tem.append(nums[i+1])
i += 1
if i == len(nums)-1:
if nums[i] == nums[i-1]+1:
ans_list.append(tem)
break
else:
ans_list.append([nums[i]])
break
else:
ans_list.append(tem)
i+=1
#print('i={}'.format(i)) # 此時的 i 已經是最後一個 nums 的 idx
# 對 nums 的最後一個元素做處理判斷
if nums[i] == nums[i-1]+1:
ans_list[-1].append(nums[i])
else:
ans_list.append([nums[i]])
#print(ans_list)
#return ans_list (要再轉換成下面那行，以符合題目要的答案格式)
return [str(i[0])+'->'+str(i[-1]) if len(i) != 1 else str(i[0]) for i in ans_list]
# 把每個list取頭尾後，轉成 string
```
* [Increasing Triplet Subsequence (334)]()
> * 遍歷每個時，只需維護更新當前最小&當前第二小的值就可以了(因為題目已經給定 Subsequence 的長度為3)
> * 若用 DP 方法，可以維護&儲存不同長度的 Subsequence(但 space complexity 就會變成 O(n))
```python=1
def increasingTriplet(nums):
# 邊界條件
if len(nums) <= 2:
return False
min1, min2 = float('inf'), float('inf') # 一開始設定極大值 → 才能後續做更新
for i in range(len(nums)):
curr = nums[i] # 當前數字
# case 3
if curr > min2:
return True
# case 1: curr比目前最小值還小 → 最小值做更新
elif (curr < min1):
min1 = curr # 更新最小的數 min1
# case 2: curr介於最小值和倒數第二小數值之間 → 倒數第二小做更新
elif (curr > min1 and curr < min2):
min2 = curr
# 若全部都遍歷完，卻沒有機會 return True 那就代表沒有組合滿足題目的 Subsequence → return False
return False
```
* [Trapping Rain Water (42)]()
```python=1
def trap(height):
if not height:
return 0
# DP to calculate leftMax and rightMax
# 從左邊計算過來
leftMax = [0] * len(height) # 初始化
leftMax[0] = height[0]
for i in range(1, len(height)):
leftMax[i] = max(leftMax[i - 1], height[i]) # 到目前該元素為止，左邊最高的高度(因為要比較該元素左邊和右邊最高高度)
# 從右邊計算過來(同理)
rightMax = [0] * len(height)
rightMax[len(height)-1] = height[-1]
for i in range(len(height)-2, -1, -1):
rightMax[i] = max(rightMax[i+1], height[i])
# 比較左右邊，較小值決定該磚塊上面能存多少水
res = 0
for i in range(len(height)):
res += min(leftMax[i], rightMax[i]) - height[i]
return res
```
* [Best Time to Buy and Sell Stock with Cooldown (309)]()
* > DP Sol
[Ref_YT完整影片](https://www.youtube.com/watch?v=Ggzbo9eVrLU)
```python=1
def maxProfit(prices):
n = len(prices)
if n <= 1:
return 0
# 創建空間以遍歷prices 來儲存所有值
hold = [0 for _ in range(n)]
unhold = [0 for _ in range(n)] # 第一天不持有股票，最大profit一定 = 0 (因為沒有進行任何操作)
hold[0] = -prices[0] # 第一天若有操作，一定是買入操作(所以值為負，因為花錢出去了)
hold[1] = max(hold[0], -prices[1])
unhold[1]= max(unhold[0], hold[0] + prices[1])
for i in range(2, n):
hold[i] = max(hold[i-1], unhold[i-2] - prices[i])
# 可能的狀態: (hold[i - 1]: 第 i-1 天買入 ;
# unhold[i - 2] - prices[i]: 今天才買入,且要買新的舊的一定要先賣掉，且賣掉又須停一天，所以只能是第 i-2 天賣掉)
unhold[i] = max(unhold[i-1], hold[i-1] + prices[i])
# 可能的狀態: (unhold[i - 1]: 昨天就沒持有股票；
# hold[i - 1] + prices[i]: 昨天持有，但今天賣掉
# 所求: 最後一天不持有股票的最大價值 (要記得 n - 1 才會式最後一筆)
return unhold[n-1]
```
* [Container With Most Water (11)]()
```python=1
def maxArea(height):
max_ans = 0
# idx: 同時一個左邊，一個從右邊
# max_ans 有變大才更新
i, j = 0, len(height)-1
while i < j :
if (height[i] > height[j]):
max_ans = max(max_ans, (j - i) * height[j])
j -= 1 # 因為 height[i] 比較高所以不用動，移動矮的那邊繼續遍歷看有沒有機會面積變大(有沒有機會找到比較高的height[j])
# 另一邊同理
else:
max_ans = max(max_ans, (j - i) * height[i])
i += 1
return max_ans
```
* [Best Time to Buy and Sell Stock IV (188)]()
* > 解題思路 DP作法([Ref](https://www.youtube.com/watch?v=aNoSpLIoB-k)):
dp[i][0][1] 在第i天進行第一次買入
dp[i][1][0] 在第i天進行第一次賣出。
* > dp[i][j-1][1]：表示第i天，第j次買入後的累計最大利潤
dp[i][j][0]：表示第i天，第j次賣出後的累計最大利潤
dp[i][0][0] = 0: 初始的狀態
dp[n][k][0]: 即為所求，因為最後一天不會再買入了
* > step1:
第j次買入： 第j次買入後保持不動 OR 從第j-1次賣出後買入
dp[i][j-1][1] = max(dp[i-1][j-1][1], dp[i-1][j-1][0] - prices[i])
#dp[i-1][j-1][1]: 保持不動; dp[i-1][j-1][0] - prices[i]: 前一次賣出後，再買入
第j次賣出： 第j次賣出後保持不動 OR 第j次買入後賣出
#dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])
* > step2: 因為第j次買入只和第j-1賣出相關，第j次賣出只和第j次買入相關，所以可以省去第一維(即捨去[i])
dp[j-1][1] = max(dp[j-1][1], dp[j-1][0] - prices[i])
dp[j][0] = max(dp[j][0], dp[j-1][1] + prices[i])
```python=1
def maxProfit(k, prices):
if not prices:
return 0
n = len(prices)
# k > n // 2: 就可視為無限次數交易(跟這系列第二題一樣: 122.)，作法就是Greedy: O(n)
if k > n // 2:
res = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
res += prices[i] - prices[i - 1]
return res
n = len(prices)
dp = [[0, 0] for _ in range(k + 1)]
for i in range(k + 1):
# 第零天進行第 i 次買入
dp[i][1] = -prices[0]
# 遍歷每一天
for i in range(1, n):
# 遍歷所有可能買賣次數
for j in range(1, k + 1):
dp[j - 1][1] = max(dp[j - 1][1], dp[j - 1][0] - prices[i])
dp[j][0] = max(dp[j][0], dp[j - 1][1] + prices[i])
# 最後一天進行最後第k次的買入
return dp[k][0]
```
* [Best Time to Buy and Sell Stock III (123)]()
* > 兩個 Array的意涵:
* p1: 從頭開始到某個元素的 max_profit
* p2: 從某個元素開始到最後的 max_profit
* 某元素的 p1+p2 為最大值，就是題目要求的
* > 使用到該系列第一題的概念
```python=1
def maxProfit(prices):
if len(prices) < 2:
return 0
max_profit, min_price = 0, prices[0]
profitTrans1 = [0]*len(prices)
profitTrans2 = [0]*len(prices)
for i in range(len(prices)):
profitTrans1[i] = max(profitTrans1[i], prices[i] - min_price)
min_price = min(min_price, prices[i])
highest = prices[len(prices)-1]
# 逆著算
for j in range(len(prices)-2, 0, -1):
profitTrans2[j] = max(profitTrans2[j+1], highest - prices[j])
highest = max(highest, prices[j])
max_ans = 0
for idx in range(len(profitTrans1)):
max_ans = max(max_ans, profitTrans1[idx]+profitTrans2[idx])
return max_ans
```
* [Best Time to Buy and Sell Stock II (122)]()
> 可多次買賣
> Ex: prices = [1,2,3,4,5] # Output: 4
for-loop
(prices[1] - prices[0]) + (prices[2] - prices[1]) + (prices[3] - prices[2]) + (prices[4] - prices[3]) = prices[4] - prices[0]
> 整理後前後相消，就會是題目要的方式
```python=1
def maxProfit(prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <= 1:
return 0
total = 0
# 注意 i 是從 1 開始
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
total += (prices[i] - prices[i-1])
return total
```
* [Best Time to Buy and Sell Stock (121)]()
> O(n^2):TLE
```python=1
def maxProfit(prices):
profit = 0
# ｊ為出售的日期
for j in range(len(prices)):
# i 不用減 1
for i in range(j):
if (prices[j] - prices[i]) > profit:
profit = prices[j] - prices[i]
return profit
```
> Greedy
```python=1
def maxProfit(prices):
"""
:type prices: List[int]
:rtype: int
"""
max_profit, min_price = 0, float("inf") # float("inf"):初始值設定無限大，那末更新時就會變新數值
for price in prices:
# 以下都是比較後做數值更新
min_price = min(min_price, price) # 只要確保買入價格是最低，就能得到 max_profit
max_profit = max(max_profit, price - min_price)
return max_profit
```
> DP
> C++
> 
min_prices[i] & max_profit[i]分別都是動態規劃
[Jump Game II (45)](https://leetcode.com/problems/jump-game-ii/)
> Greedy
> 最後一個位置不用遍歷，題目設定隱含一定會走到最後一個位置
```python=1
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return 0
step = 0
left = 0
right = 0
# len(nums) - 1 因為最後一個不用遍歷(它是跳到的最終位置)
for i in range(len(nums) - 1):
right = max(right, i+nums[i]) # 更新該範圍遍歷後能走到的最右邊距離
#以下條件滿足，代表遍歷完成(就要進入下一個區域)
if i == left:
# 跳轉下一個區域，代表又多走一步
step += 1
left = right # 下下個區域的左界線，就是下個區域的右界線
return step
```
* [Pascal’s Triangle II (119)]
> Sol_1: 參見玫如筆記
> Sol_2: Recursive Solution
```python=1
class Solution(object):
def getRow(self, rowIndex):
if rowIndex == 0:
return [1]
output_pre = self.getRow(rowIndex-1)
output = [1] * (rowIndex+1)
for i in range(1, len(output)-1):
output[i] = output_pre[i-1] + output_pre[i]
return output
* [Majority Element (169)]
```python=1
def majorityElement(nums):
"""
:type nums: List[int]
:rtype: int
"""
tem = {}
for i in nums:
if i in tem.keys():
tem[i] += 1
else:
tem[i] = 1
#print(tem)
#check for the maximum value and return the key associated with it
return max(tem, key = tem.get)
```
* [Majority Element II (229)]
```python=1
def majorityElement(nums):
times = len(nums)/3
dic = {}
A = []
for i in range(len(nums)):
if nums[i] not in dic:
dic[nums[i]] = 1
else:
dic[nums[i]] += 1
#print(dic)
if (dic[nums[i]] > times):
A.append(nums[i])
# 用set()來消除重複append的元素
return list(set(A))
```
---
## String
* [Repeated DNA Sequences (187)]()
* mine: TLE
```python=
class Solution:
def findRepeatedDnaSequences(self, s: str):
if len(s) == 10:
return [].append(s)
nums_dic = {}
cut_list = []
# range()範圍要熟悉!!!
for i in range(len(s)-9):
cut_list.append(s[i:i+10])
for i in cut_list:
if cut_list.count(i)>1:
nums_dic[i] = cut_list.count(i) # 計算cut_list這個list, 出現i元素幾次
return list(nums_dic.keys())
```
* Sol: set().add
> * Runtime: 52 ms, faster than 96.15% of Python3 online submissions for Repeated DNA Sequences.
> * Memory Usage: 26.4 MB, less than 53.82% of Python3 online submissions for Repeated DNA Sequences.
```python=
# java: hashset
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
# set for sequence
sequence = set()
# set for sequence with repetition
repeated = set()
for i in range( len(s)-9 ):
# make current sequence for i to i+10
cur_seq = s[i:i+10]
if cur_seq in sequence:
# check for repetition
repeated.add( cur_seq )
# add to sequence set
sequence.add( cur_seq )
return [ *repeated ]
```
* [Is Subsequence (392)]()
> * Runtime: 32 ms, faster than 71.17% of Python3 online submissions for Is Subsequence.
> * Memory Usage: 14.4 MB, less than 54.67% of Python3 online submissions for Is Subsequence.
```python=
def isSubsequence(s, t):
# s = "abc", t = "ahbgdc"
remainder_of_t = iter(t)
print([i for i in remainder_of_t]) # ['a', 'h', 'b', 'g', 'd', 'c']
for letter in s:
if letter not in remainder_of_t:
return False
return True
```
> Q: why no bug?? 應該是iter的特性，對應到就會消掉
s = "aaaaaa"
t = "bbaaaa" # Output: false
print(isSubsequence(s, t))
* [Longest Valid Parentheses (32)]()
> [Ref_YT](https://www.youtube.com/watch?v=39CEPFCl5sE): DP解法 & 其他兩種 (暴力會TLE)
> Runtime: 44 ms, faster than 76.74% of Python3 online submissions for Longest Valid Parentheses.
> Memory Usage: 14.4 MB, less than 88.78% of Python3 online submissions for Longest Valid Parentheses.
>
```python=1
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n == 0:
return 0
dp = [0]*n # 初始化所有dp值為0
for i in range(len(s)):
# i - dp[i-1] - 1 是與當前")"對稱的位置
if s[i] == ")" and i-dp[i-1]-1 >=0 and s[i-dp[i-1]-1] == "(":
dp[i] = dp[i-1] + dp[i - dp[i-1] - 2]+2
return max(dp)
```
* [Palindrome Partitioning (131)]()
* Backtracking演算法
* 印度老師 [YT](https://www.youtube.com/watch?v=DKCbsiDBN6c)
* 台大訓練班 [YT](https://www.youtube.com/watch?v=nrHTtjkYEyQ)
```python=1
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
self.res = []
self.dfs(s, [])
return self.res
def dfs(self, s, temp):
if not s:
self.res.append(temp[:])
return
for i in range(1,len(s)+1):
if self.isPali(s[:i]):
temp.append(s[:i])
self.dfs(s[i:], temp)
temp.pop() # 要清空才能做下一輪
def isPali(self, s):
return s == s[::-1]
```
* [Palindrome Pairs (336)]()
* > 說明清楚[Ref_YT](https://www.youtube.com/watch?v=WPASktChEA4)
* 
```python=1
class Solution:
def palindromePairs(self, words):
dicts={}
for i, word in enumerate(words):
dicts[word[::-1]]=i # 把反轉的字串存到 dict
def isPalindrome(s):
return s==s[::-1]
res = set()
for i, word in enumerate(words):
for j in range(len(word)+1): # to cover the case of empty string
left = word[:j]
right = word[j:]
# case 1:
# i!=dicts[right] 才不會對到重複的值(即自己和自己的reverse組成的回文，是不符合題意)
if isPalindrome(left) and (right in dicts) and (i!=dicts[right]):
res.add((dicts[right], i))
# case 2:
if isPalindrome(right) and (left in dicts) and (i!=dicts[left]):
res.add((i, dicts[left]))
return res
```
* [Shortest Palindrome (214)]()
> * [Ref_YT](https://www.youtube.com/watch?v=c4akpqTwE5g)
> * 
```python=1
def shortestPalindrome(s):
"""
:type s: str
:rtype: str
"""
rev_s = s[::-1] # py型別str並無提供方法reverse() → 用逆轉切片方式做
l = s + '#' + rev_s
p = [0]* len(l)
print(p)
# Build KMP table
for i in range(1, len(l)):
j = p[i-1] # update prefix boundary
# move to the last prefix boundary match
while (j > 0) and (l[i] != l[j]):
j = p[j-1]
if l[i] == l[j]:
p[i] = j+1
return rev_s[:(len(s) - p[len(l) - 1])] + s
```
* [Minimum Window Substring (76)]()
> 1. sliding window 的右邊界每次移動一格，左邊界移動越多越好
> 2. 當移動左邊界會不滿足題目要求，則只能繼續新增右邊界，除非遇到同一個character 才能縮小slinding window(slow:左邊界, fast:右邊界)
> 3. dic 紀錄每個char 欠的次數(若為負數，代表重複出現了→有機會縮小slinding); formed代表滿足T要求的的char個數
> 4. Time: 左右邊界都分別走 O(n), Space: 使用字典，最壞的情況是T和S長度一樣長 → O(n)
```python=
import collections
def minWindow(s, t):
# build the counter
d = dict(collections.Counter(t)) # {A:1, B:1, C:1}
formed, slow = 0, 0
min_str, min_length = None, sys.maxsize-1
for fast in range(len(s)):
# skip if s[fast] dosen't matter(就跳過，即使用continue)
ch = s[fast]
fast += 1
if ch not in d:
# 利用continue 來終止本次的 for-loop
continue
# use the ch to update d
d[ch] -= 1
# 下面這個代表債還完
if d[ch] == 0:
formed += 1 # 還完的債就要紀錄
# 若全部都還完了(formed == len(d))，則開始移動至下一個窗格(if all satisfied, then move the left pointer)
# 債還完，且確保左右邊界不會交叉
while formed == len(d) and slow <= fast:
# save the result(要用全域變數: min_str, min_length)
curr_length = fast - slow
if curr_length < min_length:
min_length = curr_length # 若值更小，就做更新
min_str = s[slow:fast]
# update the left pointer
ch = s[slow]
slow += 1
# 若不再裡面就跳過
if ch not in d:
continue
d[ch] += 1 # 代表欠的債又變多了
if d[ch] == 1:
formed -= 1 # 代表滿足條件的 char 個數減一
return min_str if min_str is not None else ""
```
* [Longest Palindromic Substring (5)]()
> * [Ref_Leetcode](https://leetcode.com/problems/longest-palindromic-substring/discuss/751188/Simple-Easy-to-Follow-Python)
```python=1
#class Solution:
def longestPalindrome(s):
result = ""
for i in range(len(s)):
# this is for odd(奇數) length palindrome
word1 = checkPalindrome(s, i, i)
# this is for even(偶數) length palindrome
word2 = checkPalindrome(s, i, i+1)
#word1 will be max length word from word1 and word2
word1 = word1 if len(word1) >= len(word2) else word2
# compare word1 with our result
result = word1 if len(word1) >= len(result) else result
return result
# 該函數用來確認每個 substring 是回文
def checkPalindrome(s, lo, hi):
# 'lo': 由最右邊往左邊跑
# 'hi': 由最左邊往右邊跑
while lo>=0 and hi<len(s) and s[lo]==s[hi]:
lo -= 1
hi += 1
# return the slice from original string that starts from our last matched index of lo and hi.
# We don't increament hi because python slice goes up to ending index-1
return s[lo+1:hi]
```
* [Valid Palindrome (125)]()
> * consider alphanumeric characters(數字字符字母) and ignoring cases(忽略大小寫).
> * 要清除所有標點符號
```python=1
def isPalindrome(s):
s = re.sub("[^a-z0-9]",'',s.lower()) # 先轉小寫，再用 re 過濾
return s == ''.join(reversed(s))
```
* [Longest Substring with At Least K Repeating Characters (395)]()
* > 該最長子字串，每個元素都要出現>= k 次(at least)
* 
```python=1
def longestSubstring(s, k):
res = 0
# 遍歷子串能出現幾個不同的字母
for i in range(1, len(set(s)) + 1):
times = [0] * 26
# 以下分別為: 左指針、右指針、次數、當前子字串已經出現多少個不同字母
l = r = ct = dif_ct = 0
# 右指針步道結尾時，持續遍歷
while r < len(s):
ind = ord(s[r]) - ord('a')
times[ind] += 1
if times[ind] == 1:
# 出現一個新的不同字母
dif_ct += 1
if times[ind] == k:
# 已經出現k次，代表該字母已經符合條件了
ct += 1
r += 1 # 右指針向右移動
# dif_ct > i: 超過我們限定的字母個數 → 移動左指針
while l < r and dif_ct > i:
ind = ord(s[l]) - ord('a')
if times[ind] == k:
ct -= 1 # 就不符合題目要求了
if times[ind] == 1:
dif_ct -= 1 # times[ind]減1之後就是0 → 所 dif_ct 就要對應減1
times[ind] -= 1
l += 1 # 左指針就要向右移動了
if dif_ct == ct == i:
res = max(res, r - l)
return res
```
* [Longest Substring Without Repeating Characters (3)]()
* 完整版YT解說影片(C++) [Ref_YT](https://www.youtube.com/watch?v=LupZFfCCbAU)
* > 1.只移動windows的一個端點(右邊ｊ)，另外一邊都過是否合法來做更新
> 2.左端點一定是最後一次出現'a'的右邊一個元素
```python=1
def lengthOfLongestSubstring(s):
dic = {} # 用這個來記錄每個元素最後出線的 idx
res = 0
i = 0
# j 為右端點
for j in range(len(s)):
if s[j] not in dic:
dic[s[j]] = j # i 為該字元的最後出現位置 idx
else:
# 若有重複字元就要更新左端點
i = max(i, dic[s[j]]+1)
dic[s[j]] = j # dict對應到的 idx 也要更新
res = max(res, j-i+1) # 若長度有變長，就做更新
return res
```
* [Palindrome Number (9)]()
>
```python=1
def isPalindrome(x):
A = list(str(x))
return A == A[::-1]
```
> 正規解法
```python=1
def isPalindrome(x):
if x < 0:
return False
beg = x
rev = 0
while(x > 0):
rev = rev * 10 + x % 10
x = x // 10
return beg == rev
```
* [Integer to English Words (273)]()
```python=1
def numberToWords(num):
to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
thousand = 'Thousand Million Billion'.split()
def word(num, idx=0):
if num == 0:
return []
if num < 20:
return [to19[num-1]]
if num < 100:
return [tens[num//10-2]] + word(num%10)
if num < 1000:
# word(num) 這個地方就是 recursive
return [to19[num//100-1]] + ['Hundred'] + word(num%100)
p, r = num//1000, num%1000
space = [thousand[idx]] if p % 1000 !=0 else []
return word(p, idx+1) + space + word(r)
return ' '.join(word(num)) or 'Zero'
```
* [Integer to Roman (12)]()
```python=1
def intToRoman1(num):
values = [ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 ]
numerals = [ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" ]
res, i = "", 0
while num:
res += (num//values[i]) * numerals[i]
num %= values[i]
i += 1
return res
```
* [Roman to Integer (13)]()
> 找出規則
> test
s = "IV" # 4
ans = 1+5+(-2)
s = "IX" # 9
ans = 1+10+(-2)
```python=1
d = {'I': 1, 'V': 5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000, 'IV':-2, 'IX':-2, 'XL':-20
, 'XC':-20, 'CD':-200, 'CM':-200}
def romanToInt(s):
ans = 0
list_s = list(s)
#print(list_s)
for i in range(len(list_s)):
if list_s[i] in d:
ans += d[list_s[i]]
for j in range(len(list_s)-1):
if s[j:j+2] in d:
ans += d[s[j:j+2]]
return ans
```
* [Excel Sheet Column Number (171)]()
```python=1
def titleToNumber(s):
ele_list = list(s[::-1]) # 逆著算
j = 0
for i in range(len(ele_list)):
j += 26**(i)*(ord(ele_list[i])%65+1)
return j
```
* [Excel Sheet Column Title (168)](https://leetcode.com/problems/excel-sheet-column-title/submissions/)
> key: n -= 1
```python=1
class Solution(object):
def convertToTitle(self, n):
"""
:type n: int
:rtype: str
"""
ans = []
while (n > 0):
# 28 應得到 'AB' (26: 'Z', 27: 'AA')
n -= 1 # 'A' + 27 % 26 = 'B'
ans.append((chr(ord('A') + n % 26)))# 餘數
n = n // 26 # 商數
ans.reverse()
# 輸出結果要逆著算
return ''.join(ans)
```
* [Valid Anagram (242)]
```python=1
def isAnagram(s, t):
"""
:type s: str
:type t: str
:rtype Boolean
"""
# s 的字元組成是否和 ｔ 的組成相同
dic_s = {}
dic_t = {}
for i in range(len(s)):
if s[i] in dic_s.keys():
dic_s[s[i]] += 1
else:
dic_s[s[i]] = 1
for j in range(len(t)):
if t[j] in dic_t.keys():
dic_t[t[j]] += 1
else:
dic_t[t[j]] = 1
return dic_s == dic_t
```
* [Group Anagrams (49)]
```python=1
def groupAnagrams(strs):
res = {}
for item in strs:
k = ''.join(sorted(item)) # 字符串排序: 先sortedt成list，再轉回str
# 判斷是否存在
if k not in res:
# 新增字典資料
res[k] = []
# 相同字符串放到同一個字典 k 中 (厲害！)
res[k].append(item)
#print(f'res={res}')
return [res[x] for x in res]
```
> Sol_1: Recursive Solution
> Boyer-Moore(BM) Voting Algorithm (沒比較快)
[Ref: 摩爾投票算法](https://blog.csdn.net/u014248127/article/details/79230221)
```python=1
def majorityElement(self, nums: List[int]) -> List[int]:
num1,count1 = None,0
num2,count2 = None,0
# 算法核心，找出主要元素的候選值
for x in nums:
if x == num1:
count1 += 1
elif x == num2:
count2 += 1
elif count1 == 0:
num1,count1 = x,1
elif count2 == 0:
num2,count2 = x,1
else:
count1 -= 1
count2 -= 1
count1,count2 = 0,0
# 統計確定候選值是真的主要元素
for x in nums:
if x == num1:
count1 += 1
if x == num2:
count2 += 1
res = []
if count1 > len(nums)//3:
res.append(num1)
if count2 > len(nums)//3:
res.append(num2)
return res
```
Sign in with Wallet
Connect another wallet