核心算法
Binary Tree based Recursion & Divide Conquer 二叉树递归与分治
226. Invert Binary Tree (Easy)
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
递归1:
class Solution:
def invertTree(self, root):
if not root:
return
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root遍历：
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
stack = [(root)]
while stack:
p = stack.pop()
p.left, p.right = p.right, p.left
if p.left:
stack.append((p.left))
if p.right:
stack.append((p.right))
return root递归2
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return rootBlind 75
100. Same Tree (Easy)
Given two binary trees, 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.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
递归：
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if (p and not q) or (q and not p) or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)遍历：
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
stack = [(p, q)]
while stack:
p, q = stack.pop(-1)
if not p and not q:
continue
if (p and not q) or (q and not p) or p.val != q.val:
return False
stack.append((p.left, q.left))
stack.append((p.right, q.right))
return True五刷：高频
101. Symmetric Tree (Easy)
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
递归
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def helper(l, r):
if not l and not r:
return True
if (l and not r) or (not l and r):
return False
return l.val == r.val and helper(l.left, r.right) and helper(l.right, r.left)
return helper(root.left, root.right)遍历：
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
stack = [(root.left, root.right)]
while stack:
(l, r) = stack.pop()
if not l and not r:
continue
if l and not r or not l and r or l.val != r.val:
return False
if l and r:
stack.append((l.left, r.right))
stack.append((l.right, r.left))
return True9刷：高频
104. Maximum Depth of Binary Tree (Easy)
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
递归1：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def helper(root, depth = 0):
nonlocal ans
ans = max(ans, depth)
if root:
helper(root.left, depth + 1)
helper(root.right, depth + 1)
ans = 0
helper(root)
return ans递归2：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
else:
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1遍历1：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
ans = 0
stack = [(root, 1)]
while stack:
root, cur = stack.pop()
ans = max(ans, cur)
if root.left:
stack.append((root.left, cur + 1))
if root.right:
stack.append((root.right, cur + 1))
return ans遍历2：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
q = [[root]]
ans = 0
while q:
cur = []
for root in q.pop(0):
if root:
cur.append(root.left)
cur.append(root.right)
if cur:
ans += 1
q.append(cur)
return ans10刷：高频
111. Minimum Depth of Binary Tree (Easy)
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
递归
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
def helper(root, depth):
nonlocal ans
if not root:
return
if not root.left and not root.right:
ans = min(ans, depth)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
ans = float('inf')
helper(root, 1)
return ans遍历
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
stack = [(root, 1)]
ans = float('inf')
while stack:
root, depth = stack.pop()
if not root.left and not root.right:
ans = min(ans, depth)
if root.left:
stack.append((root.left, depth + 1))
if root.right:
stack.append((root.right, depth + 1))
return ans递归2：
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
l = self.minDepth(root.left)
r = self.minDepth(root.right)
if not root.left:
return r + 1
if not root.right:
return l + 1
return min(l, r) + 1高频
144. Binary Tree Preorder Traversal (Easy)
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
递归1:
class Solution:
def preorderTraversal(self, root):
def helper(root):
if not root:
return
ans.append(root.val)
helper(root.left)
helper(root.right)
ans = []
helper(root)
return ans非递归1：
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans, stack = [], []
while root or stack:
if root:
ans.append(root.val)
stack.append(root)
root = root.left
else:
root = stack.pop()
root = root.right
return ans非递归2:
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans, stack = [], [root]
while stack:
root = stack.pop()
ans.append(root.val)
if root.right:
stack.append(root.right)
if root.left:
stack.append(root.left)
return ans递归2:
class Solution:
def preorderTraversal(self, root):
if not root:
return []
l = self.preorderTraversal(root.left)
r = self.preorderTraversal(root.right)
return [root.val] + l + r非递归3：
class Solution:
def preorderTraversal(self, root):
if not root:
return []
ans, stack = [], []
while stack or root:
if root:
ans.append(root.val)
if root.right:
stack.append(root.right)
root = root.left
else:
root = stack.pop(-1)
return ans
94. Binary Tree Inorder Traversal (Medium)
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
递归 Traverse:
class Solution:
def inorderTraversal(self, root):
ans = []
def helper(root):
if not root:
return
helper(root.left)
ans.append(root.val)
helper(root.right)
helper(root)
return ans遍历：
class Solution:
def inorderTraversal(self, root):
if not root:
return []
ans = []
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop(-1)
ans.append(root.val)
root = root.right
return ans递归 Divide and Conquer/backtracking 分治:
class Solution:
def inorderTraversal(self, root):
if not root:
return []
l = self.inorderTraversal(root.left)
r = self.inorderTraversal(root.right)
return l + [root.val] + r八刷：高频, 遍历，stack初始为空，while root or stack: if root: 向左入栈到底 else: root出栈，root.val入ans，向右走...root = root.right
145. Binary Tree Postorder Traversal (Easy)
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
递归：
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
ans.append(root.val)
ans = []
helper(root)
return ans遍历：
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return
ans = []
stack = []
while root or stack:
if root:
stack.append(root)
ans.append(root.val)
root = root.right
else:
root = stack.pop()
root = root.left
return ans[::-1]class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [(root, False)]
while stack:
root, visited = stack.pop()
if root:
if visited:
ans.append(root.val)
else:
stack.append((root, True))
stack.append((root.right, False))
stack.append((root.left, False))
return ansclass Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans = []
stack = [(root)]
while stack:
root = stack.pop()
ans.append(root.val)
if root.left:
stack.append(root.left)
if root.right:
stack.append(root.right)
return ans[::-1]230. Kth Smallest Element in a BST (Medium)
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
递归：
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
ans = None
def helper(root):
nonlocal k, ans
if not root:
return
helper(root.left)
k -= 1
if k == 0:
ans = root.val
return
helper(root.right)
helper(root)
return ans遍历:
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right10刷：面经，Triplebyte, 维萨
Follow up: 二叉树经常被修改 如何优化 kthSmallest 这个操作? leetcode官方答案提出做一个类似LRU双链表的数据结构实现O(h + k)插删和查询
129. Sum Root to Leaf Numbers (Medium)
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
递归:
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def helper(root, cur):
nonlocal ans
if not root:
return
cur += root.val
if not root.left and not root.right:
ans += cur
helper(root.left, cur * 10)
helper(root.right, cur * 10)
ans = 0
helper(root, 0)
return ans遍历：
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
ans, stack = 0, [(root, 0)]
while stack:
root, cur = stack.pop()
cur = cur * 10 + root.val
if not root.left and not root.right:
ans += cur
if root.left:
stack.append((root.left, cur))
if root.right:
stack.append((root.right, cur))
return ans8刷：高频
116. Populating Next Right Pointers in Each Node (Medium)
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example:
递归：
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
if root.left:
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.right)
self.connect(root.left)
return root六刷：高频，遍历允许用额外空间的话比较简单，就不写了，用O(1)额外空间的遍历写法与117题差不多
117. Populating Next Right Pointers in Each Node II (Medium)
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example:
Note:
You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.
原题链接不稳定，少量测试数据：
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
class Solution:
def connect(self, root: 'Node') -> 'Node':
# solution code here
return
def verify(root):
current = root
while current:
temp = current
while temp:
if temp.left and temp.right:
if temp.left.next != temp.right:
return False
if temp.right.next and temp.next:
if temp.right.next != temp.next.left and temp.next.left:
return False
elif temp.left and not temp.right:
if temp.left.next and temp.next:
if temp.left.next != temp.next.left:
return False
elif temp.right and not temp.left:
if temp.right.next and temp.next:
if temp.right.next != temp.next.left and temp.next.left:
return False
temp = temp.next
current = current.left
return True
# Example 1: Given Example
# 1 -> NULL
# / \
# 2 -> 3 -> NULL
# / \ \
# 4->5 -> 7 -> NULL
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)
root1.right.right = Node(7)
solution = Solution()
solution.connect(root1)
print(f"Example 1: {verify(root1)}") # Should print True
# Example 2: Perfect Binary Tree
# 1 -> NULL
# / \
# 2 -> 3 -> NULL
# / \ / \
# 4-> 5->6-> 7 -> NULL
root2 = Node(1)
root2.left = Node(2)
root2.right = Node(3)
root2.left.left = Node(4)
root2.left.right = Node(5)
root2.right.left = Node(6)
root2.right.right = Node(7)
solution = Solution()
solution.connect(root2)
print(f"Example 2: {verify(root2)}") # Should print True
# Example 3: Skewed Binary Tree
# 1 -> NULL
# /
# 2 -> NULL
# /
# 3 -> NULL
# /
# 4 -> NULL
root3 = Node(1)
root3.left = Node(2)
root3.left.left = Node(3)
root3.left.left.left = Node(4)
solution = Solution()
solution.connect(root3)
print(f"Example 3: {verify(root3)}") # Should print True
# Example 4: Single Node Tree
# 1 -> NULL
root4 = Node(1)
solution = Solution()
solution.connect(root4)
print(f"Example 4: {verify(root4)}") # Should print True递归1，如果可用额外空间：
class Solution:
def connect(self, root: 'Node') -> 'Node':
def helper(root, depth):
if not root:
return
if depth in left:
left[depth].next = root
left[depth] = root
helper(root.left, depth + 1)
helper(root.right, depth + 1)
left = {}
helper(root, 0)
return root递归2，不用额外空间：
class Solution:
def connect(self, root: 'Node') -> 'Node':
def helper(root: Node):
if root:
return root.left or root.right or helper(root.next)
if root:
if root.left:
if root.right:
root.left.next = root.right
else:
root.left.next = helper(root.next)
if root.right:
root.right.next = helper(root.next)
self.connect(root.right)
self.connect(root.left)
return root遍历1，如果可用额外空间：
class Solution:
def connect(self, root: 'Node') -> 'Node':
q = [root]
while q:
nq = []
for i, root in enumerate(q):
if i:
q[i - 1].next = root
if root.left:
nq.append(root.left)
if root.right:
nq.append(root.right)
q = nq
return root遍历2，不用额外空间：
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return
cur = root
nextLevelHead = Node(0)
while cur:
p = nextLevelHead
while cur:
if cur.left:
p.next = cur.left
p = p.next
if cur.right:
p.next = cur.right
p = p.next
cur = cur.next
cur = nextLevelHead.next
nextLevelHead.next = None
return root 高频
110. Balanced Binary Tree (Easy)
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
递归1:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def helper(root):
nonlocal ans
if not root:
return 0
l = helper(root.left)
r = helper(root.right)
if abs(l - r) > 1:
ans = False
return max(l, r) + 1
ans = True
helper(root)
return ans遍历1:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
stack = [(root, False)]
depth = {None: 0}
while stack:
root, visited = stack.pop()
if root:
if visited:
l, r = depth[root.left], depth[root.right]
if abs(l - r) > 1:
return False
depth[root] = max(l, r) + 1
else:
stack.append((root, True))
stack.append((root.left, False))
stack.append((root.right, False))
return True遍历2:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
stack = [root]
depth = {None: 0}
while stack:
root = stack[-1]
if root.left in depth and root.right in depth:
l, r = depth[root.left], depth[root.right]
if abs(l - r) > 1:
return False
depth[root] = max(l, r) + 1
stack.pop()
if root.left not in depth:
stack.append(root.left)
if root.right not in depth:
stack.append(root.right)
return True递归2:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def helper(root):
if not root:
return 0
hl = helper(root.left)
hr = helper(root.right)
return max(hl, hr) + 1
if not root:
return True
hl = helper(root.left)
hr = helper(root.right)
return abs(hl - hr) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)递归3:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def helper(root):
if not root:
return 0
l = helper(root.left)
r = helper(root.right)
if l < 0 or r < 0 or abs(l - r) > 1:
return -1
return max(l, r) + 1
return helper(root) >= 0递归4:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def helper(root):
if not root:
return 0, True
l, leftBalanced = helper(root.left)
r, rightBalanced = helper(root.right)
return max(l, r) + 1, leftBalanced and rightBalanced and abs(l - r) <= 1
return helper(root)[1]16刷: 高频
543. Diameter of Binary Tree (Easy)
Given a binary tree, you need to compute 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.
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
递归1：
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def helper(root):
nonlocal ans
if not root:
return 0
l = helper(root.left)
r = helper(root.right)
ans = max(ans, l + r)
return max(l, r) + 1
ans = 0
helper(root)
return ans遍历1：
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
stack = [(root, False)]
depth = {None: 0}
while stack:
root, visited = stack.pop()
if root:
if visited:
l = depth[root.left]
r = depth[root.right]
ans = max(ans, l + r)
depth[root] = max(l, r) + 1
else:
stack.append((root, True))
stack.append((root.left, False))
stack.append((root.right, False))
return ans遍历2：
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
stack = [root]
depth = {None: 0}
while stack:
root = stack[-1]
if root.left in depth and root.right in depth:
l = depth[root.left]
r = depth[root.right]
ans = max(ans, l + r)
depth[root] = max(l, r) + 1
stack.pop()
if root.left not in depth:
stack.append(root.left)
if root.right not in depth:
stack.append(root.right)
return ans递归2：
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def helper(root):
if not root:
return 0, 0
leftDepth, leftDiameter = helper(root.left)
rightDepth, rightDiameter = helper(root.right)
return max(leftDepth, rightDepth) + 1, max(leftDiameter, rightDiameter, leftDepth + rightDepth)
return helper(root)[1]高频
108. Convert Sorted Array to Binary Search Tree (Easy)
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
递归
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def helper(l, r):
if l <= r:
mid = (l + r) // 2
root = TreeNode(nums[mid])
root.left = helper(l, mid - 1)
root.right = helper(mid + 1, r)
return root
return helper(0, len(nums) - 1)遍历
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
root = TreeNode()
stack = [(root, 0, len(nums) - 1)]
while stack:
p, l, r = stack.pop()
mid = (l + r) // 2
p.val = nums[mid]
if l < mid:
p.left = TreeNode()
stack.append((p.left, l, mid - 1))
if mid < r:
p.right = TreeNode()
stack.append((p.right, mid + 1, r))
return root递归
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root高频; 面经: Amazon
109. Convert Sorted List to Binary Search Tree (Medium)
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
解法3：space: O(1): time: O(nlogn)
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
def helper(l, r):
if l == r:
return
s = f = l
while f != r and f.next != r:
s = s.next
f = f.next.next
root = TreeNode(s.val)
root.left = helper(l, s)
root.right = helper(s.next, r)
return root
return helper(head, None)解法2：space: O(n); time : O(n)
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
def helper(l, r):
if l > r:
return
root_i = (l + r) // 2
root = TreeNode(nums[root_i])
root.left = helper(l, root_i - 1)
root.right = helper(root_i + 1, r)
return root
nums = []
while head:
nums.append(head.val)
head = head.next
return helper(0, len(nums) - 1)解法1：space: O(1): time: O(nlogn)
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
def helper(l, r):
if l == r:
return
s = f = dummy = ListNode()
dummy.next = l
while f != r and f.next != r:
s = s.next
f = f.next.next
root = TreeNode(s.val)
root.left = helper(l, s)
root.right = helper(s.next, r)
return root
return helper(head, None)Blind 75; 高频
112. Path Sum (Easy)
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
ans = False
def helper(root, cur):
nonlocal ans
if not root:
return
cur -= root.val
if not root.left and not root.right:
if cur == 0:
ans = True
return
helper(root.left, cur)
helper(root.right, cur)
helper(root, sum)
return ans七刷：高频，面经，Quora
199. Binary Tree Right Side View (Medium)
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
递归：
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
def dfs(root, depth):
if not root:
return
if len(ans) < depth:
ans.append(root.val)
dfs(root.right, depth + 1)
dfs(root.left, depth + 1)
ans = []
dfs(root, 1)
return ans遍历：
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
ans = []
q = [root]
while q:
ans.append(q[-1].val)
nq = []
for root in q:
if root.left:
nq.append(root.left)
if root.right:
nq.append(root.right)
q = nq
return ans6刷：面经, 维萨
235. Lowest Common Ancestor of a Binary Search Tree (Easy)
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Note:
All of the nodes' values will be unique.
p and q are different and both values will exist in the BST.
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > q.val:
p, q = q, p
if p.val <= root.val <= q.val:
return root
if root.val < p.val:
return self.lowestCommonAncestor(root.right, p, q)
if root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > q.val:
p, q = q, p
if root.val < p.val:
return self.lowestCommonAncestor(root.right, p, q)
if root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
return rootclass Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
return rootclass Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
if root.val < p.val and root.val < q.val:
root = root.right
elif root.val > p.val and root.val > q.val:
root = root.left
else:
return root注意要return f()，否则会return最顶上的root
563. Binary Tree Tilt (Easy)
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.
The tilt of the whole tree is defined as the sum of all nodes' tilt.
Example:
Input:
1
/ \
2 3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1
Note:
The sum of node values in any subtree won't exceed the range of 32-bit integer.
All the tilt values won't exceed the range of 32-bit integer.
class Solution:
def findTilt(self, root: TreeNode) -> int:
if not root:
return 0
ans = 0
def helper(root):
nonlocal ans
if not root:
return 0
l = helper(root.left)
r = helper(root.right)
ans += abs(l - r)
return l + r + root.val
helper(root)
return ans六刷：O(n)
669. Trim a Binary Search Tree (Easy)
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:
1
/ \
0 2
L = 1
R = 2
Output:
1
\
2
Example 2:
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
class Solution:
def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
if not root:
return
l = self.trimBST(root.left, L, R)
r = self.trimBST(root.right, L, R)
root.left, root.right = l, r
if L <= root.val <= R:
return root
if root.val < L:
return r
if root.val > R:
return l10刷：每层三种情况：1：小于最小，则返回右子树传上来的root；2：大于最大，则返回左子树传上来的root；3.大小之间，将root返回上层
687. Longest Univalue Path (Medium)
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
The length of path between two nodes is represented by the number of edges between them.
Example 1:
Input:
5
/ \
4 5
/ \ \
1 1 5
Output: 2
Example 2:
Input:
1
/ \
4 5
/ \ \
4 4 5
Output: 2
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
def dfs(root):
nonlocal ans
if not root:
return 0
l = dfs(root.left)
r = dfs(root.right)
lp, rp = 0, 0
if root.left and root.val == root.left.val:
lp = l + 1
if root.right and root.val == root.right.val:
rp = r + 1
ans = max(ans, lp + rp)
return max(lp, rp)
ans = 0
dfs(root)
return ans 写法2：
class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
def dfs(root, pre):
nonlocal ans
if not root:
return 0
l = dfs(root.left, root)
r = dfs(root.right, root)
ans = max(ans, l + r)
if pre and pre.val == root.val:
return max(l, r) + 1
return 0
ans = 0
dfs(root, None)
return ans16刷：写法1：l, r左右各自递归后lp = rp = 0; if ...: lp = l + 1...ans = max(ans, lp + rp) return max(lp, rp)。写法2：f(root, pre) 当前层无法判断是否左右子节点都相等，但是因为如果有一边子节点不相等会将l或r返回为0，那么ans = max(ans, l + r)即可获得想要的答案
114. Flatten Binary Tree to Linked List (Medium)
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
解法1：
class Solution:
def flatten(self, root: TreeNode) -> None:
if not root:
return
l = self.flatten(root.left)
r = self.flatten(root.right)
if l:
root.right = l
root.left = None
while l.right:
l = l.right
l.right = r
return root九刷：高频
236. Lowest Common Ancestor of a Binary Tree (Medium)
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
according to the LCA definition.
Note:
All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.
递归：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return
if root == p or root == q:
return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if l and r:
return root
elif l:
return l
elif r:
return r遍历：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
parent = {root: None}
stack = [root]
while p not in parent or q not in parent:
root = stack.pop()
if root.left:
parent[root.left] = root
stack.append(root.left)
if root.right:
parent[root.right] = root
stack.append(root.right)
ancestors = []
while p:
ancestors.append(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q13刷：递归：注意最后返回root需要if l and r这个条件。遍历：遍历，建立parent关系，p存入ancestors，遍历p的parent入ancestors，遍历q和q的parent，在ancestors中即返回。TODO 不需要parent关系的算法
285. Inorder Successor in BST (Medium) 带锁
LinC 448. Inorder Successor in BST (Medium)
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
If the given node has no in-order successor in the tree, return null.
It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)
Example
Given tree = [2,1] and node = 1:
2
/
1
return node 2.
Given tree = [2,1,3] and node = 2:
2
/ \
1 3
return node 3.
Challenge
O(h), where h is the height of the BST.
O(h)
class Solution:
def inorderSuccessor(self, root, p):
if not root:
return
suc = None
while root != p:
if root.val < p.val:
root = root.right
else:
suc = root
root = root.left
if not root.right:
return suc
root = root.right
while root.left:
root = root.left
return rootO(n):
def inorderSuccessor(self, root, p):
def dfs(root):
nonlocal inPre, ans
if not root:
return
dfs(root.left)
if inPre == p:
ans = root
inPre = root
dfs(root.right)
ans, inPre = None, None
dfs(root)
return ansO(n)遍历：
class Solution:
def inorderSuccessor(self, root, p):
pre = None
stack = []
while root or stack:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
if pre == p:
return root
pre = root
root = root.rightO(n)递归2：
class Solution:
def inorderSuccessor(self, root, p):
found = False
ans = None
def helper(root):
nonlocal found, ans
if not root:
return
helper(root.left)
if found:
ans = root
found = False
if root == p:
found = True
helper(root.right)
helper(root)
return ans13刷：递归O(n)解法：注意：处理p == inPre需要在递归调用左子树之后，否则pre为空；找到ans以后如果想return需要将inPre = None，否则会锁定inPre，导致上层的 inPre == p，而将上层的root赋值到ans中。
O(h)解法：找p的successor，那么如果root比p小p在右子树，反之p在左子树，去左子树之前要记一下suc节点，以防找到的root.val == p.val节点无右节点（即需要返回上层的suc）。如有右节点，则返回右节点中最小的（往右走一个然后返回最左节点）
98. Validate Binary Search Tree (Medium)
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
递归：
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def helper(root, l, h):
if not root:
return True
return l < root.val < h and helper(root.left, l, root.val) and helper(root.right, root.val, h)
return helper(root, float('-inf'), float('inf'))遍历：
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
stack = [(root, float('-inf'), float('inf'))]
while stack:
root, l, h = stack.pop()
if root.val <= l or root.val >= h:
return False
if root.left:
stack.append((root.left, l, root.val))
if root.right:
stack.append((root.right, root.val, h))
return Trueinorder 中序遍历：
class Solution:
def isValidBST(self, root):
stack = []
pre = None
while root or stack:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop(-1)
if pre and pre.val >= root.val:
return False
pre = root
root = root.right
return Trueinorder 中序递归：
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def in_order(root):
nonlocal pre, ans
if not root:
return
in_order(root.left)
if pre and pre.val >= root.val:
ans = False
return
pre = root
in_order(root.right)
pre = None
ans = True
inorder(root)
return ansinorder 中序递归额外数组：
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def in_order(root):
if not root:
return
in_order(root.left)
res.append(root.val)
in_order(root.right)
res = []
in_order(root)
for i in range(1, len(res)):
if res[i] <= res[i - 1]:
return False
return True高频
572. Subtree of Another Tree (Easy)
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def helper(r1, r2):
if not r1 and not r2:
return True
return r1 and r2 and r1.val == r2.val and helper(r1.left, r2.left) and helper(r1.right, r2.right)
if root:
return helper(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
else:
return FalseBlind 75; 高频
606. Construct String from Binary Tree (Easy)
You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.
The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".
Example 2:
Input: Binary tree: [1,2,3,null,4]
1
/ \
2 3
\
4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
写法1：
class Solution:
def tree2str(self, t: TreeNode) -> str:
if not t:
return ''
l = self.tree2str(t.left)
r = self.tree2str(t.right)
if r:
return f"{t.val}({l})({r})"
elif l:
return f"{t.val}({l})"
else:
return f"{t.val}"写法2：
class Solution:
def tree2str(self, t: TreeNode) -> str:
def helper(root):
nonlocal ans
if not root:
return
ans += str(root.val)
if root.right:
ans += '('
helper(root.left)
ans += ')('
helper(root.right)
ans += ')'
elif root.left:
ans += '('
helper(root.left)
ans += ')'
ans = ''
helper(t)
return ans11刷
297. Serialize and Deserialize Binary Tree (Hard)
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Example:
You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"
Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
dfs递归：
class Codec:
def serialize(self, root):
if not root:
return '#'
return f"{root.val}/{self.serialize(root.left)}/{self.serialize(root.right)}"
def deserialize(self, data):
if data == '#':
return
dq = deque(data.split('/'))
def helper():
if dq:
root_v = dq.popleft()
if root_v != '#':
root = TreeNode(root_v)
root.left = helper()
root.right = helper()
return root
return helper()bfs：
class Codec:
def serialize(self, root):
if not root:
return '#'
q = deque([root])
res = []
while q:
root = q.popleft()
if root:
res.append(str(root.val))
q.append(root.left)
q.append(root.right)
else:
res.append('#')
return '/'.join(res)
def deserialize(self, data):
if data == '#':
return
data = deque(data.split('/'))
root = TreeNode(data.popleft())
root_q = deque([root])
while data:
p = root_q.popleft()
root_v = data.popleft()
if root_v != '#':
p.left = TreeNode(root_v)
root_q.append(p.left)
root_v = data.popleft()
if root_v != '#':
p.right = TreeNode(root_v)
root_q.append(p.right)
return rootdfs遍历：
class Codec:
def serialize(self, root):
if not root:
return '#'
stack = []
res = []
while root or stack:
if root:
res.append(str(root.val))
stack.append(root)
root = root.left
else:
root = stack.pop()
res.append('#')
root = root.right
return '/'.join(res)
def deserialize(self, data):
if data == '#':
return
data = deque(data.split('/'))
root = p = TreeNode(data.popleft())
stack = []
while data:
root_v = data.popleft()
if p:
stack.append(p)
if root_v != '#':
p.left = TreeNode(root_v)
p = p.left
else:
p = stack.pop()
if root_v != '#':
p.right = TreeNode(root_v)
p = p.right
return rootBlind 75
536. Construct Binary Tree from String (Medium) 带锁
LinC 880. Construct Binary Tree from String (Medium)
You need to construct a binary tree from a string consisting of parenthesis and integers.
The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.
You always start to construct the left child node of the parent first if it exists.
Example 1:
Input: "-4(2(3)(1))(6(5))"
Output: {-4,2,6,3,1,5}
Explanation:
The output is look like this:
-4
/ \
2 6
/ \ /
3 1 5
Example 2:
Input: "1(-1)"
Output: {1,-1}
Explanation:
The output is look like this:
1
/
-1
Notice
There will only be '(', ')', '-' and '0' ~ '9' in the input string.
An empty tree is represented by "" instead of "()".
class Solution:
def str2tree(self, s):
if not s:
return
stack = []
i = 0
while i < len(s):
cur = ''
while s[i] and s[i] not in '()':
cur += s[i]
i += 1
if cur:
root = TreeNode(int(cur))
if stack:
if stack[-1].left:
stack[-1].right = root
else:
stack[-1].left = root
stack.append(root)
if s[i] == ")":
stack.pop()
i += 1
return stack[0]七刷：Facebook tag，递归的方法不适合面试时写，将此较好想的方法写熟。注意：string没有pop()
105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
写法2：O(n) time and space
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
in_idx = {v: i for i, v in enumerate(inorder)}
def helper(pl, pr, il, ir):
if pl <= pr and il <= ir:
root = TreeNode(preorder[pl])
r_i = in_idx[root.val]
l_len = r_i - il
root.left = helper(pl + 1, pl + l_len, il, r_i - 1)
root.right = helper(pl + l_len + 1, pr, r_i + 1, ir)
return root
return helper(0, len(preorder) - 1, 0, len(inorder) - 1)写法1：O(n^2) time and space
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if preorder:
root = TreeNode(preorder[0])
l_len = inorder.index(root.val)
root.left = self.buildTree(preorder[1:l_len + 1], inorder[:l_len])
root.right = self.buildTree(preorder[l_len + 1:], inorder[l_len + 1:])
return rootBlind 75; 高频
106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
O(n^2) time and space:
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return
root = TreeNode(postorder[-1])
lLen = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:lLen], postorder[:lLen])
root.right = self.buildTree(inorder[lLen + 1:], postorder[lLen:-1])
return rootO(n) time and space:
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return
iMap = {}
for i, v in enumerate(inorder):
iMap[v] = i
def helper(inS, inE, postS, postE):
if inS > inE:
return
root = TreeNode(postorder[postE])
ilE = iMap[root.val] - 1
plE = postS + ilE - inS
root.left = helper(inS, ilE, postS, plE)
root.right = helper(ilE + 2, inE, plE + 1, postE - 1)
return root
return helper(0, len(inorder) - 1, 0, len(postorder) - 1)七刷: 高频
889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre and post are distinct positive integers.
Example 1:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Note:
1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.
O(n)时间和空间解：
class Solution:
def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
if not pre:
return
iMap = {}
for i, v in enumerate(post):
iMap[v] = i
def helper(preS, preE, postS, postE):
if preS > preE:
return
root = TreeNode(pre[preS])
if preS < preE:
lEIPost = iMap[pre[preS + 1]]
lEIPre = preS + 1 + lEIPost - postS
root.left = helper(preS + 1, lEIPre, postS, lEIPost)
root.right = helper(lEIPre + 1, preE, lEIPost + 1, postE - 1)
return root
return helper(0, len(pre) - 1, 0, len(post) - 1)六刷：Facebook tag。需要一个insight：root in left subtree of pre show up last in left subtree of post
865. Smallest Subtree with all the Deepest Nodes (Medium)
Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.
A node is deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is that node, plus the set of all descendants of that node.
Return the node with the largest depth such that it contains all the deepest nodes in its subtree.
Example 1:
Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:
We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.
Note:
The number of nodes in the tree will be between 1 and 500.
The values of each node are unique.
class Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
def helper(root, pre, depth):
nonlocal maxDepth, deepest
if not root:
return
if depth == maxDepth:
deepest.append(root)
elif depth > maxDepth:
maxDepth = depth
deepest = [root]
parent[root] = pre
helper(root.left, root, depth + 1)
helper(root.right, root, depth + 1)
parent = {}
deepest = []
maxDepth = 0
helper(root, None, 1)
while len(deepest) > 1:
deepest = set([parent[n] for n in deepest])
return list(deepest)[0]10刷：Facebook tag
426. Convert Binary Search Tree to Sorted Doubly Linked List (Medium) 带锁
Linc 1534. Convert Binary Search Tree to Sorted Doubly Linked List
Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.
Let's take the following BST as an example, it may help you understand the problem better:
We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.
Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.
The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
Example 1:
Input: {4,2,5,1,3}
4
/ \
2 5
/ \
1 3
Output: "left:1->5->4->3->2 right:1->2->3->4->5"
Explanation:
Left: reverse output
Right: positive sequence output
Example 2:
Input: {2,1,3}
2
/ \
1 3
Output: "left:1->3->2 right:1->2->3"
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
def treeToDoublyList(self, root):
if not root:
return
head = None
pre = None
def helper(root):
nonlocal head, pre
if not root:
return
helper(root.left)
if not head:
head = root
if pre:
root.left = pre
pre.right = root
pre = root
helper(root.right)
helper(root)
head.left = pre
pre.right = head
return head四刷：Facebook tag。中序遍历可以升序遍历。连接相邻结点，需要用变量 pre 记录上一个遍历到的结点。需要变量head来指向最小（最左）的节点。在递归函数中，先判空，之后对左子结点递归调用，一直递归到最左结点。此时如果 head 为空的话，那么当前就是最左结点，赋值给 head 然后给 pre，对于之后遍历到的结点，就可以和 pre 接上
298. Binary Tree Longest Consecutive Sequence (Medium) 带锁
LinC 595. Binary Tree Longest Consecutive Sequence
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
Example
Example 1:
Input:
1
\
3
/ \
2 4
\
5
Output:3
Explanation:
Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input:
2
\
3
/
2
/
1
Output:2
Explanation:
Longest consecutive sequence path is 2-3,not 3-2-1, so return 2.
class Solution:
def longestConsecutive(self, root):
if not root:
return 0
ans = 0
def helper(root, pre, cur):
nonlocal ans
if not root:
return
if root.val == pre.val + 1:
cur += 1
else:
cur = 1
ans = max(ans, cur)
helper(root.left, root, cur)
helper(root.right, root, cur)
helper(root, root, 1)
return ans遍历：
class Solution:
def longestConsecutive(self, root):
if not root:
return 0
ans = 0
q = [(root, root, 1)]
while q:
root, pre, cur = q.pop(0)
if not root:
continue
if root.val == pre.val + 1:
cur += 1
else:
cur = 1
ans = max(ans, cur)
q.append((root.left, root, cur))
q.append((root.right, root, cur))
return ans五刷：Facebook tag
897. Increasing Order Search Tree (Easy)
Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.
Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
Note:
The number of nodes in the given tree will be between 1 and 100.
Each node will have a unique integer value from 0 to 1000.
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
nonlocal p
if not root:
return
dfs(root.left)
p.right = root
root.left = None
p = p.right
dfs(root.right)
dummy = p = TreeNode(0)
dfs(root)
return dummy.rightt7刷：Facebook tag，关键要建立p，因为在任意root，左边都被递归处理过并被p保存，第一步就可以将left切断
617. Merge Two Binary Trees (Easy)
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Constraints:
The number of nodes in both trees is in the range [0, 2000].
-104 <= Node.val <= 104
解法1：
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1解法2：
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return None
if not root1:
return TreeNode(root2.val, root2.left, root2.right)
if not root2:
return TreeNode(root1.val, root1.left, root1.right)
rootM = TreeNode(root1.val + root2.val)
rootM.left = self.mergeTrees(root1.left, root2.left)
rootM.right = self.mergeTrees(root1.right, root2.right)
return rootM写法3：
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return
root = TreeNode()
if root1 and not root2:
root.val = root1.val
root.left = self.mergeTrees(root1.left, None)
root.right = self.mergeTrees(root1.right, None)
return root
if not root1 and root2:
root.val = root2.val
root.left = self.mergeTrees(None, root2.left)
root.right = self.mergeTrees(None, root2.right)
return root
if root1 and root2:
root.val = root1.val + root2.val
root.left = self.mergeTrees(root1.left, root2.left)
root.right = self.mergeTrees(root1.right, root2.right)
return root4刷
124. Binary Tree Maximum Path Sum (Hard)
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Example 1:
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000
递归：
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
def helper(root):
nonlocal ans
if not root:
return 0
l = max(helper(root.left), 0)
r = max(helper(root.right), 0)
ans = max(ans, l + r + root.val)
return max(l, r) + root.val
ans = float('-inf')
helper(root)
return ans遍历：
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans = float('-inf')
stack = [(root, False)]
d = {None: 0}
while stack:
root, visited = stack.pop()
if visited:
l = max(d[root.left], 0)
r = max(d[root.right], 0)
ans = max(ans, l + r + root.val)
d[root] = max(l, r) + root.val
else:
stack.append((root, True))
if root.left:
stack.append((root.left, False))
if root.right:
stack.append((root.right, False))
return ansBlind 75
Tree based BFS 基于树的 BFS
102. Binary Tree Level Order Traversal (Medium)
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
递归：
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans = []
def helper(root, depth = 0):
if not root:
return
if depth == len(ans):
ans.append([])
ans[depth].append(root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root)
return ans遍历 BFS：
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans, cur = [], [root]
while cur:
res, nCur = [], []
for root in cur:
res.append(root.val)
if root.left:
nCur.append(root.left)
if root.right:
nCur.append(root.right)
ans.append(res)
cur = nCur
return ans遍历2 DFS：
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return
ans = []
stack = [(root, 0)]
while stack:
root, depth = stack.pop()
if depth == len(ans):
ans.append([])
ans[depth].append(root.val)
if root.right:
stack.append((root.right, depth + 1))
if root.left:
stack.append((root.left, depth + 1))
return ans高频, blind 75
107. Binary Tree Level Order Traversal II (Easy)
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans = []
def helper(root, depth):
if not root:
return
if depth == len(ans) :
ans.insert(0, [])
ans[len(ans) - 1 - depth].append(root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root, 0)
return ans遍历：
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
q = [root]
ans = []
while q:
nq = []
cur = []
for root in q:
cur.append(root.val)
if root.left:
nq.append(root.left)
if root.right:
nq.append(root.right)
ans.insert(0, cur)
q = nq
return ans五刷：高频。list.insert(0, x), 也可用deque的appendleft
103. Binary Tree Zigzag Level Order Traversal (Medium)
LinC 71. Binary Tree Zigzag Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
DFS:
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(root, d):
if not root:
return
if len(ans) - 1 < d:
ans.append(deque())
if d % 2:
ans[d].appendleft(root.val)
else:
ans[d].append(root.val)
dfs(root.left, d + 1)
dfs(root.right, d + 1)
ans = []
dfs(root, 0)
return ansBFS:
class Solution:
def zigzagLevelOrder(self, root):
if not root:
return []
q = [root]
ans = []
zig = True
while q:
ans.append([root.val for root in q])
if not zig:
ans[-1].reverse()
zig = not zig
nq = []
for root in q:
if root.left:
nq.append(root.left)
if root.right:
nq.append(root.right)
q = nq
return ans 3刷：高频
958. Check Completeness of a Binary Tree (Medium)
Given a binary tree, determine if it is a complete binary tree.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example 1:
Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.
Note:
The tree will have between 1 and 100 nodes.
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
q = [root]
noMore = False
while q:
root = q.pop(0)
if root and noMore:
return False
if not root:
noMore = True
else:
q.append(root.left)
q.append(root.right)
return True五刷
Interval
56. Merge Intervals (Medium)
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
高频
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x: x[0])
[pre_s, pre_e] = intervals[0]
ans = []
for s, e in intervals[1:]:
if pre_e >= s:
pre_e = max(pre_e, e)
else:
ans.append([pre_s, pre_e])
pre_s, pre_e = s, e
ans.append([pre_s, pre_e])
return ansBlind 75，面经：Cruise
57. Insert Interval (Medium)
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
写法1：
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
l, r = [], []
for s, e in intervals:
if e < newInterval[0]:
l.append([s, e])
elif s > newInterval[1]:
r.append([s, e])
else:
newInterval[0] = min(newInterval[0], s)
newInterval[1] = max(newInterval[1], e)
return l + [newInterval] + r写法2：
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ans = []
i = 0
ns, ne = newInterval
n = len(intervals)
while i < n and intervals[i][1] < ns:
ans.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= ne:
ns = min(ns, intervals[i][0])
ne = max(ne, intervals[i][1])
i += 1
ans.append([ns, ne])
while i < n:
ans.append(intervals[i])
i += 1
return ansBlind75; 高频
写法1：用左右两个数组装不相交的区间，处理相交的区间，将左右和新区间拼接
写法2：先把结束小于新开始的加到ans里；然后过开始小于等于新结束的，合并区间，加到ans中；最后把剩下的加到ans
还有写法3是把newInterval直接加进原数组，然后排序，然后做上一题的merge，不过时间复杂度是O(nlogn)不如前两种的O(n)
435. Non-overlapping Intervals (Medium)
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key = lambda x: x[1])
ans = 0
pre = intervals[0]
for interval in intervals[1:]:
if pre[1] > interval[0]:
ans += 1
else:
pre = interval
return ansBlind 75; Greedy 贪心算法，优先提前结束的事件。如果下一个结束的事件和前一个事件有交集，既删除它
Meeting Rooms 带锁
920 · Meeting Rooms Lintcode
Given an array of meeting time intervals consisting of start and end times [(s1,e1),(s2,e2),...] (si < ei), determine if a person could attend all meetings.
Example1
Input: intervals = [(0,30),(5,10),(15,20)]
Output: false
Explanation:
(0,30), (5,10) and (0,30),(15,20) will conflict
Example2
Input: intervals = [(5,8),(9,15)]
Output: true
Explanation:
Two times will not conflict
from typing import (
List,
)
from lintcode import (
Interval,
)
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
@param intervals: an array of meeting time intervals
@return: if a person could attend all meetings
"""
def can_attend_meetings(self, intervals: List[Interval]) -> bool:
intervals.sort(key = lambda x: x.start)
for i in range(1, len(intervals)):
if intervals[i].start < intervals[i - 1].end:
return False
return TrueBlind 75
Meeting Rooms II 带锁
919 · Meeting Rooms II Lintcode
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
Example1
Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
Explanation:
We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)
Example2
Input: intervals = [(2,7)]
Output: 1
Explanation:
Only need one meeting room
class Solution:
"""
@param intervals: an array of meeting time intervals
@return: the minimum number of conference rooms required
"""
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
# Write your code here
events = []
for interval in intervals:
events.append((interval.start, 1))
events.append((interval.end, -1))
events.sort()
cur_room = 0
ans = 0
for _, e_type in events:
cur_room += e_type
ans = max(ans, cur_room)
return ansBlind 75
Binary Search & LogN Algorithm
二分法模板: start + 1 < end; start + (end - start) / 2; A[mid] ==, <, >; A[start] A[end] ? target
704. Binary Search (Easy)
Find any position of a target number in a sorted array. Return -1 if target does not exist.
Example
Given [1, 2, 2, 4, 5, 5].
For target = 2, return 1 or 2.
For target = 5, return 4 or 5.
For target = 6, return -1.
Challenge
O(logn) time
class Solution:
"""
@param: nums: An integer array sorted in ascending order
@param: target: An integer
@return: An integer
"""
def findPosition(self, nums, target):
# write your code here
if (len(nums) == 0):
return -1
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid] == target):
return mid
elif (nums[mid] < target):
start = mid
else:
end = mid
if (nums[start] == target):
return start
if (nums[end] == target):
return end
return -1
总结：背好模板，lintcode 的 test case 包含空输入数组，需要 python3 的 // 整除运算符才能过
二刷：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0 or (len(nums) == 1 and nums[0] != target):
return -1
return self.helper(nums, target, 0, len(nums) - 1)
def helper(self, nums, target, start, end):
if (start > end):
return -1
if (start + 1 == end):
if nums[end] == target:
return end
if nums[start] == target:
return start
else:
return -1
mid = start + (end - start) // 2
if (nums[mid] == target):
return mid
elif (nums[mid] < target):
start = mid
else:
end = mid
return self.helper(nums, target, start, end)总结：不背模板也能写。 但是写出来不如模板的优雅。如果递归调用前面不加 return 的话，还会发生不 return 的情况
LinC 14. First Position of Target (Easy)
Description
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Have you met this question in a real interview?
Example
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
Challenge
If the count of numbers is bigger than 2^32, can your code work properly?
思路：找到了不要 return，扔掉大的一半，继续找
class Solution:
"""
@param nums: The integer array.
@param target: Target to find.
@return: The first position of target. Position starts from 0.
"""
def binarySearch(self, nums, target):
# write your code here
if (len(nums) == 0):
return -1
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid] >= target):
end = mid
else:
start = mid
if (nums[start] == target):
return start
if (nums[end] == target):
return end
return -1总结：背好模板，模板 v5
278. First Bad Version (Easy)
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l, r = 0, n
while l + 1 < r:
mid = l + (r - l) // 2
if not isBadVersion(mid):
l = mid + 1
else:
r = mid
return l if isBadVersion(l) else r3刷: 高频
34. Find First and Last Position of Element in Sorted Array (Medium)
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums or target < nums[0] or target > nums[-1]:
return [-1, -1]
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = (l + r) // 2
if nums[mid] < target:
l = mid + 1
else:
r = mid
ans = [-1, -1]
if nums[l] == target:
ans[0] = l
elif nums[r] == target:
ans[0] = r
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = (l + r) // 2
if nums[mid] > target:
r = mid - 1
else:
l = mid
if nums[r] == target:
ans[1] = r
elif nums[l] == target:
ans[1] = l
return ans3刷：高频，二分法找 Target, 两次二分法，一次找左边界，一次找右边界
LinC 61. Search for a Range (Medium)
Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Challenge
O(log n) time.
思路：找一个数的第一次和最后一次出现的 index
class Solution:
"""
@param A: an integer sorted array
@param target: an integer to be inserted
@return: a list of length 2, [index1, index2]
"""
def searchRange(self, A, target):
# write your code here
firstO, lastO = -1, -1
if len(A) == 0:
return [firstO, lastO]
start, end = 0, len(A) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (A[mid] < target):
start = mid
else:
end = mid
if (A[end] == target):
firstO = end
if (A[start] == target):
firstO = start
start, end = 0, len(A) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (A[mid] <= target):
start = mid
else:
end = mid
if (A[start] == target):
lastO = start
if (A[end] == target):
lastO = end
return [firstO, lastO]总结：注意检查空输入！
852. Peak Index in a Mountain Array
LinC 585. Maximum Number in Mountain Sequence (Medium)
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
思路：切一刀，判断递增就扔左边，递减就扔右边， 不然就找到了中点
二刷：
class Solution:
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
start, end = 0, len(A) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if A[mid - 1] < A[mid] < A[mid + 1]:
start = mid
elif A[mid - 1] > A[mid] > A[mid + 1]:
end = mid
else:
return mid
return start if A[start] > A[end] else end总结：二刷写法跟一刷一样，哪怕是简单的题，题要看清楚， mid min 不要拼错
162. Find Peak Element (Medium)
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
Note:
Your solution should be in logarithmic complexity.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
def get(i):
if i == -1 or i == n:
return float('-inf')
return nums[i]
n = len(nums)
l, r = 0, n - 1
while l + 1 < r:
mid = l + (r - l) // 2
if nums[mid - 1] < nums[mid] > nums[mid + 1]:
return mid
elif nums[mid - 1] < nums[mid] < nums[mid + 1]:
l = mid + 1
else:
r = mid - 1
return r if nums[l] < nums[r] else l写法2：
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
def get(i):
if i == -1 or i == n:
return float('-inf')
return nums[i]
def bs(l, r):
mid = (l + r) // 2
if get(mid - 1) < get(mid) > get(mid + 1):
return mid
elif get(mid - 1) < get(mid) < get(mid + 1):
return bs(mid + 1, r)
else:
return bs(l, mid - 1)
n = len(nums)
return bs(0, n - 1)2刷：面经，Quora。关键要知道切中点，如果是///向上，则顶点在右，如果/^\则找到顶点，否则顶点在左
74. Search a 2D Matrix (Medium)
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m, n = len(matrix), len(matrix[0])
l, r = 0, m - 1
while l + 1 < r:
mid = (l + r) // 2
if matrix[mid][0] == target:
return True
elif matrix[mid][0] < target:
l = mid
else:
r = mid - 1
tr = l if matrix[r][0] > target else r
l, r = 0, n - 1
while l + 1 < r:
mid = (l + r) // 2
if matrix[tr][mid] == target:
return True
elif matrix[tr][mid] < target:
l = mid + 1
else:
r = mid - 1
return matrix[tr][l] == target or matrix[tr][r] == target3刷：高频
153. Find Minimum in Rotated Sorted Array (Medium)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
遍历
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = (l + r) // 2
if nums[mid] < nums[r]:
r = mid
else:
l = mid + 1
return min(nums[l], nums[r])递归
class Solution:
def findMin(self, nums: List[int]) -> int:
def helper(l, r):
if l == r:
return nums[l]
mid = l + (r - l) // 2
if nums[mid] < nums[r]:
return helper(l, mid)
else:
return helper(mid + 1, r)
return helper(0, len(nums) - 1)Blind 75; 答案肯定在转折的区间里， 因此，如果右边是连续的，那答案可能在mid及左半边，否则就一定不在左半边（mid已经不是最小了）
33. Search in Rotated Sorted Array (Medium)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n - 1
while l + 1 < r:
mid = (l + r) // 2
if nums[mid] < nums[r]:
if nums[mid] <= target <= nums[r]:
l = mid
else:
r = mid - 1
else:
if nums[l] <= target <= nums[mid]:
r = mid
else:
l = mid + 1
if nums[l] == target:
return l
if nums[r] == target:
return r
return -1高频
81. Search in Rotated Sorted Array II (Medium)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
class Solution:
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
l, r = 0, n - 1
while l + 1 < r:
mid = (l + r) // 2
if nums[l] == nums[mid]:
l += 1
elif nums[mid] == nums[r]:
r -= 1
elif nums[mid] < nums[r]:
if nums[mid] <= target <= nums[r]:
l = mid
else:
r = mid - 1
else:
if nums[l] <= target <= nums[mid]:
r = mid
else:
l = mid + 1
return target == nums[l] or target == nums[r]高频
69. Sqrt(x) (Easy)
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x
while l + 1 < r:
mid = l + (r - l) // 2
if mid * mid <= x < (mid + 1) * (mid + 1):
return mid
elif mid * mid < x:
l = mid + 1
else:
r = mid - 1
return l if l * l <= x < (l + 1) * (l + 1) else r高频：统一模板...l + 1 < r...if mid * mid <= x <(mid + 1) * (mid + 1)...return l if l * l <= x <...
35. Search Insert Position (Easy)
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid
else:
r = mid
if target <= nums[l]:
return l
if target <= nums[r]:
return r
return len(nums)高频：...l = mid...if target <= nums[l]: return l...return len(nums)
658. Find K Closest Elements (Medium)
LinC 460. Find K Closest Elements (Medium)
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 104
Absolute value of elements in the array and x will not exceed 104
UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n = len(arr)
l, r = 0, n - 1
while l + 1 < r:
mid = (l + r) // 2
if arr[mid] < x:
l = mid
else:
r = mid
ans = deque()
while l >= 0 and r < n and len(ans) < k:
if abs(arr[l] - x) <= abs(arr[r] - x):
ans.appendleft(arr[l])
l -= 1
else:
ans.append(arr[r])
r += 1
while l >= 0 and len(ans) < k:
ans.appendleft(arr[l])
l -= 1
while r < n and len(ans) < k:
ans.append(arr[r])
r += 1
return ans4刷：二分查找 target，将 l, r 指针放到离x最近的位置...if arr[mid] < x: l = mid else: r = mid...；然后开始往结果里填充k个数
网上还有一种很妖的二分查找一步到位解法，破坏了模板，核心原理是l, r = 0, len(arr) - k...if x - arr[mid] > arr[mid + k] - x: l = mid + 1 else: r = mid; return arr[l: l + k]
528. Random Pick with Weight (Medium)
You are given an array of positive integers w where w[i] describes the weight of ith index (0-indexed).
We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. pickIndex() should return the integer proportional to its weight in the w array. For example, for w = [1, 3], the probability of picking the index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) while the probability of picking the index 1 is 3 / (1 + 3) = 0.75 (i.e 75%).
More formally, the probability of picking index i is w[i] / sum(w).
Example 1:
Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. Since there is only one single element on the array the only option is to return the first element.
Example 2:
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It's returning the second element (index = 1) that has probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It's returning the first element (index = 0) that has probability of 1/4.
Since this is a randomization problem, multiple answers are allowed so the following outputs can be considered correct :
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
Constraints:
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex will be called at most 10000 times.
class Solution:
def __init__(self, w: List[int]):
for i in range(1, len(w)):
w[i] += w[i - 1]
self.w = w
def pickIndex(self) -> int:
target = random.randint(1, self.w[-1])
l, r = 0, len(self.w) - 1
while l + 1 < r:
mid = (l + r) // 2
if self.w[mid] < target:
l = mid + 1
elif self.w[mid] > target:
r = mid
else:
return mid
return l if self.w[l] >= target else r2刷：高频
981. Time Based Key-Value Store (Medium)
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.
Implement the TimeMap class:
TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".
Example 1:
Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]
Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1); // return "bar"
timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "ba2r" along with timestamp = 4.
timeMap.get("foo", 4); // return "bar2"
timeMap.get("foo", 5); // return "bar2"
Constraints:
1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits.
1 <= timestamp <= 107
All the timestamps timestamp of set are strictly increasing.
At most 2 * 105 calls will be made to set and get.
class TimeMap:
def __init__(self):
self.d = collections.defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.d[key].append((value, timestamp))
def get(self, key: str, timestamp: int) -> str:
if key not in self.d or self.d[key][0][1] > timestamp:
return ""
arr = self.d[key]
l, r = 0, len(arr) - 1
while l + 1 < r:
mid = (l + r) // 2
if arr[mid][1] > timestamp:
r = mid - 1
else:
l = mid
if arr[r][1] <= timestamp:
return arr[r][0]
return arr[l][0]use bisect:
class TimeMap:
def __init__(self):
self.d = collections.defaultdict(list)
self.dt = collections.defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.d[key].append(value)
self.dt[key].append(timestamp)
def get(self, key: str, timestamp: int) -> str:
if key not in self.d:
return ""
i = bisect.bisect(self.dt[key], timestamp)
return self.d[key][i - 1] if i else ""4刷：高频
Two pointers
LinC 373. Partition Array by Odd and Even (Easy)
Partition an integers array into odd number first and even number second.
Example
Given [1, 2, 3, 4], return [1, 3, 2, 4]
思路：双指针一头一尾，碰到不符合的就换。
class Solution:
"""
@param: nums: an array of integers
@return: nothing
"""
def partitionArray(self, nums):
# write your code here
if len(nums) < 2:
return
l, r = 0, len(nums) - 1
while l < r:
while l < r and nums[l] % 2 != 0:
l += 1
while l < r and nums[r] % 2 == 0:
r -= 1
if nums[l] % 2 == 0 or nums[r] % 2 != 0:
nums[l], nums[r] = nums[r], nums[l]
if nums[l] % 2 == 0 or nums[r] % 2 != 0:
nums[l], nums[r] = nums[r], nums[l]总结：送两个测试数据进去就能写对。 最后两个 if 可以简化。
26. Remove Duplicates from Sorted Array (Easy)
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路：简单题， 慢指针只有在快指针碰到不同的值才走。
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
slow, fast = 0, 1
while fast < len(nums):
if nums[fast] == nums[slow]:
fast += 1
else:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1总结：纯热身，秒解
二刷
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
slow, fast = 0, 1
while fast < len(nums):
if nums[slow] == nums[fast]:
fast += 1
else:
slow += 1
nums[slow], nums[fast] = nums[fast], nums[slow]
fast += 1
return slow + 1总结：虽然是容易热身题，却要思考两个问题，第一，数组需要 in place sort, 需要利用已经排好序这个条件来在 slow 往前一个以后交换 slow 和 fast 的数； 第二，返回 slow + 1 可以省一个 ans 变量
高频: ...else: slow += 1; nums[slow], nums[fast] = nums[fast], nums[slow]; fast += 1...
80. Remove Duplicates from Sorted Array II (Medium)
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
It doesn't matter what values are set beyond the returned length.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
w = 0
for i, n in enumerate(nums):
if i < 2 or n != nums[w - 2]:
nums[w] = n
w += 1
return w高频：反正两周前的代码也看不懂了，抄个简单一点的...if i < 2 or n != nums[w - 2]
28. Implement strStr() (Easy)
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
思路：快慢指针
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if len(needle) == 0:
return 0
if len(haystack) == 0:
return -1
for i in range(len(haystack)):
if haystack[i] == needle[0]:
if i + len(needle) - 1 < len(haystack):
if needle == haystack[i: i + len(needle)]:
return i
else:
return -1
return -1总结: 思路是双指针没问题，实际用 python 的时候可以用 python 的性质直接取子串
二刷：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
if len(haystack) == 0:
return -1
end = len(haystack) - len(needle) + 1
if end < 0:
return -1
for i in range(0, end):
if haystack[i:i + len(needle)] == needle:
return i
return -1总结：注意空串的时候要返回 int 而不是 bool, needle 为空时，直接返回 0, 优化 end = len(haystack) - len(needle) + 1; if end < 0: return -1; for i in range(0, end)
高频：考点 end = lh - ln + 1; ... if haystack[i:i + ln] == needle: return i。代码能优化一点点，但是大同小异。
283. Move Zeroes (Easy)
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
l, r = 0, 0
n = len(nums)
while r < n:
while nums[r] < n and nums[r] == 0:
r += 1
nums[l], nums[r] = nums[r], nums[l]
l += 1
r += 16刷：高频：l，r从0，0开始，l，r永远前进，省去很多判断的麻烦
125. Valid Palindrome (Easy)
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:
Input: "race a car"
Output: false
思路：头尾双指针， 碰头了返回 True，相同继续走，不同返回 False
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return TrueBlind 75; 高频
680. Valid Palindrome II (Easy)
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
暴力 TLE：
class Solution:
def validPalindrome(self, s: str) -> bool:
for i in range(len(s)):
t = s[:i] + s[i + 1:]
if t == t[::-1]:
return True
return False双指针：
class Solution:
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
break
l += 1
r -= 1
if l == r:
return True
s1 = s[:l] + s[l + 1:]
s2 = s[:r] + s[r + 1:]
return s1 == s1[::-1] or s2 == s2[::-1]3刷，高频
1. Two Sum (Easy)
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution:
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]class Solution(object):
def twoSum(self, nums, target):
remain = {}
for i, n in enumerate(nums):
if n in remain:
return [remain[n], i]
remain[target - n] = i一刷，高频，面经：维萨。简化代码， 双指针， hashmap
167. Two Sum II - Input array is sorted (Easy)
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
思路：增加了 sorted 这个条件， 第一感觉是可以折半查找了。固定 index1，index2 用折半查找获得
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for index1 in range(len(numbers)):
start, end = index1 + 1, len(numbers) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if numbers[index1] + numbers[mid] == target:
return [index1 + 1, mid + 1]
elif numbers[index1] + numbers[mid] < target:
start = mid + 1
else:
end = mid - 1
if numbers[index1] + numbers[start] == target:
return [index1 + 1, start + 1]
elif numbers[index1] + numbers[end] == target:
return [index1 + 1, end + 1]总结：要细心。1.题中 answers are not zero-based 2.要测两个情况 [2, 7, 19], 9 和 [5, 25, 75] 可以测出代码的问题
二刷：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
tsum = numbers[l] + numbers[r]
if tsum == target:
return [l + 1, r + 1]
if tsum < target:
l += 1
else:
r -= 1总结：二分法跑分不如直接双指针，可能是测试数据导致。双指针代码也简单很多
LinC 607. Two Sum III - Data structure design (Easy)
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
Example
add(1); add(3); add(5);
find(4) // return true
find(7) // return false
思路：add 的时候把 sum 都存 dict 里面， 查的时候直接返回 dict 里面有没有 sum. 会超时。
class TwoSum:
keys = {}
"""
@param: number: An integer
@return: nothing
"""
def add(self, number):
# write your code here
if number not in self.keys:
self.keys[number] = 1
else:
self.keys[number] = 2
"""
@param: value: An integer
@return: Find if there exists any pair of numbers which sum is equal to the value.
"""
def find(self, value):
# write your code here
for key in self.keys:
if value - key in self.keys:
if value - key == key:
if self.keys[key] == 2:
return True
else:
return True
return False总结：虽然是一道容易题， 第一反应的思路会超时。 需要在 find 的时候判断能凑出答案的另一个 key 是不是已经在 keys 里了。而不是先存好 sum。 还要判断两个数相同的时候有没有存过两个数。
15. 3Sum (Medium)
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
O(n^2)：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
n = len(nums)
nums.sort()
for i in range(n - 2):
if i and nums[i - 1] == nums[i]:
continue
l, r = i + 1, n - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total == 0:
ans.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif total > 0:
r -= 1
else:
l += 1
return ansBlind 75; 面经：维萨
LinC 382. Triangle Count (Medium)
Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?
Example
Given array S = [3,4,6,7], return 3. They are:
[3,4,6]
[3,6,7]
[4,6,7]
Given array S = [4,4,4,4], return 4. They are:
[4(1),4(2),4(3)]
[4(1),4(2),4(4)]
[4(1),4(3),4(4)]
[4(2),4(3),4(4)]
思路： 判断能不能做三角形以后全排列
class Solution:
"""
@param S: A list of integers
@return: An integer
"""
def triangleCount(self, S):
# write your code here
S.sort(reverse=True)
sum = 0
for index1, longest in enumerate(S):
head, tail = index1 + 1, index1 + 2
while tail < len(S) and S[head] + S[tail] > longest:
tail += 1
tail -= 1
while head < tail:
sum += tail - head
head += 1
while head < tail and S[head] + S[tail] <= longest:
tail -= 1
return sum总结：看清题目，问的是有多少个这样的三角形， 返回数就行。 全排列效率比较低。 更优解是每次定下最长边， 寻找符合条件的另外两个边的数量。 双指针的解法是将 tail 推到最小不能组成三角形的位置， 退一步， 然后从 tail 到 head 的位置的都可以组， 因为他们相加只会比最长边更长。 然后将 head 进一步（缩短），tail 边加长到大于最长边的位置，新 tail 到 head 的位置又都可以组。
16. 3Sum Closest (Medium)
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
ans = None
nums.sort()
for i in range(len(nums) - 2):
l, r = i + 1, len(nums) - 1
while l < r:
t = nums[i] + nums[l] + nums[r]
if t == target:
return t
elif t < target:
l += 1
else:
r -= 1
if ans == None or abs(t - target) < abs(ans - target):
ans = t
return ans高频：将1，2刷的代码思路总结都删了，都差不多。注意这里没有mid，不是二分查找。
LinC 31. Partition Array (Medium)
Description
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:
All elements < k are moved to the left
All elements >= k are moved to the right
Return the partitioning index, i.e the first index i nums[i] >= k.
You should do really partition in array nums instead of just counting the numbers of integers smaller than k.
If all elements in nums are smaller than k, then return nums.length
Example
If nums = [3,2,2,1] and k=2, a valid answer is 1.
Challenge
Can you partition the array in-place and in O(n)?
class Solution:
def partitionArray(self, nums, k):
if len(nums) == 0:
return 0
l, r = 0, len(nums) - 1
while l <= r:
while l < len(nums) and nums[l] < k:
l += 1
while r >= 0 and nums[r] >= k:
r -= 1
if l > r:
break
nums[l], nums[r] = nums[r], nums[l]
return l总结：注意：1。while 的条件是 l <= r 2.l > r 的时候需要 break
215. Kth Largest Element in an Array (Medium)
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def qs(l, r):
p = findP(l, r)
if p == k - 1:
return nums[p]
elif p < k - 1:
return qs(p + 1, r)
else:
return qs(l, p - 1)
def findP(l, r):
rP = random.randint(l, r)
nums[rP], nums[r] = nums[r], nums[rP]
i = l
for j in range(l, r):
if nums[j] > nums[r]:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[r] = nums[r], nums[i]
return i
return qs(0, len(nums) - 1)4刷，由于完全抛弃另一侧，时间复杂度平均由 quick sort 的 O(nlogn) 降为 O(n) 因为输入变小了， quicksort 的输入一直是 n, 最差情况 O(n^2)
面经：维萨
75. Sort Colors (Medium)
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?
二刷：
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return
l, r, i = 0, len(nums) - 1, 0
while i <= r:
if nums[i] == 0 and i > l:
nums[l], nums[i] = nums[i], nums[l]
l += 1
elif nums[i] == 2 and i < r:
nums[i], nums[r] = nums[r], nums[i]
r -= 1
else:
i += 1总结：in place 不数元素的话得用 l, r 和 i, 要过的话需要熟记交换的第二条件分别为 i > l 和 i < r, 其他情况 i 均前进
高频：去掉了一刷繁琐的方法。counting sort只需要count 0和1。1 pass：...while i <= r:...and i > l:...and i < r:...
面经：Celo。3个数要保持两个边界l和r，和一个worker i，交换条件要加...i > l...和...i < r，否则会过度交换导致结果有bug
18. 4Sum (Medium)
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路：看了下三年前的答案，不是特别直观。看了九章的答案，貌似好理解一点：去重，枚举一个数，然后用 3Sum 的做法，O(N^3)
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
ans = []
for i in range(0, len(nums) - 3):
if i and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 2):
if j != i + 1 and nums[j] == nums[j - 1]:
continue
l, r = j + 1, len(nums) - 1
while l < r:
sum = nums[i] + nums[j] + nums[l] + nums[r]
if sum == target:
ans.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif sum < target:
l += 1
else:
r -= 1
return ans总结：有一个自己肯定想不出的条件就是第二层循环怎么跳过：if j != i + 1 and nums[j] == nums[j - 1]: continue; 非常勉强能过 AC. 看了网上和三年前的，都是用 dict 先存 2sum，然后再 loop 两遍，用 if pair[0] > j 来去重（第三个元素的 index 要大于前面两个）。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
ans = []
def nsum(l, r, N, target, path):
if r - l + 1 < N or N < 2 or N > len(nums) or N * nums[l] > target or N * nums[r] < target:
return
if N == 2:
while l < r:
t = nums[l] + nums[r]
if t == target:
ans.append(path + [nums[l], nums[r]])
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
elif t < target:
l += 1
else:
r -= 1
else:
for i in range(l, r + 1):
if i == l or (i > l and nums[i] != nums[i - 1]):
nsum(i + 1, r, N - 1, target - nums[i], path + [nums[i]])
nums.sort()
nsum(0, len(nums) - 1, 4, target, [])
return ans二刷：看 leetcode ac 的流行答案， 返回递归 nsum， 递归内终结条件为解决 2sum，，注意两处去重，1.找到 target 以后，在 l < r 条件下跳过所有后面与 l 相同的；2.进入 nsum 前，if i == 0 or (i > 0 and nums[i - 1] != nums[i])
总结：很多坑，N == 2 时要注意 while l < r 做二分法；N > 2 时 for i in range(l, r + 1); nsum(i + 1, ...); 如是高频题需要练熟
高频：...def nsum(l, r, N, target, path): if r - l + 1 < N or N < 2 or...if N == 2: while l < r:... while l < r and nums[l] == nums[l + 1]:...while...l += 1; r -= 1... for i in range(l, r + 1): if (i == l) or...: nsum(i + 1, r...)...
27. Remove Element
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn't matter what values are set beyond the returned length.
高频
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
ans = len(nums)
i = 0
j = ans - 1
while i <= j:
while i <= j and nums[i] != val:
i += 1
while i <= j and nums[j] == val:
j -= 1
ans -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
return ans总结：背while i <= j: while i <= j and ... while i <= j and ...if i < j: ...
11. Container With Most Water (Medium)
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
hl, hr = height[l], height[r]
ans = max(ans, (r - l) * min(hl, hr))
if hl < hr:
l += 1
else:
r -= 1
return ansBlind 75; 高频：双指针往中心走，面积是：(r − l) × min(height[l], height[r]), 优先收缩矮的（对总面积贡献小的）一边
345. Reverse Vowels of a String (Easy)
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Input: "hello"
Output: "holle"
Example 2:
Input: "leetcode"
Output: "leotcede"
Note:
class Solution:
def reverseVowels(self, s: str) -> str:
stack = []
for c in s:
if c in "aeiouAEIOU":
stack.append(c)
for i, c in enumerate(s):
if c in "aeiouAEIOU":
s = s[:i] + stack.pop() + s[i + 1:]
return sinplace:
class Solution:
def reverseVowels(self, s: str) -> str:
l, r = 0, len(s) - 1
arr = list(s)
while l < r:
while arr[l] not in "aeiouAEIOU" and l < len(s) - 1:
l += 1
while arr[r] not in "aeiouAEIOU" and r > 0:
r -= 1
if l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
return "".join(arr)面经：DJI。
BFS 广度优先搜索
695. Max Area of Island (Medium)
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
BFS：
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0
m, n = len(grid), len(grid[0])
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
res = 0
q = deque()
q.append((r, c))
grid[r][c] = 0
while q:
(rq, cq) = q.popleft()
res += 1
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = rq + dr, cq + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
q.append((nr, nc))
ans = max(ans, res)
return ansDFS：
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(r, c):
nonlocal res
res += 1
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
dfs(nr, nc)
m, n = len(grid), len(grid[0])
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
res = 0
grid[i][j] = 0
dfs(i, j)
ans = max(ans, res)
return ans3刷：BFS注意清零的位置要在放 queue 之后立刻清零，以防同一个点入两次
133. Clone Graph (Medium)
Given a reference of a node in a connected undirected graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Constraints
The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
dfs:
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
def helper(node):
if node not in d:
d[node] = Node(node.val)
for neighbor in node.neighbors:
if neighbor not in d:
helper(neighbor)
d[node].neighbors.append(d[neighbor])
return d[node]
if not node:
return
d = {}
return helper(node)bfs
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return
d = {node: Node(node.val)}
q = deque([node])
while q:
p = q.popleft()
for neighbor in p.neighbors:
if neighbor not in d:
d[neighbor] = Node(neighbor.val)
q.append(neighbor)
d[p].neighbors.append(d[neighbor])
return d[node]Blind 75; 高频
127. Word Ladder (Medium)
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
可以输出此path：
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or len(beginWord) != len(endWord):
return 0
q = [[beginWord]]
wordList = set(wordList)
visited = set()
while q:
curPath = q.pop(0)
curWord = curPath[-1]
if curWord == endWord:
return len(curPath)
for i in range(len(curWord)):
for c in [chr(x) for x in range(ord("a"), ord("z") + 1)]:
newW = curWord[:i] + c + curWord[i + 1:]
if newW in wordList and newW not in visited:
visited.add(newW)
q.append(curPath + [newW])
return 0精简无需输出path：
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or len(beginWord) != len(endWord):
return 0
q = [(beginWord, 1)]
wordList = set(wordList)
visited = set()
while q:
word, length = q.pop(0)
if word == endWord:
return length
for i in range(len(word)):
for c in [chr(i) for i in range(ord("a"), ord("z"))]:
newW = word[:i] + c + word[i + 1:]
if newW in wordList and newW not in visited:
visited.add(newW)
q.append((newW, length + 1))
return 0面试：DJI
三刷：注意简版需要visited
LinC 611. Knight Shortest Path (Medium)
Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if knight can not reached.
source and destination must be empty.
Knight can not enter the barrier.
Clarification
If the knight is at (x, y), he can get to the following positions in one step:
(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)
Example
[[0,0,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2] return 2
[[0,1,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2] return 6
[[0,1,0],
[0,0,1],
[0,0,0]]
source = [2, 0] destination = [2, 2] return -1
思路：没什么思路， 看了下答案，就是 BFS 硬来，需要检查走了某个方向以后是不是还是在棋盘内
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
class Solution:
"""
@param grid: a chessboard included 0 (false) and 1 (true)
@param source: a point
@param destination: a point
@return: the shortest path
"""
def shortestPath(self, grid, source, destination):
# write your code here
if len(grid) == 0 or (len(grid[0]) == 1 and grid[0][0] == 1):
return -1
ans = 0
dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [2, -2, 2, -2, 1, -1, 1, -1]
q = collections.deque([source])
grid[source.x][source.y] = 1
while q:
qlen = len(q)
next_q = collections.deque()
for i in range(qlen):
pt = q.popleft()
if pt.x == destination.x and pt.y == destination.y:
return ans
for move in range(len(dx)):
nextPt = Point(pt.x + dx[move], pt.y + dy[move])
if (self.isInbound(grid, nextPt) and grid[nextPt.x][nextPt.y] == 0):
next_q.append(nextPt)
grid[nextPt.x][nextPt.y] = 1
ans += 1
q = next_q
return -1
def isInbound(self, grid, pt):
return pt.x >= 0 and pt.x < len(grid) and pt.y >= 0 and pt.y < len(grid[0])总结：注意 isInbound 要查的是 >=0 和 < len()， 其他的问题可以通过跑一个测试数据发现
785. Is Graph Bipartite? (Medium)
Given an undirected graph, return true if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
Note:
graph will have length in range [1, 100].
graph[i] will contain integers in range [0, graph.length - 1].
graph[i] will not contain i or duplicate values.
The graph is undirected: if any element j is in graph[i], then i will be in graph[j].
DFS:
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
def dfs(n, color):
if n in d:
return color == d[n]
d[n] = color
return all(dfs(v, -color) for v in graph[n])
d = {}
return all(dfs(i, 1) for i in range(len(graph)) if i not in d)BFS:
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
d = {}
for i in range(len(graph)):
if i not in d:
d[i] = 1
s = [(i, 1)]
while s:
n, color = s.pop()
for v in graph[n]:
if v in d:
if color == d[v]:
return False
else:
d[v] = -color
s.append((v, -color))
return True3刷：思路：用染色的方法，可以用 DFS, BFS 给所有 node 染上两种色中的一种。1.如未上色，上色，给相邻节点上相反色 2.如已上色，DFS: 要和当前要上的色相同 BFS：要和pop出来的颜色相反
LinC 178. Graph Valid Tree (Medium)
Leetcode 261. Graph Valid Tree 带锁
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
写法1：
class Solution:
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
graph = collections.defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = set()
def helper(v):
if v not in seen:
seen.add(v)
for neighbor in graph[v]:
if neighbor not in seen:
helper(neighbor)
helper(0)
return len(seen) == n写法2：
class Solution:
def validTree(self, n, edges):
if len(edges) != n - 1:
return False
graph = collections.defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
q = collections.deque([0])
res = set()
while q:
v = q.popleft()
res.add(v)
for neighbor in graph[v]:
if neighbor not in res:
q.append(neighbor)
return len(res) == nBlind 75; 注意: 已经访问过的节点不要入 q，不然无向图的边会导致死循环
130. Surrounded Regions (Medium)
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board:
return
m, n = len(board), len(board[0])
rule = lambda ij: 0 <= ij[0] < m and 0 <= ij[1] < n and board[ij[0]][ij[1]] == 'O'
q = list(filter(rule, [ij for k in range(max(m, n)) for ij in [(0, k), (k, 0), (m - 1, k), (k, n - 1)]]))
while q:
(i, j) = q.pop()
board[i][j] = 'S'
q += list(filter(rule, [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]))
for i in range(m):
for j in range(n):
if board[i][j] == 'S':
board[i][j] = 'O'
else:
board[i][j] = 'X'高频：需要改为q.pop(0)才是BFS，否则是DFS，但是代码风格放在BFS比较合适
675. Cut Off Trees for Golf Event (Hard)
You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:
0 represents the obstacle can't be reached.
1 represents the ground can be walked through.
The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree's height.
You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).
You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.
You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.
Example 1:
Input:
[
[1,2,3],
[0,0,4],
[7,6,5]
]
Output: 6
Example 2:
Input:
[
[1,2,3],
[0,0,0],
[7,6,5]
]
Output: -1
Example 3:
Input:
[
[2,3,4],
[0,0,5],
[8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
class Solution:
def cutOffTree(self, forest):
m, n = len(forest), len(forest[0])
trees = [[forest[r][c], r, c] for r in range(m) for c in range(n) if forest[r][c] > 1]
trees.sort(key = lambda x: x[0])
ans = 0
nextR, nextC = 0, 0
for h, r, c in trees:
step = self.bfs(forest, nextR, nextC, r, c, m, n)
if step == -1:
return -1
else:
forest[r][c] = 1
nextR, nextC = r, c
ans += step
return ans
def bfs(self, forest, startR, startC, endR, endC, m, n):
step = 0
q = [(startR, startC)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
while q:
nq = []
for _ in range(len(q)):
r, c = q.pop()
if r == endR and c == endC:
return step
visited.add((r, c))
for dr, dc in dirs:
if 0 <= r + dr <= m - 1 and 0 <= c + dc <= n - 1 and forest[r + dr][c + dc] != 0 and (r + dr, c + dc) not in visited:
nq.append((r + dr, c + dc))
step += 1
q = nq
return -1面经：Amazon。比较不偏门的算法，可惜会TLE
310. Minimum Height Trees (Medium)
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
Example 2 :
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
Note:
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if not edges:
return [0]
from collections import defaultdict
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
leaves = [k for k, v in adj.items() if len(v) == 1]
while n > 2:
n -= len(leaves)
newLeaves = []
for u in leaves:
v = adj[u].pop()
adj[v].remove(u)
if len(adj[v]) == 1:
newLeaves.append(v)
leaves = newLeaves
return leaves一刷：Facebook tag，leetcode 讨论区解法
LinC 178 · Graph Valid Tree (Medium)
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Example 1:
Input: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true.
Example 2:
Input: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false.
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
graph = collections.defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = set()
q = collections.deque([0])
while q:
v = q.popleft()
seen.add(v)
for neighbor in graph[v]:
if neighbor not in seen:
q.append(neighbor)
return len(seen) == nBlind 75
todo union find 写法
Topological sorting 拓扑排序
LinC 127. Topological Sorting (Medium)
Given an directed graph, a topological order of the graph nodes is defined as follow:
For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.
You can assume that there is at least one topological order in the graph.
Clarification
Learn more about representation of graphs
Example:
For graph as follow:
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
思路：拓扑排序，算法貌似是：1.统计每个点的入度；2.将入度为 0 的点入 queue；3.从队列中 pop 点，去掉所有指向别的点的边: 相应点入度 -1；4.新入度为 0 的点入 queue
"""
Definition for a Directed graph node
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
"""
class Solution:
"""
@param: graph: A list of Directed graph node
@return: Any topological order for the given graph.
"""
def topSort(self, graph):
# write your code here
if len(graph) == 0:
return []
ans = []
inBound = {}
for node in graph:
if node not in inBound:
inBound[node] = 0
for neighbor in node.neighbors:
if neighbor not in inBound:
inBound[neighbor] = 0
inBound[neighbor] += 1
q = collections.deque()
for node in inBound:
if inBound[node] == 0:
q.append(node)
while q:
zNode = q.popleft()
ans.append(zNode)
for node in zNode.neighbors:
inBound[node] -= 1
if inBound[node] == 0:
q.append(node)
return ans总结：顺利。但是题目没有说清楚 return 的是一个拓扑排序好的 node 的 list
207. Course Schedule (Medium)
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
indeg = Counter()
for u, v in prerequisites:
graph[v].append(u)
indeg[u] += 1
stack = [c for c in range(numCourses) if indeg[c] == 0]
while stack:
for course in graph[stack.pop()]:
indeg[course] -= 1
if indeg[course] == 0:
stack.append(course)
return sum(indeg.values()) == 0Blind 75; 面经：Cruise
210. Course Schedule II (Medium)
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .
Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
p2c = collections.defaultdict(list)
inD = [0] * numCourses
for [c, p] in prerequisites:
p2c[p].append(c)
inD[c] += 1
q = [i for i in range(numCourses) if inD[i] == 0]
ans = q[:]
while q:
p = q.pop()
for c in p2c[p]:
inD[c] -= 1
if inD[c] == 0:
ans.append(c)
q.append(c)
return ans if len(ans) == numCourses else []2刷：面经：Cruise。时间复杂度：O(v + e) number of vertices and edges, 空间复杂度: O(v + e)
LinC 892 · Alien Dictionary (Hard)
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
- You may assume all letters are in lowercase
- At first different letter, if the letter in s precedes the letter in t in the given list order, then the dictionary order of s is less than t
- The dictionary is invalid, if string a is prefix of string b and b is appear before a
- If the order is invalid, return an empty string
- There may be multiple valid order of letters, return the smallest in normal lexicographical order
- The letters in one string are of the same rank by default and are sorted in Human dictionary order
Example 1:
Input：["wrt","wrf","er","ett","rftt"]
Output："wertf"
Explanation：
from "wrt"and"wrf" ,we can get 't'<'f'
from "wrt"and"er" ,we can get 'w'<'e'
from "er"and"ett" ,we can get 'r'<'t'
from "ett"and"rftt" ,we can get 'e'<'r'
So return "wertf"
Example 2:
Input：["z","x"]
Output："zx"
Explanation：
from "z" and "x"，we can get 'z' < 'x'
So return "zx"
import heapq
class Solution:
def alien_order(self, words: List[str]) -> str:
graph = {}
for w in words:
for c in w:
graph[c] = []
indegrees = collections.Counter()
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
w1l, w2l = len(w1), len(w2)
if w1l > w2l and w1.startswith(w2):
return ''
for j in range(min(w1l, w2l)):
c1, c2 = w1[j], w2[j]
if c1 != c2:
graph[c1].append(c2)
indegrees[c2] += 1
break
hq = [c for c in graph if indegrees[c] == 0]
import heapq
heapq.heapify(hq)
ans = ''
while hq:
c = heapq.heappop(hq)
ans += c
for neighbor in graph[c]:
indegrees[neighbor] -= 1
if indegrees[neighbor] == 0:
heapq.heappush(hq, neighbor)
return ans if len(ans) == len(graph) else ''Blind 75
DFS 二叉树深度优先搜索
257. Binary Tree Paths (Easy)
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
def dfs(root):
if not root:
return
cur.append(str(root.val))
if not root.left and not root.right:
ans.append("->".join(cur))
dfs(root.left)
dfs(root.right)
del cur[-1]
ans = []
cur = []
dfs(root)
return ans8刷：注意：1.剪枝，因为cur是一个reference，递归过程中cur会变长，当前层完成返回上一级函数调用时需要将当前层加上的多余的枝减去 2.ans.append()后不要return，不然无法剪枝
113. Path Sum II (Medium)
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
def dfs(root):
global sum
if not root:
return
cur.append(root.val)
if not root.left and not root.right and sum(cur) == target:
ans.append(cur[:])
dfs(root.left)
dfs(root.right)
del cur[-1]
target = sum
ans, cur = [], []
dfs(root)
return ans9刷：高频，面经：Quora, 大疆。注意：ans.append()后面不要return，否则会丢失剪枝。TODO 用遍历再刷
437. Path Sum III (Medium)
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Constraints:
The number of nodes in the tree is in the range [0, 1000].
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000
O(n^2)
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def dfs(root, cur):
nonlocal ans
if not root:
return
cur += root.val
if cur == targetSum:
ans += 1
dfs(root.left, cur)
dfs(root.right, cur)
def helper(root):
if not root:
return
dfs(root, 0)
helper(root.left)
helper(root.right)
ans = 0
helper(root)
return ansDFS + Memo：
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
def dfs(root, cur):
nonlocal ans
if not root:
return
cur += root.val
ans += memo.get(cur - targetSum, 0)
memo[cur] = memo.get(cur, 0) + 1
dfs(root.left, cur)
dfs(root.right, cur)
memo[cur] -= 1
ans = 0
memo = {0 : 1}
dfs(root, 0)
return ans7刷：面经：Quora。初始化memo为{0 : 1}的目的是当cur == sum的时候memo需要返回1因为这是一个符合条件的路径。 leetcode讨论区有详细的讨论
DFS 基于组合的深度优先搜索
78. Subsets (Medium)
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution:
def subsets(self, nums):
def dfs(idx):
ans.append(cur[:])
for i in range(idx, len(nums)):
cur.append(nums[i])
dfs(i + 1)
del cur[-1]
cur, ans = [], []
dfs(0)
return ans7刷：高频。O(2^n)
39. Combination Sum (Medium)
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
class Solution:
def combinationSum(self, candidates, target):
nums = sorted(candidates)
def dfs(idx):
if sum(cur) == target:
ans.append(cur[:])
return
for i in range(idx, len(nums)):
if nums[i] + sum(cur) <= target:
cur.append(nums[i])
dfs(i)
del cur[-1]
ans = []
cur = []
dfs(0)
return ans7刷：高频, 面经, Quora, Amazon。需要排序的原因是为了避免结果里[2,3,2], [3,2,2]这类情况的发生，结果里只能取当前或比当前大的数。时间复杂度为O(n^k)，n是candidates的数量，k是target / min(candidates)或者用target来近似（假设min是1的话），这个上限比网上一些O(n!)的说法更低
40. Combination Sum II (Medium)
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(idx):
nonlocal target
if sum(cur) == target:
ans.append(cur[:])
return
for i in range(idx, len(nums)):
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
if sum(cur) + nums[i] <= target:
used[i] = True
cur.append(nums[i])
dfs(i + 1)
del cur[-1]
used[i] = False
nums = sorted(candidates)
cur, ans = [], []
used = [False] * len(nums)
dfs(0)
return ans写法2：
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]::
def dfs(idx):
nonlocal target
if sum(cur) == target:
ans.append(cur[:])
return
for i in range(idx, len(nums)):
if i > idx and nums[i] == nums[i - 1]:
continue
if sum(cur) + nums[i] <= target:
cur.append(nums[i])
dfs(i + 1)
del cur[-1]
nums = sorted(candidates)
cur, ans = [], []
dfs(0)
return ans8刷：高频, 面经, amazon。o(2^n) 注意：...if i > idx and nums[i] == nums[i - 1]: continue...
216. combination sum iii (medium)
find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
note:
all numbers will be positive integers.
the solution set must not contain duplicate combinations.
example 1:
input: k = 3, n = 7
output: [[1,2,4]]
example 2:
input: k = 3, n = 9
output: [[1,2,6], [1,3,5], [2,3,4]]
class solution:
def combinationsum3(self, k, n):
def dfs(i):
if len(cur) == k and sum(cur) == n:
ans.append(cur[:])
return
for j in range(i, 10):
if len(cur) < k and sum(cur) < n:
cur.append(j)
dfs(j + 1)
del cur[-1]
ans, cur = [], []
dfs(1)
return ans6刷：面经
77. combinations (medium)
given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
example:
input: n = 4, k = 2
output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class solution:
def combine(self, n: int, k: int) -> list[list[int]]:
def dfs(idx):
if len(cur) == k:
ans.append(cur[:])
return
for i in range(idx, n + 1):
cur.append(i)
dfs(i + 1)
del cur[-1]
ans, cur = [], []
dfs(1)
return ans4刷：面经：amazon
131. palindrome partitioning (medium)
given a string s, partition s such that every substring of the partition is a palindrome.
return all possible palindrome partitioning of s.
example:
input: "aab"
output:
[
["aa","b"],
["a","a","b"]
]
class solution:
def partition(self, s: str) -> list[list[str]]:
ans = []
cur = []
def dfs(idx):
if idx == len(s):
ans.append(cur[:])
return
for i in range(idx + 1, len(s) + 1):
w = s[idx : i]
if w == w[::-1]:
cur.append(w)
dfs(i)
del cur[-1]
ans, cur = [], []
dfs(0)
return ans6刷：高频，o(n*(2^n))
93. restore ip addresses (medium)
given a string containing only digits, restore it by returning all possible valid ip address combinations.
example:
input: "25525511135"
output: ["255.255.11.135", "255.255.111.35"]
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def dfs(idx):
if len(cur) == 4 and idx == n:
ans.append(".".join(cur))
return
for i in range(1, 4):
if idx + i <= n:
num = s[idx: idx + i]
if int(num) < 256 and str(int(num)) == num:
cur.append(num)
dfs(idx + i)
del cur[-1]
n = len(s)
cur, ans = [], []
dfs(0)
return ans11刷：高频。时间复杂度是一件有趣的事情，正常情况下分割字符串是o(2^n)复杂度，但是ip地址是有限的，因此这个题有个常数的时间复杂度上限
linc 680. split string (easy)
give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. output all possible results.
example
given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]
class solution:
def splitstring(self, s):
if len(s) == 0:
return [[]]
def dfs(idx):
if idx == len(s):
ans.append(cur[:])
return
for i in range(1, 3):
if idx + i <= len(s):
cur.append(s[idx:idx + i])
dfs(idx + i)
del cur[-1]
ans, cur = [], []
dfs(0)
return ans5刷
90. subsets ii (medium)
given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
note: the solution set must not contain duplicate subsets.
example:
input: [1,2,2]
output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
无额外空间：
class solution:
def subsetswithdup(self, nums: list[int]) -> list[list[int]]:
def dfs(idx):
ans.append(cur[:])
for i in range(idx, len(nums)):
if i > idx and nums[i] == nums[i - 1]:
continue
cur.append(nums[i])
dfs(i + 1)
del cur[-1]
nums.sort()
ans, cur = [], []
dfs(0)
return ans有额外空间：
class solution:
def subsetswithdup(self, nums: list[int]) -> list[list[int]]:
def dfs(idx):
ans.append(cur[:])
for i in range(idx, len(nums)):
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
cur.append(nums[i])
used[i] = true
dfs(i + 1)
used[i] = false
del cur[-1]
nums.sort()
ans, cur = [], []
used = [false for _ in range(len(nums))]
dfs(0)
return ans8刷：高频，无额外空间的解法需要if i > idx and ...是因为要防止第一次就跳过重复的数字。在47题：permutations ii中因为全排列没有idx这个参数，需要用到用额外空间的写法去重
140. Word Break II (Hard)
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
Example 2:
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
TLE:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def dfs(idx):
if idx == n:
ans.append(' '.join(cur))
return
for i in range(idx + 1, n + 1):
w = s[idx: i]
if w in wordDict:
cur.append(w)
dfs(i)
del cur[-1]
n = len(s)
ans, cur = [], []
dfs(0)
return ansAC: dfs + memo
写法1：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def dfs(idx):
if idx in memo:
return memo[idx]
res = []
for w in wordDict:
if s[idx:].startswith(w):
if w == s[idx:]:
res.append(w)
else:
restW = dfs(idx + len(w))
for item in restW:
res.append(w + ' ' + item)
memo[idx] = res
return res
memo = {}
return dfs(0)写法2：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def dfs(s):
if s in memo:
return memo[s]
res = []
for w in wordDict:
if s.startswith(w):
if w == s:
res.append(w)
else:
restW = dfs(s[len(w):])
for item in restW:
res.append(w + ' ' + item)
memo[s] = res
return res
memo = {}
return dfs(s)6刷：面经：Amazon。九章。TODO 时间空间复杂度
698. Partition to K Equal Sum Subsets (Medium)
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Example 2:
Input: nums = [1,2,3,4], k = 3
Output: false
Constraints:
1 <= k <= nums.length <= 16
1 <= nums[i] <= 104
The frequency of each element is in the range [1, 4].
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
def dfs(k, cur = 0, idx = 0):
nonlocal ans
if k == 1:
ans = True
return
if cur == target:
dfs(k - 1)
for i in range(idx, n):
if not used[i] and cur + nums[i] <= target:
used[i] = True
dfs(k, cur + nums[i], i + 1)
used[i] = False
s = sum(nums)
if s % k != 0:
return False
target = s // k
n = len(nums)
nums.sort(reverse = True)
used = [False] * n
ans = False
dfs(k)
return ans写法2：
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
def dfs(idx):
nonlocal ans
if idx == n:
if all(v == target for v in ka):
ans = True
return
for i in range(k):
if ka[i] + nums[idx] <= target:
ka[i] += nums[idx]
dfs(idx + 1)
ka[i] -= nums[idx]
s = sum(nums)
if s % k != 0:
return False
target = s // k
ka = [0] * k
n = len(nums)
nums.sort(reverse = True)
ans = False
dfs(0)
return ans高频
5. Longest Palindromic Substring (Medium)
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
dfs, expand around center:
class Solution:
def longestPalindrome(self, s: str) -> str:
def helper(l, r):
nonlocal ans
if 0 <= l and r < n and s[l] == s[r]:
if r - l + 1 > len(ans):
ans = s[l:r + 1]
helper(l - 1, r + 1)
ans = ''
n = len(s)
for i in range(n):
helper(i, i)
helper(i, i + 1)
return ansdp：
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = ''
for l in range(n - 1, -1 , -1):
for r in range(l, n):
if s[l] == s[r] and (r - l <= 2 or dp[l + 1][r - 1]):
dp[l][r] = True
if r - l + 1 > len(ans):
ans = s[l:r + 1]
return ansBlind 75
647. Palindromic Substrings (Medium)
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Constraints:
1 <= s.length <= 1000
s consists of lowercase English letters.
写法4：
class Solution:
def countSubstrings(self, s: str) -> int:
def helper(l, r):
nonlocal ans
while 0 <= l and r <= n - 1 and s[l] == s[r]:
ans += 1
l -= 1
r += 1
n = len(s)
ans = 0
for i in range(n):
helper(i, i)
helper(i, i + 1)
return ans写法3：
class Solution:
def countSubstrings(self, s: str) -> int:
def helper(l, r):
nonlocal ans
if 0 <= l and r < n and s[l] == s[r]:
ans += 1
helper(l - 1, r + 1)
ans = 0
n = len(s)
for i in range(n):
helper(i, i)
helper(i, i + 1)
return ans写法2：
class Solution:
def countSubstrings(self, s: str) -> int:
def helper(idx):
nonlocal ans
for e in range(idx + 1, n + 1):
if s[idx:e] == s[idx:e][::-1]:
ans += 1
n = len(s)
ans = 0
for i in range(n):
helper(i)
return ans写法1：
class Solution:
def countSubstrings(self, s: str) -> int:
def helper(idx):
nonlocal ans
for e in range(idx + 1, n + 1):
if s[idx:e] == s[idx:e][::-1]:
ans += 1
if idx < n - 1:
helper(idx + 1)
n = len(s)
ans = 0
helper(0)
return ansblind 75
DFS 基于排列的深度优先搜索
46. Permutations (Medium)
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
写法1：
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs():
if len(cur) == len(nums):
ans.append(cur[:])
return
for n in nums:
if c[n] > 0:
cur.append(n)
c[n] -= 1
dfs()
del cur[-1]
c[n] += 1
c = Counter(nums)
cur, ans = [], []
dfs()
return ans写法2：
class Solution:
def permute(self, nums):
def dfs():
if len(cur) == n:
ans.append(cur[:])
return
for i in range(n):
if not used[i]:
used[i] = True
cur.append(nums[i])
dfs()
del cur[-1]
used[i] = False
cur, ans = [], []
n = len(nums)
used = [False] * n
dfs()
return ans11刷：高频, used = [False] * len(nums); def dfs(). subset从idx开始往后扫，全排每一位都有可能放任意数字，因此要从第一位往后扫。这样就需要一个used的变量来记住哪一位已经被用过了
47. Permutations II (Medium)
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
写法1：
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def helper():
if len(cur) == len(nums):
ans.append(cur[:])
return
for n in counter:
if counter[n] > 0:
cur.append(n)
counter[n] -= 1
helper()
del cur[-1]
counter[n] += 1
cur, ans = [], []
counter = Counter(nums)
helper()
return ans写法2:
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def helper():
if len(cur) == n:
ans.append(cur[:])
return
for i in range(n):
if i and nums[i] == nums[i - 1] and used[i - 1]:
continue
if not used[i]:
cur.append(nums[i])
used[i] = True
helper()
del cur[-1]
used[i] = False
cur, ans = [], []
n = len(nums)
used = [False] * n
nums.sort()
helper()
return ans14刷：高频，空间复杂度O(n)。时间复杂度：O(n*n!), 因为需要n步产生一个排列，总共有n！个可能的排列
22. Generate Parentheses (Medium)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(l, r):
if l == r == n:
ans.append(''.join(cur))
return
if l < n:
cur.append('(')
dfs(l + 1, r)
del cur[-1]
if r < n and l > r:
cur.append(')')
dfs(l, r + 1)
del cur[-1]
ans, cur = [], []
dfs(0, 0)
return ans9刷：高频。时间复杂度分析涉及到nth catalan number的时间复杂度，超出面试范畴，如果是产生所有可能的括号时间复杂度是O(2^2n) != O(2^n)
51. N-Queens (Hard)
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
写法1：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def dfs():
nonlocal cur, ans
if len(cur) == n:
ans.append(cur[:])
return
for nC in range(n):
if nC not in cur and len(cur) + nC not in [r + c for r, c in enumerate(cur)] and len(cur) - nC not in [r - c for r, c in enumerate(cur)]:
cur.append(nC)
dfs()
del cur[-1]
cur, ans = [], []
dfs()
return [['.' * i + 'Q' + '.' * (n - i - 1) for i in b] for b in ans]写法2：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def dfs():
if len(cur) == n:
ans.append(["." * i + "Q" + "." * (n - i - 1) for i in cur])
return
for nC in range(n):
if nC not in cur and legal(nC):
cur.append(nC)
dfs()
del cur[-1]
def legal(nC):
nR = len(cur)
for r, c in enumerate(cur):
if nR + nC == r + c or nR - nC == r - c:
return False
return True
cur, ans = [], []
dfs()
return ans6刷：高频。检查下一行的某列的合法性：举个栗子就能看出来，检查列就看此列是否已在cur中（皇后已在此列），检查/方向的对角线是坐标相加，检查\方向的对角线是坐标相减，行递增无需检查。时间：O(n^3)， 空间：O(n)。因为c (count) 是row，v（value）是column, 正常 for c, v in enuerate() 就写成 for r, c in enumerate()
DFS 基于图的深度优先搜索
17. Letter Combinations of a Phone Number (Medium)
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
递归：
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
def dfs(idx):
if len(cur) == len(digits):
ans.append("".join(cur))
return
for c in kB[digits[idx]]:
cur.append(c)
dfs(idx + 1)
del cur[-1]
cur, ans = [], []
kB = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
dfs(0)
return ans遍历：
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
kB = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
ans = ['']
for i in range(len(digits)):
ans = [prev + c for prev in ans for c in kB[digits[i]]]
return ans8刷：高频
79. Word Search (Medium)
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def helper(r, c, i):
nonlocal ans
if i < k:
if i == k - 1:
ans = True
return
ch = board[r][c]
board[r][c] = ''
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + rd, c + cd
if 0 <= nr <= m - 1 and 0 <= nc <= n - 1 and board[nr][nc] == word[i + 1]:
helper(nr, nc, i + 1)
board[r][c] = ch
m, n, k = len(board), len(board[0]), len(word)
ans = False
for r in range(m):
for c in range(n):
if not ans and board[r][c] == word[0]:
helper(r, c, 0)
return ansBlind 75; 高频
212. Word Search II (Hard)
Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = {}
for w in words:
p = root
for c in w:
if c not in p:
p[c] = {}
p = p[c]
p['/'] = w
def helper(r, c, root):
char = board[r][c]
if char in root:
root = root[char]
if '/' in root:
ans.append(root['/'])
del root['/']
board[r][c] = ''
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + rd, c + cd
if 0 <= nr < m and 0 <= nc < n and board[nr][nc]:
helper(nr, nc, root)
board[r][c] = char
m, n = len(board), len(board[0])
ans = []
for r in range(m):
for c in range(n):
helper(r, c, root)
return ansblind 75
490. The Maze (Medium) 带锁
Lintcode 787. The Maze
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position, the destination and the maze, determine whether the ball could stop at the destination.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
Example 1
Input 1: a maze represented by a 2D array
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Example 2
Input 1: a maze represented by a 2D array
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)
Output: false
Explanation: There is no way for the ball to stop at the destination.
Note:
1.There is only one ball and one destination in the maze.
2.Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
4.The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
class Solution(object):
"""
@param maze: the maze
@param start: the start
@param destination: the destination
@return: whether the ball could stop at the destination
"""
def hasPath(self, maze, start, destination):
def dfs(r, c):
nonlocal ans
if [r, c] == destination:
ans = True
return
if not ans:
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nR, nC = r, c
while 0 <= nR + rd <= len(maze) - 1 and 0 <= nC + cd <= len(maze[0]) - 1 and maze[nR + rd][nC + cd] != 1:
nR += rd
nC += cd
if maze[nR][nC] != 2:
maze[nR][nC] = 2
dfs(nR, nC)
ans = False
dfs(start[0], start[1])
return ans7刷：面经：Amazon。TODO: BFS。确保不往回滚的关键是把滚到的终点标记为2，再往各可能方向滚好以后递归之前查看此点是否来过（为2)。for循环内要用nR, nC = r, c保存当前滚到的位置，才能四个方向都滚到
417. Pacific Atlantic Water Flow (Medium)
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
The order of returned grid coordinates does not matter.
Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
dfs:
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
reach_p = [[False] * n for _ in range(m)]
reach_a = [[False] * n for _ in range(m)]
def helper(r, c, reach):
reach[r][c] = True
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + rd, c + cd
if 0 <= nr < m and 0 <= nc < n and not reach[nr][nc] and \
heights[r][c] <= heights[nr][nc]:
helper(nr, nc, reach)
for c in range(n):
helper(0, c, reach_p)
helper(m - 1, c, reach_a)
for r in range(m):
helper(r, 0, reach_p)
helper(r, n - 1, reach_a)
return [[r, c] for r in range(m) for c in range(n) if reach_p[r][c] and reach_a[r][c]]bfs:
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
reach_p = [[False] * n for _ in range(m)]
reach_a = [[False] * n for _ in range(m)]
def helper(q, reach):
while q:
r, c = q.popleft()
reach[r][c] = True
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + rd, c + cd
if 0 <= nr < m and 0 <= nc < n and not reach[nr][nc] and \
heights[nr][nc] >= heights[r][c]:
q.append((nr, nc))
pq, aq = deque(), deque()
for r in range(m):
pq.append((r, 0))
aq.append((r, n - 1))
for c in range(n):
pq.append((0, c))
aq.append((m - 1, c))
helper(pq, reach_p)
helper(aq, reach_a)
return [[r, c] for r in range(m) for c in range(n) if reach_p[r][c] == reach_a[r][c] == True]Blind 75; 面经：Cruise。从两个海接触的四条边上的点为起点往内陆灌，返回两个海都能灌到的点坐标
399. Evaluate Division (Medium)
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
DFS:
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = collections.defaultdict(list)
for [s, e], w in zip(equations, values):
graph[s].append((e, w))
graph[e].append((s, 1 / w))
def dfs(s, e, cur):
nonlocal res
if s == e:
res = cur
return
seen.add(s)
for (n_s, w) in graph[s]:
if n_s not in seen:
dfs(n_s, e, cur * w)
ans = []
for [s, e] in queries:
seen = set()
res = -1.0
if s in graph:
dfs(s, e, 1.0)
ans.append(res)
return ansBFS:
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = collections.defaultdict(list)
for [s, e], w in zip(equations, values):
graph[s].append((e, w))
graph[e].append((s, 1 / w))
ans = []
for [s, e] in queries:
res = -1.0
if s in graph:
q = deque([(s, 1.0)])
seen = set()
while q:
c_s, cur = q.popleft()
if c_s == e:
res = cur
break
seen.add(c_s)
for n_s, w in graph[c_s]:
if n_s not in seen:
q.append((n_s, w * cur))
ans.append(res)
return ans9刷：面经：头条。Currency Calculator一种题，先build graph，再用DFS, BFS寻最短路径的乘积
332. Reconstruct Itinerary (Medium)
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 1:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:
Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
But it is larger in lexical order.
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(deque)
for [s, e] in sorted(tickets):
graph[s].append(e)
def dfs(s):
while graph[s]:
e = graph[s].popleft()
dfs(e)
ans.append(s)
ans = []
dfs("JFK")
return ans[::-1]2刷：高频
547. Number of Provinces (Medium)
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Constraints:
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i):
for j, conn in enumerate(isConnected[i]):
if conn and j not in seen:
seen.add(j)
dfs(j)
seen = set()
ans = 0
for i in range(len(isConnected)):
if i not in seen:
seen.add(i)
dfs(i)
ans += 1
return ans高频
211. Design Add and Search Words Data Structure (Medium)
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
Constraints:
1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 104 calls will be made to addWord and search.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word: str) -> None:
root = self.root
for c in word:
if c not in root:
root[c] = {}
root = root[c]
root['/'] = ''
def search(self, word: str) -> bool:
def helper(root, i):
if i == len(word):
return '/' in root
c = word[i]
if c == '.':
return any(helper(root[child], i + 1) for child in root if isinstance(root[child], dict))
elif c in root:
return helper(root[c], i + 1)
else:
return False
return helper(self.root, 0)
写法2：
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word: str) -> None:
root = self.root
for c in word:
if c not in root:
root[c] = {}
root = root[c]
root['/'] = ''
def search(self, word: str) -> bool:
def helper(root, i):
nonlocal ans
if i == n and '/' in root:
ans = True
return
if i < n:
c = word[i]
if c in root:
helper(root[c], i + 1)
if c == '.':
for child in root.values():
if isinstance(child, dict):
helper(child, i + 1)
ans = False
n = len(word)
helper(self.root, 0)
return ansBlind 75
LinC 3651 · Number of Connected Components in an Undirected Graph (Medium)
In this problem, there is an undirected graph with n nodes. There is also an edges array. Where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.
You need to return the number of connected components in that graph.
Example 1
Input:
3
[[0,1], [0,2]]
Output:
1
Example 2
Input:
6
[[0,1], [1,2], [2, 3], [4, 5]]
Output:
2
class Solution:
"""
@param n: the number of vertices
@param edges: the edges of undirected graph
@return: the number of connected components
"""
def count_components(self, n: int, edges: List[List[int]]) -> int:
graph = collections.defaultdict(list)
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
seen = set()
def helper(node):
if node not in seen:
seen.add(node)
for neighbor in graph[node]:
helper(neighbor)
ans = 0
for i in range(n):
if i not in seen:
ans += 1
helper(i)
return ansBlind 75
todo union find 写法
200. Number of Islands (Medium)
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
DFS
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def helper(r, c):
grid[r][c] = '0'
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + rd, c + cd
if 0 <= nr < m and 0 <= nc <n and grid[nr][nc] == '1':
helper(nr, nc)
m, n = len(grid), len(grid[0])
ans = 0
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
ans += 1
helper(r, c)
return ansBFS
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ans = 0
m, n = len(grid), len(grid[0])
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
ans += 1
grid[r][c] = 0
q = deque([(r, c)])
while q:
cr, cc = q.popleft()
for rd, cd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = cr + rd, cc + cd
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
grid[nr][nc] = '0'
q.append((nr, nc))
return ansBlind 75; 面经：Amazon
数据结构
Array 数组
LinC 6. Merge Two Sorted Arrays (Easy)
Merge two given sorted integer array A and B into a new sorted integer array.
Example
A=[1,2,3,4]
B=[2,4,5,6]
return [1,2,2,3,4,4,5,6]
Challenge
How can you optimize your algorithm if one array is very large and the other is very small?
思路：热身题，直接做
class Solution:
"""
@param A: sorted integer array A
@param B: sorted integer array B
@return: A new sorted integer array
"""
def mergeSortedArray(self, A, B):
# write your code here
ans = []
indexA = 0
indexB = 0
indexC = 0
while indexC < len(A) + len(B):
if indexA == len(A) or indexB == len(B):
if indexA == len(A):
ans.append(B[indexB])
indexB += 1
else:
ans.append(A[indexA])
indexA += 1
else:
if A[indexA] < B[indexB]:
ans.append(A[indexA])
indexA += 1
else:
ans.append(B[indexB])
indexB += 1
indexC += 1
return ans总结：非常值得刷的一道热身题， 需要考虑两个 array 越界的问题。看了下答案用三个 while 循环也可以。
88. Merge Sorted Array (Easy)
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
m -= 1
n -= 1
p = len(nums1) - 1
while m >= 0 and n >= 0:
if nums1[m] < nums2[n]:
nums1[p] = nums2[n]
n -= 1
else:
nums1[p] = nums1[m]
m -= 1
p -= 1
if n >= 0:
nums1[:p + 1] = nums2[:n + 1]2刷，高频
73. Set Matrix Zeroes (Medium)
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
O(m+n)空间
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
z_r, z_c = [1] * m, [1] * n
for r in range(m):
for c in range(n):
if matrix[r][c] == 0:
z_r[r] = 0
z_c[c] = 0
for r in range(m):
for c in range(n):
if z_r[r] == 0 or z_c[c] == 0:
matrix[r][c] = 0O(1)空间：
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
top_z, left_z = 0 in matrix[0], 0 in list(zip(*matrix))[0]
for r in range(1, m):
for c in range(1, n):
if matrix[r][c] == 0:
matrix[r][0] = 0
matrix[0][c] = 0
for r in range(1, m):
for c in range(1, n):
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
if top_z:
for c in range(n):
matrix[0][c] = 0
if left_z:
for r in range(m):
matrix[r][0] = 0Blind 75
LinC 839. Merge Two Sorted Interval Lists (Easy)
Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.
The intervals in the given list do not overlap.
The intervals in different lists may overlap.
Example
Given list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)], return [(1,4),(5,6)].
思路：思路跟上题 merge interval一样，可以不做
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
@param list1: one of the given list
@param list2: another list
@return: the new sorted list of interval
"""
def mergeTwoInterval(self, list1, list2):
# write your code here
if not list1:
return list2
if not list2:
return list1
list3 = list1 + list2
list3.sort(key=lambda x: x.start)
ans = [list3[0]]
for i in range(1, len(list3)):
if list3[i].start <= ans[-1].end:
ans[-1].end = max(list3[i].end, ans[-1].end)
else:
ans.append(list3[i])
return ans二刷：删掉一刷代码，统一思路
228. Summary Ranges (Medium)
Given a sorted integer array without duplicates, return the summary of its ranges.
Example 1:
Input: [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.
Example 2:
Input: [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.
# 先写 O(n) 的再优化
class Solution:
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
if not nums:
return []
ans, start = [], 0
def addToRes(l, r):
if l == r:
ans.append(str(nums[l]))
else:
ans.append(f"{str(nums[l])}->{str(nums[r])}")
for i in range(len(nums) - 1):
if nums[i] != nums[i + 1] - 1:
addToRes(start, i)
start = i + 1
addToRes(start, len(nums) - 1)
return ans二刷：删掉了一刷的思路，代码和总结。 ..start = 0...def addToRes(l, r):...start = i + 1...
67. Add Binary (Easy)
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
高频
class Solution:
def addBinary(self, a: str, b: str) -> str:
m = len(a)
n = len(b)
l = max(m, n)
i = 1
carry = 0
ans = ""
while i <= l:
if i <= m and i <= n:
val = int(a[-i]) + int(b[-i]) + carry
elif i <= m:
val = int(a[-i]) + carry
elif i <= n:
val = int(b[-i]) + carry
if val > 1:
carry = 1
else:
carry = 0
ans = str(val % 2) + ans
i += 1
if carry == 1:
ans = "1" + ans
return ans总结：...i = 1...while i <= l:...if val > 1: carry = 1; else: carry = 0; ans = str(val % 2) + ans; i += 1...
12. Integer to Roman (Medium)
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: 3
Output: "III"
Example 2:
Input: 4
Output: "IV"
Example 3:
Input: 9
Output: "IX"
Example 4:
Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 5:
Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
高频
class Solution:
def intToRoman(self, num: int) -> str:
n = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
l = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
ans = ""
for i, v in enumerate(n):
if num == 0:
return ans
t = num // v
ans += l[i] * t
num %= v
return ans总结：有了n和l俩数组就是easy了
43. Multiply Strings (Medium)
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
class Solution:
def multiply(self, num1: str, num2: str) -> str:
res = [0 for _ in range(len(num1) + len(num2))]
num1 = num1[::-1]
num2 = num2[::-1]
for i in range(len(num1)):
for j in range(len(num2)):
res[i + j] += int(num1[i]) * int(num2[j])
for i in range(len(res)):
d = res[i] % 10
c = res[i] // 10
if i < len(res) - 1:
res[i + 1] += c
res[i] = d
res.reverse()
while res[0] == 0 and len(res) > 1:
del res[0]
return "".join(str(i) for i in res)高频：...for i in range(len(res)):...res[i] = d...while res[0] == 0 and len(res) > 1:...
128. Longest Consecutive Sequence (Medium)
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
ans = 0
nums = set(nums)
for num in nums:
if num - 1 not in nums:
cur = 0
while num in nums:
cur += 1
num += 1
ans = max(ans, cur)
r