对于难题,先想出来 Brute Force 怎么做啊!在刷题的时候先把 BF 的写出来!
然后看下有哪些可以优化的地方:
- 是不是可以用空间换时间
- 是不是有重复计算的地方?
- 一般求最大最小要不是 DP 就是 Greedy,怎么知道 Greedy 是最优?
思考一下面对不会做的题目,要如何想!
滚动数组降低空间复杂度!
结题总结
- 求极值
- 最小路径:BFS
- 最大或最小:DP
- 最大或最小:Greedy
二分模板
# Author: Huahua
# Returns the smallest m in [l, r),
# s.t. cond(m) == True
# If not found returns r.
def binary_search(l, r, cond)
while l < r:
m = l + (r - l) // 2
if cond(m):
r = m
else
l = m + 1
return l
组合模板
# Author: Huahua
def C(n, m, s, cur):
if len(cur) == m:
print(cur)
return
for i in range(s, n):
cur.append(i + 1)
C(n, m, i + 1, cur)
cur.pop()
n = 5
m = 3
C(n, m, 0, [])
排列模板
# Author: Huahua
def P(n, m, cur, used):
if len(cur) == m:
print(cur)
return
for i in range(n):
if used[i]: continue
used[i] = True
cur.append(i + 1)
P(n, m, cur, used)
cur.pop()
used[i] = False
n = 5
m = 3
P(n, m, [], [False] * n)
BFS模板
# Author: Huahua
# Find the shortest path from |start| to |target| in a unweighted graph G.
# neighbor(x) returns the neighbors of x in G.
q = deque([start])
seen = set([start])
steps = 0
while q:
size = len(q)
for _ in range(size):
n = q.popleft()
if n == target: return steps
for t in neighbor(n):
if t in seen: continue
q.append(t)
seen.add(t)
steps += 1
return -1 # not found
DFS模板
# Author: Huahua
# Check whether there is a path from |start| to |target| in graph G.
# neighbor(x) returns the neighbors of x in G.
seen = set([start])
def dfs(n):
if n == target:
return True
for t in neighbor(n):
if t in seen: continue
seen.add(t)
if dfs(t): return True
seen.remove(t) # back-tracking
return False
return dfs(start)
前缀树模板
# Author: Huahua
class Trie(object):
def __init__(self): self.root = {}
def insert(self, word):
p = self.root
for c in word:
if c not in p: p[c] = {}
p = p[c]
p['#'] = True
def search(self, word):
node = self._find(word)
return node and '#' in node
def startsWith(self, prefix):
return self._find(prefix)
def _find(self, prefix):
p = self.root
for c in prefix:
if c not in p: return None
p = p[c]
return p
并查集模板
# Author: Huahua
class UnionFindSet:
def __init__(self, n):
self.p = [i for i in range(n + 1)]
self.r = [1 for i in range(n + 1)]
def find(self, u):
while u != self.p[u]:
self.p[u] = self.p[self.p[u]]
u = self.p[u]
return u
def union(self, u, v):
pu, pv = self.find(u), self.find(v)
if pu == pv: return False
if self.r[pu] < self.r[pv]:
self.p[pu] = pv
elif self.r[pu] > self.r[pv]:
self.p[pv] = pu
else:
self.p[pv] = pu
self.r[pu] += 1
return True
记忆化递归模板
# Author: Huahua
# dp(state) returns the minimal cost to solve the subproblem |s|.
def dp(s):
# No solution
if unsolvable(s): return float('inf')
# Base case, easy to solve.
if base_case(s): return cost(s)
# Already solved
if s in memo: return memo[s]
best = float('inf')
for t in subproblems(s):
best = min(best, cost(s, t) + dp(t))
memo[s] = best
return best
return dp(start)
LeetCode Done
- 45. Jump Game II
- Greedy Algorithm
- 58. Length of Last Word
- 43. Multiply Strings
- 30. Substring with Concatenation of All Words
- 83. Remove Duplicates from Sorted List
- 9. Palindrome Number
- 24. Swap Nodes in Pairs
- 27. Remove Element
- 16. 3Sum Closest
- 6. ZigZag Conversion
- 312. Burst Balloons
- 406. Queue Reconstruction by Height
- 438. Find All Anagrams in a String
- 647. Palindromic Substrings
- 621. Task Scheduler
- 494. Target Sum
- 560. Subarray Sum Equals K
- 617. Merge Two Binary Trees
- 739. Daily Temperatures
- 338. Counting Bits
- 31. Next Permutation
- 226. Invert Binary Tree
- 309. Best Time to Buy and Sell Stock with Cooldown
- 221. Maximal Square
- 395. Longest Substring with At Least K Repeating Characters
- 387. First Unique Character in a String
- 371. Sum of Two Integers
- 378. Kth Smallest Element in a Sorted Matrix
- 412. Fizz Buzz
- 344. Reverse String
- 341. Flatten Nested List Iterator
- 328. Odd Even Linked List
- 347. Top K Frequent Elements
- 350. Intersection of Two Arrays II
- 349. Intersection of Two Arrays
- 315. Count of Smaller Numbers After Self
- 324. Wiggle Sort II
- 326. Power of Three
- 295. Find Median from Data Stream
- 283. Move Zeroes
- 236. Lowest Common Ancestor of a Binary Tree
- 224. Basic Calculator
- 268. Missing Number
- 240. Search a 2D Matrix II
- 289. Game of Life
- 208. Implement Trie (Prefix Tree)
- 230. Kth Smallest Element in a BST
- 227. Basic Calculator II
- 218. The Skyline Problem
- 215. Kth Largest Element in an Array
- 217. Contains Duplicate
- 150. Evaluate Reverse Polish Notation
- 172. Factorial Trailing Zeroes
- 206. Reverse Linked List
- 202. Happy Number
- 166. Fraction to Recurring Decimal
- 191. Number of 1 Bits
- 190. Reverse Bits
- 148. Sort List
- 146. LRU Cache
- 128. Longest Consecutive Sequence
- 125. Valid Palindrome
- 171. Excel Sheet Column Number
- 134. Gas Station
- 169. Majority Element
- 42. Trapping Rain Water
- 76. Minimum Window Substring
- 703. Kth Largest Element in a Stream
- 49. Group Anagrams
- 55. Jump Game
- 56. Merge Intervals
- 48. Rotate Image
- 119. Pascal’s Triangle II
- 118. Pascal’s Triangle
- 28. Implement strStr()
- 19. Remove Nth Node From End of List
- 41. First Missing Positive
- 26. Remove Duplicates from Sorted Array
- 8. String to Integer (atoi)
- 14. Longest Common Prefix
- 13. Roman to Integer
- 12. Integer to Roman
- 983. Minimum Cost For Tickets
- 181. Employees Earning More Than Their Managers
- 178. Rank Scores
- 177. Nth Highest Salary
- 176. Second Highest Salary
- 175. Combine Two Tables
- 7. Reverse Integer
- 4. Median of Two Sorted Arrays
- 205. Isomorphic Strings
- 92. Reverse Linked List II
- 149. Max Points on a Line
- 730. Count Different Palindromic Subsequences
- 914. X of a Kind in a Deck of Cards
- 433. Minimum Genetic Mutation
- 501. Find Mode in Binary Search Tree
- 334. Increasing Triplet Subsequence
- 454. 4Sum II
- 66. Plus One
- 18. 4Sum
- 29. Divide Two Integers
- 714. Best Time to Buy and Sell Stock with Transaction Fee
- 495. Teemo Attacking
- 430. Flatten a Multilevel Doubly Linked List
- 869. Reordered Power of 2
- 525. Contiguous Array
- 982. Triples with Bitwise AND Equal To Zero
- 54. Spiral Matrix
- 35. Search Insert Position
- Bit Manipulation
- 389. Find the Difference
- 260. Single Number III
- 958. Check Completeness of a Binary Tree
- 543. Diameter of Binary Tree
- 333. Largest BST Subtree
- 449. Serialize and Deserialize BST
- 523. Continuous Subarray Sum
- 655. Print Binary Tree
- 297. Serialize and Deserialize Binary Tree
- 474. Ones and Zeroes
- 416. Partition Equal Subset Sum
- 926. Flip String to Monotone Increasing
- 1143. Longest Common Subsequence
- 814. Binary Tree Pruning
- 812. Largest Triangle Area
- 36. Valid Sudoku
- 813. Largest Sum of Averages
- 815. Bus Routes
- 222. Count Complete Tree Nodes
- 34. Find First and Last Position of Element in Sorted Array
- 162. Find Peak Element
- 160. Intersection of Two Linked Lists
- 138. Copy List with Random Pointer
- 86. Partition List
- 25. Reverse Nodes in k-Group
- 234. Palindrome Linked List
- 203. Remove Linked List Elements
- 708. Insert into a Cyclic Sorted List
- 239. Sliding Window Maximum
- 232. Implement Queue using Stacks
- 225. Implement Stack using Queues
- 189. Rotate Array
- 572. Subtree of Another Tree
- 796. Rotate String
- 242. Valid Anagram
- 151. Reverse Words in a String
- 164. Maximum Gap
- 1031. Maximum Sum of Two Non-Overlapping Subarrays
- 132. Palindrome Partitioning II
- 131. Palindrome Partitioning
- 152. Maximum Product Subarray
- 123. Best Time to Buy and Sell Stock III
- 122. Best Time to Buy and Sell Stock II
- 95. Unique Binary Search Trees II
- 121. Best Time to Buy and Sell Stock
- 96. Unique Binary Search Trees
- 87. Scramble String
- 93. Restore IP Addresses
- 85. Maximal Rectangle
- 581. Shortest Unsorted Continuous Subarray
- 32. Longest Valid Parentheses
- 126. Word Ladder II
- 89. Gray Code
- 472. Concatenated Words
- 60. Permutation Sequence
- 52. N-Queens II
- 44. Wildcard Matching
- 37. Sudoku Solver
- 77. Combinations
- 503. Next Greater Element II
- 496. Next Greater Element I
- 140. Word Break II
- 139. Word Break
- 213. House Robber II
- 90. Subsets II
- 47. Permutations II
- 20. Valid Parentheses
- 142. Linked List Cycle II
- 141. Linked List Cycle
- 137. Single Number II
- 136. Single Number
- 179. Largest Number
- 38. Count and Say
- 23. Merge k Sorted Lists
- 46. Permutations
- 74. Search a 2D Matrix
- 40. Combination Sum II
- 39. Combination Sum
- 216. Combination Sum III
- 33. Search in Rotated Sorted Array
- 75. Sort Colors
- 15. 3Sum
- 567. Permutation in String
- 443. String Compression
- 706. Design HashMap
- 2. Add Two Numbers
- 11. Container With Most Water
- 473. Matchsticks to Square
- 394. Decode String
- 337. House Robber III
- 329. Longest Increasing Path in a Matrix
- 129. Sum Root to Leaf Numbers
- 124. Binary Tree Maximum Path Sum
- 117. Populating Next Right Pointers in Each Node II
- 116. Populating Next Right Pointers in Each Node
- 114. Flatten Binary Tree to Linked List
- 106. Construct Binary Tree from Inorder and Postorder Traversal
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 刷题代码模板
- 99. Recover Binary Search Tree
- 897. Increasing Order Search Tree
- 872. Leaf-Similar Trees
- 733. Flood Fill
- 110. Balanced Binary Tree
- 437. Path Sum III
- 257. Binary Tree Paths
- 113. Path Sum II
- 112. Path Sum
- 863. All Nodes Distance K in Binary Tree
- 109. Convert Sorted List to Binary Search Tree
- 108. Convert Sorted Array to Binary Search Tree
- 100. Same Tree
- 787. Cheapest Flights Within K Stops
- 73. Set Matrix Zeroes
- 72. Edit Distance
- 70. Climbing Stairs
- 704. Binary Search
- 700. Search in a Binary Search Tree
- 994. Rotting Oranges
- 993. Cousins in Binary Tree
- 785. Is Graph Bipartite?
- 559. Maximum Depth of N-ary Tree
- 429. N-ary Tree Level Order Traversal
- 155. Min Stack
- 752. Open the Lock
- 743. Network Delay Time
- 690. Employee Importance
- 542. 01 Matrix
- 133. Clone Graph
- 513. Find Bottom Left Tree Value
- 513. Find Bottom Left Tree Value
- 301. Remove Invalid Parentheses
- 310. Minimum Height Trees
- 210. Course Schedule II
- 207. Course Schedule
- 200. Number of Islands
- 199. Binary Tree Right Side View
- 130. Surrounded Regions
- 127. Word Ladder
Hard to handle
- [123. Best Time to Buy and Sell Stock III]
- [137. Single Number II]
- [164. Maximum Gap]
- [23. Merge k Sorted Lists]
- [10. Regular Expression Matching]
- [417. Pacific Atlantic Water Flow]
- 1263. Minimum Moves to Move a Box to Their Target Location
- 212. Word Search II
- 5. Longest Palindromic Substring
- 322. Coin Change
- 639. Decode Ways II