可能有点乱；不过，用这个笔记，我通过了面试 :)
426. Convert Binary Search Tree to Sorted Doubly Linked List
inorder dfs, use self.pre cur var to link
133. Clone Graph
dfs, ref[old]=new
for n in nei, newnei.add(dfs(n))
282. Expression Add Operators
d=num[i:j+1] to try number.
dfs(j+1, path, res, curnum)
863. All Nodes Distance K in Binary Tree
build a graph.
dfs(cur,parent). parent<->cur. dfsleft, dfsright.
bfs
1216. Valid k Palindrome III
dp[i,j]--> max len pan in range.
init all 1.
for len in (2,n+1),
for i, j=i+len-1
if yes, dp[i + 1][j - 1] + 2
no, max(dp[i + 1][j], dp[i][j - 1])
116. Populating Next Right Pointers in Each Node
bfs. but can use prev res instead of q.
721. Accounts Merge
graph: e2e, e2n
dfs(email,path). res=sorted(path)
109. Convert Sorted List to Binary Search Tree
def findmid. slow fast till fast.next or fast=right. return slow.
build(l,r). find mid, make mid node.
l=build(l,m)
r=build(m+1,r)
127. Word Ladder
build graph, bfs
can bibfs to save. start from smaller. track 2 visited sets
126. Word Ladder II
build graph, dfs(cur,path)
329. Longest Increasing Path in a Matrix
dfs memo
139. Word Break
def dfs(start):
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and dfs(end):
memo[start] = True
return True
return dfs(0)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
10. Regular Expression Matching
def backtrack(i, j):
first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
# Handle '*'
if j + 1 < len(p) and p[j + 1] == '*':
# Match zero or more occurrences of p[j]
return (
backtrack(i, j + 2) or #0
(first_match and backtrack(i + 1, j)) #many
)
else:
# Match one character and move forward
return first_match and backtrack(i + 1, j + 1)
691. Stickers to Spell Word
try each helpful word
if sticker[remaining[0]] == 0: pass
use memo[reminaing]=res
983. Minimum Cost For Tickets
dfs memo.
dfs(i+1, res+daypass)
dfs(i+next out of wek, res+wk pass)
take min.
239. Sliding Window Maximum
decreasing q.
rmove left,
process q if meet smalar
add right
1004. Max Consecutive Ones III
extend r, shrink l to valid
76. Minimum Window Substring
add right to window, check.
while valid, shrink left
3. Longest Substring Without Repeating Characters
while invalid, move left
add right, update res
179. Largest Number
nums.sort(key=cmp_to_key(compare))
compare a + b > b + a
31. Next Permutation
next larger.
find a decrease from right.
swap to 1st larger from right
reverse the after
670. Maximum Swap
find last appear.
for each num, find a large num to swap.
1539. Kth Missing Positive Number
bs, missing = arr[mid] - (mid + 1)
163. Missing Ranges
[lower, max(lower,i-1)]
380. Insert Delete GetRandom O(1)
dict and list
remove, find the index using dict, swap to end, pop.
636. Exclusive Time of Functions
stack, pretime.
start, add cur-pre time to stack last. pre=cur
end, cur-pre+1 for stack pop. pre=cur+1
65. Valid Number
int. remove sign, part.isdigit()
decimal. split. left is int, right.isdigit()
E, left is decimal. right is int.
169. Majority Element (appear >n/2 times)
if count == 0:
res = num
if num == res:
count += 1
else:
count -= 1
536. Construct Binary Tree from String
on - and number, make node, add to stack.
on ), cur=pop. try add to stack last l or r.
8. String to Integer (atoi)
space by lstrip,
get sign at s[0]
digit, apply sign
269. Alien Dictionary
make a graph. indegree
for w1 w2, w1j->w2j
q of 0 indegree
quick check: w1.startswith(w2): false
825. friends age
sort age. counter.
count[age_x] * count[age_y]
2914. Minimum Number of Changes to Make Binary String Beautiful
make adjacent pairs the same.
for i in (0,n//2), res += int(s[2*i] != s[2*i+1])
4. Median of Two Sorted Arrays
mid1 = (low + high) // 2 # Calculate mid index for nums1
mid2 = leftnumbers a fixed value - mid1 # Calculate mid index for nums2
compute the smallest right, largest left.
ends when largest left < smallest right
48. Rotate Image
rc=cr, flip diag
row.reverse(), flip vert.
224. Basic Calculator, +-()
curres = 0
ops = 1
stack = [] # Stack to save state before parentheses
n = 0 # Accumulate numbers
+-, finish cur ops and asign ops.
l, save curres ops to stack. reset
r, finish cur ops, pop the preres, add in.
227. Basic Calculator II. +-*/
stack = [] # return the sum of stack
num = 0
sign = '+' # need to use str.
when meet a ops, apply prev ops
+-, append the num to stack
*, times num to last in stack
then log the new ops
138. Copy List with Random Pointer
random: need to check.
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
143. Reorder List
find mid.
reverse the latter
merge.
53. Maximum Subarray
if total < 0:
total = 0
total += n
34. Find First and Last Position of Element in Sorted Array
def findLeft(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
def findRight(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
378. Kth Smallest Element in a Sorted Matrix
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
def countLessEqual(mid):
# Count elements <= mid
count = 0
row, col = n - 1, 0 # Start from bottom-left corner
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1 # All elements in this column up to `row` are <= mid
col += 1
else:
row -= 1 # Move up to reduce value
return count
# Binary search
low, high = matrix[0][0], matrix[n-1][n-1]
while low < high:
mid = (low + high) // 2
if countLessEqual(mid) < k:
low = mid + 1
else:
high = mid
return low
616. Add Bold Tag in String
s.find(word)
3097. Shortest Subarray With OR at Least K II
or can only filp 0->1
expend |=, shink ^=
435. Non-overlappingIntervals
min revmove
sort by end.
if overlap, count+=1 (remove later end)
658. Find K Closest Elements
bs to find x
expend to find k.
796. Rotate String
goal in s+s
723. Candy Crush
Med.
773. Sliding Puzzle
Hard
787. Cheapest Flights Within K Stops
Med.
814. Binary Tree Pruning
Med.
852. Peak Index in a Mountain Array
Med.
907. Sum of Subarray Minimums
Med.
1161. Maximum Level Sum of a Binary Tree
Med.
1382. Balance a Binary Search Tree
Med.
1498. Number of Subsequences That Satisfy the Given Sum Condition
Med.
1845. Seat Reservation Manager
Med.
2090. K Radius Subarray Averages
Med.
2427. Number of Common Factors
