classSolution:
deftwoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, value inenumerate(nums):
if target - value in hashmap:
return [index, hashmap[target - value]]
else:
hashmap[value] = index
classSolution:
defisAnagram(self, s: str, t: str) -> bool:
hashmap = [0] * 26for i in s:
hashmap[ord(i) - ord('a')] += 1for i in t:
hashmap[ord(i) - ord('a')] -= 1for i in hashmap:
if i != 0:
returnFalsereturnTrue
指针的移动是有目的的(为了求出最后的答案而移动,不是乱移动),两个 for 循环嵌套也就是双指针,只不过指针的移动是固定的
快慢指针:
快指针一直移动,直到最后一个元素,每次移动代表着根据题意处理接下来的一个元素
慢指针在快指针进行判断且满足题意时移动,每次移动代表着慢指针之前的元素就是要的答案
左右指针:两个指针分别位于首尾,并向中间靠拢的技巧
使用场景:需要用到左右指针的关系,比如:左指针小于右指针,或者需要左右指针之间的距离。
根据题意来决定如何移动左右指针
模板:while left < right
移动零
快慢指针
classSolution:
defmoveZeroes(self, nums: List[int]) -> None:
n = len(nums)
slow = 0
fast = 0while fast < n:
if nums[fast] != 0:
nums[fast], nums[slow] = nums[slow], nums[fast]
slow += 1
fast += 1
盛水最多的容器
左右指针
classSolution:
defmaxArea(self, height: List[int]) -> int:
n = len(height)
left = 0
right = n - 1
maxVol = 0while left < right:
vol = (right - left) * min(height[left], height[right])
maxVol = max(vol, maxVol)
if height[left] < height[right]:
left += 1else:
right -= 1return maxVol
15. 三数之和(三元组不重复)
左右指针
先排序以方便去重和左右指针的方向感,再固定一个数,利用左右指针从两端向中间'夹逼'寻找另外两个数。
用三个数之和来决定左指针动还是右指针动
classSolution:
defthreeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i inrange(len(nums)):
if nums[i] > 0:
return result
if i > 0and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1while left < right:
sum_val = nums[i] + nums[left] + nums[right]
if sum_val < 0:
left += 1elif sum_val > 0:
right -= 1else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1return result
classSolution:
defsearch(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1while left <= right:
mid = (left + right) // 2if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1else:
right = mid - 1return -1
搜索插入的位置
classSolution:
defsearchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1while left <= right:
mid = (left + right) // 2if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1else:
right = mid - 1return left
搜索二维矩阵
classSolution:
defsearchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1while left <= right:
mid = (left + right) // 2
row = mid // n
col = mid % n
if matrix[row][col] == target:
returnTrueelif matrix[row][col] < target:
left = mid + 1else:
right = mid - 1returnFalse
第一个和最后一个位置
classSolution:
defsearchRange(self, nums: List[int], target: int) -> List[int]:
deffindFirst(nums, target):
left, right = 0, len(nums) - 1
first = -1while left <= right:
mid = (left + right) // 2if nums[mid] == target:
first = mid
right = mid - 1elif nums[mid] < target:
left = mid + 1else:
right = mid - 1return first
deffindLast(nums, target):
left, right = 0, len(nums) - 1
last = -1while left <= right:
mid = (left + right) // 2if nums[mid] == target:
last = mid
left = mid + 1elif nums[mid] < target:
left = mid + 1else:
right = mid - 1return last
first = findFirst(nums, target)
last = findLast(nums, target)
if first == -1or last == -1:
return [-1, -1]
return [first, last]
搜索旋转排序数组
classSolution:
defsearch(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1while left <= right:
mid = (left + right) // 2if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1else:
left = mid + 1else:
if nums[mid] < target <= nums[right]:
left = mid + 1else:
right = mid - 1return -1
寻找排序数组中最小值
classSolution:
deffindMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1while left < right:
mid = (left + right) // 2if nums[mid] > nums[right]:
left = mid + 1else:
right = mid
return nums[left]
滑动窗口
原理
本质:用双指针(类似快慢指针)来表示一个可以移动的大小可变区间,调节子序列的起始位置和终止位置
优点:始终处理连续的子串或子数组,避免了重复计算
模板:left = 0(指向左边界),右指针用 for 循环来表示,for 循环内部的左指针根据题意移动。指针移动时增减哈希表里的元素(用哈希表来知道窗口内部是个什么情况)
无重复字符的最长子串
利用'滑动窗口'机制,通过 right 指针向右扩张寻找新字符,一旦撞上重复字符,就移动 left 指针像'挤牙膏'一样将其剔除,从而动态维护窗口内始终是不重复的子串
classSolution:
deflengthOfLongestSubstring(self, s: str) -> int:
left = 0
hashset = set()
maxLength = 0for right inrange(len(s)):
while s[right] in hashset:
hashset.remove(s[left])
left += 1
hashset.add(s[right])
curLength = right - left + 1
maxLength = max(maxLength, curLength)
return maxLength
找字符串中所有异位词
维护一个长度恒等于 p 的'定长滑动窗口',通过 Counter 实时对比窗口内外的字符频率分布,当两者完全匹配时,即锁定了异位词的起始位置。
classSolution:
deffindAnagrams(self, s: str, p: str) -> List[int]:
pHahsMap = Counter(p)
sHashMap = Counter()
n = len(s)
res = []
left = 0for right inrange(n):
sHashMap[s[right]] += 1if right - left + 1 > len(p):
sHashMap[s[left]] -= 1
left += 1if sHashMap == pHahsMap:
res.append(left)
return res
classSolution:
defgetIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
visited = set()
currentA = headA
while currentA:
visited.add(currentA)
currentA = currentA.next
currentB = headB
while currentB:
if currentB in visited:
return currentB
currentB = currentB.nextreturnNone
消除长度差来实现同步。走过你的路,我们终会相遇(数学方法)
classSolution:
defgetIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
ifnot headA ornot headB:
returnNone
pA = headA
pB = headB
while pA != pB:
if pA:
pA = pA.nextelse:
pA = headB
if pB:
pB = pB.nextelse:
pB = headA
return pA
206. 反转链表
解题思路:想清楚怎么连接链表 + 保存中间节点(不然就丢失了后续的指向)
快慢指针法:
classSolution:
defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = None
fast = head
while fast:
temp = fast.next
fast.next = slow
slow = fast
fast = temp
return slow
递归法:根据双指针改来的
classSolution:
defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
returnself.reverse(head, None)
defreverse(self, cur: ListNode, pre: ListNode):
if cur == None:
return pre
temp = cur.next
cur.next = pre
returnself.reverse(temp, cur)
回文链表
classSolution:
defisPalindrome(self, head: Optional[ListNode]) -> bool:
vals = []
current_node = head
while current_node isnotNone:
vals.append(current_node.val)
current_node = current_node.next
left, right = 0, len(vals) - 1while left < right:
if vals[left] != vals[right]:
returnFalse
left += 1
right -= 1returnTrue
141. 环形链表
classSolution:
defhasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
while head:
if head in seen:
returnTrue
seen.add(head)
head = head.nextreturnFalse
classSolution:
defhasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.nextif slow == fast:
returnTruereturnFalse
21. 合并两个有序链表
想清楚链表怎么连接
用一个新链表来保存结果
classSolution:
defmergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(-1)
current = dummy_head
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.nextelse:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 if list1 isnotNoneelse list2
return dummy_head.next
两数之和
classSolution:
defaddTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
carry = 0
dummy_head = ListNode()
current = dummy_head
while l1 or l2 or carry:
val1 = l1.val if l1 else0
val2 = l2.val if l2 else0
sum_val = val1 + val2 + carry
carry = sum_val // 10
current.next = ListNode(sum_val % 10)
current = current.nextif l1:
l1 = l1.nextif l2:
l2 = l2.nextreturn dummy_head.next
19. 删除链表的倒数第 N 个节点
classSolution:
defremoveNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
defgetLength(head: ListNode) -> int:
length = 0while head:
length += 1
head = head.nextreturn length
dummy_head = ListNode(0, head)
cur = dummy_head
length = getLength(head)
for i inrange(0, length - n):
cur = cur.next
cur.next = cur.next.nextreturn dummy_head.next
用双指针找到要删除节点的前一个节点:因为快指针先走了 n + 1 步,然后快指针和慢指针一起走,直到快指针走完全部节点,此时,慢指针就是倒数第 n + 1 个数
classSolution:
defremoveNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_head = ListNode(0, head)
fast, slow = dummy_head, dummy_head
for i inrange(n + 1):
fast = fast.nextwhile fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.nextreturn dummy_head.next
classSolution:
defremoveElement(self, nums: List[int], val: int) -> int:
i, l = 0, len(nums) - 1while i < l:
if nums[i] == val:
for j inrange(i, l):
nums[j] = nums[j + 1]
l -= 1
i -= 1
i += 1return l
最优解:双指针,需要的留在前面,不需要的放在后面
classSolution:
defremoveElement(self, nums: List[int], val: int) -> int:
slow = 0
fast = 0for fast inrange(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1return slow
977. 有序数组的平方和
双指针 - 左右指针,每次可以找到一个最大的值出来
classSolution:
defsortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left = 0
right = n - 1
result = [0] * n
idx = n - 1while left <= right:
if nums[left] * nums[left] < nums[right] * nums[right]:
square = nums[right] * nums[right]
result[idx] = square
right -= 1else:
square = nums[left] * nums[left]
result[idx] = square
left += 1
idx -= 1return result
209. 长度最小的子数组
滑动窗口,如果大于了目标值,窗口前端就缩小
classSolution:
defminSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left = 0
right = 0
cur_sum = 0
res = float('inf')
for right inrange(n):
cur_sum += nums[right]
while cur_sum >= target:
res = min(res, right - left + 1)
cur_sum -= nums[left]
left += 1return res if res != float('inf') else0
59. 螺旋矩阵Ⅱ
模拟行为:根据边界,循环填值
classSolution:
defgenerateMatrix(self, n: int) -> List[List[int]]:
if n <= 0:
return []
matrix = [[0] * n for _ inrange(n)]
top, bottom, left, right = 0, n - 1, 0, n - 1
num = 1while top <= bottom and left <= right:
for i inrange(left, right + 1):
matrix[top][i] = num
num += 1
top += 1for i inrange(top, bottom + 1):
matrix[i][right] = num
num += 1
right -= 1for i inrange(right, left - 1, -1):
matrix[bottom][i] = num
num += 1
bottom -= 1for i inrange(bottom, top - 1, -1):
matrix[i][left] = num
num += 1
left += 1return matrix
区间和
前缀和,ACM 写法(需要自己处理原始的字符流,还要打印结果)
import sys
input = sys.stdin.read
defmain():
data = input().split()
index = 0
n = int(data[index])
index += 1
vec = n * [0]
for i inrange(n):
vec[i] = int(data[index])
index += 1
p = [0] * n
pre_sum = 0for i inrange(n):
pre_sum += vec[i]
p[i] = pre_sum
results = []
while index < len(data):
a = int(data[index])
b = int(data[index + 1])
index += 2if a == 0:
sum_value = p[b]
else:
sum_value = p[b] - p[a - 1]
results.append(sum_value)
for result in results:
print(result)
if __name__ == "__main__":
main()
classSolution:
defdailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack = []
for i inrange(n):
cur = temperatures[i]
while stack and cur > temperatures[stack[-1]]:
index = stack.pop()
wait_days = i - index
answer[index] = wait_days
stack.append(i)
return answer
232. 用栈实现队列
利用两个栈,将入第一个栈的元素放到第二个栈里,第二个栈出来的时候就是先入先出了
classMyQueue:
def__init__(self):
self.stack_in = []
self.stack_out = []
defpush(self, x: int) -> None:
self.stack_in.append(x)
defpop(self) -> int:
for i inrange(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
returnself.stack_out.pop()
defpeek(self) -> int:
for i inrange(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
temp = self.stack_out.pop()
self.stack_out.append(temp)
return temp
defempty(self) -> bool:
returnnotself.stack_out
classSolution:
defremoveDuplicates(self, s: str) -> str:
res = []
for item in s:
if res and res[-1] == item:
res.pop()
else:
res.append(item)
return"".join(res)
classSolution:
defkthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1if k == 0:
return current.val
current = current.right
199. 二叉树的右视图
方法一:
classSolution:
defrightSideView(self, root: Optional[TreeNode]) -> List[int]:
result = []
ifnot root:
return result
queue = deque([root])
while queue:
k = -1
level_size = len(queue)
for _ inrange(level_size):
node = queue.popleft()
k += 1if k == level_size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
方法二:
classSolution:
defrightSideView(self, root: Optional[TreeNode]) -> List[int]:
result = []
ifnot root:
return result
queue = deque([root])
while queue:
level_size = len(queue)
leve_nodes = []
for _ inrange(level_size):
node = queue.popleft()
leve_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(leve_nodes[-1])
return result
层序遍历的变形,将每一层的最后一个值拿出来就是右视图的值
classSolution:
defrightSideView(self, root: Optional[TreeNode]) -> List[int]:
ifnot root:
return []
res = []
queue = deque([root])
while queue:
n = len(queue)
for i inrange(len(queue)):
node = queue.popleft()
if i == n - 1:
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
classSolution:
definorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ifnot root:
return []
res = []
stack = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
classSolution:
deflowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == p or root == q or root == None:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left isnotNoneand right isnotNone:
return root
if left isNoneand right isnotNone:
return right
elif left isnotNoneand right isNone:
return left
else:
returnNone
图论
原理
邻接表:用一个列表来存储每个节点的相邻节点
入度:指向该节点边的数量
深度优先搜索(递归)
广度优先搜索(队列)
拓扑排序:对有向无环图的顶点进行排序,使得对于每个有向边 u→v,顶点 u 都在顶点 v 之前
岛屿数量
classSolution:
defnumIslands(self, grid: List[List[str]]) -> int:
ifnot grid:
return0defdfs(x, y):
if x < 0or x >= len(grid) or y < 0or y >= len(grid[0]) or grid[x][y] == '0':
return
grid[x][y] = "0"
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
island_count = 0for i inrange(len(grid)):
for j inrange(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
island_count += 1return island_count
课程表
classSolution:
defcanFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
int_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
int_degree[course] += 1
queue = deque([i for i inrange(numCourses) if int_degree[i] == 0])
complete_courses = 0while queue:
course = queue.pop()
complete_courses += 1for next_course in graph[course]:
int_degree[next_course] -= 1if int_degree[next_course] == 0:
queue.append(next_course)
return complete_courses == numCourses
classSolution:
defcanJump(self, nums: List[int]) -> bool:
n = len(nums)
if n <= 1:
returnTrue
max_reach = 0for i inrange(n):
if max_reach < i:
returnFalse
max_reach = max(max_reach, i + nums[i])
if max_reach >= n - 1:
returnTrue
跳跃游戏Ⅱ
classSolution:
defjump(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return0
max_reach = 0
jumps = 0
current_end = 0for i inrange(n - 1):
max_reach = max(max_reach, i + nums[i])
if i == current_end:
jumps += 1
current_end = max_reach
return jumps
划分字母区间
classSolution:
defpartitionLabels(self, s: str) -> List[int]:
n = len(s)
last_pos = {}
for idx, ch inenumerate(s):
last_pos[ch] = idx
res = []
start = 0
end = 0for i, ch inenumerate(s):
end = max(end, last_pos[ch])
if i == end:
length = i - start + 1
res.append(length)
start = i + 1return res
回溯法
原理
递归(探索所有可能的解)+ 回溯(找到一个解或确定当前路径不可行时(剪枝的思想))
回溯:撤销递归的基本操作
回溯法模板:
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表);
回溯,撤销处理结果
}
}
路径是递归的参数(选择下一个节点进行操作),选择列表是当前存储的结果
处理节点基本就是选择节点然后加到当前的结果集'选择列表'里,回溯就是将'选择列表'里的节点拿出来
回溯三部曲函数的参数和返回值(返回值一般为 void)确定终止条件(到达了叶子节点)单层搜索的逻辑
为什么回溯法要在递归外面套一个 for 循环?
将搜索过程想象成一棵树(决策树),for 循环代表'横向'遍历,递归代表'纵向'遍历
46.全排列
classSolution:
defpermute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
used = [False] * len(nums)
defbacktrack():
iflen(path) == len(nums):
res.append(path[:])
returnfor i inrange(len(nums)):
if used[i]:
continue
path.append(nums[i])
used[i] = True
backtrack()
path.pop()
used[i] = False
backtrack()
return res
Python 支持闭包,内部函数可以直接访问外部函数作用域里的变量
用 used 数组标记使用过哪些元素
classSolution:
defpermute(self, nums: List[int]) -> List[List[int]]:
res = []
used = [False] * len(nums)
self.backtracking(nums, used, [], res)
return res
defbacktracking(self, nums, used, path, res):
iflen(path) == len(nums):
res.append(path[:])
returnfor i inrange(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
self.backtracking(nums, used, path, res)
used[i] = False
path.pop()
78. 子集
利用 startIndex 保证不重复
classSolution:
defsubsets(self, nums: List[int]) -> List[List[int]]:
res = []
self.backtracking(nums, 0, [], res)
return res
defbacktracking(self, nums, startIndex, path, res):
res.append(path[:])
if startIndex >= len(nums):
returnfor i inrange(startIndex, len(nums)):
path.append(nums[i])
self.backtracking(nums, i + 1, path, res)
path.pop()
90. 子集Ⅱ
去重问题,类似组合总和Ⅱ
classSolution:
defsubsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
used = [False] * len(nums)
nums.sort()
self.backtracking(nums, 0, used, [], res)
return res
defbacktracking(self, nums, startIndex, used, path, res):
res.append(path[:])
if startIndex >= len(nums):
returnfor i inrange(startIndex, len(nums)):
if i > 0and nums[i] == nums[i - 1] and used[i - 1] == False:
continue
path.append(nums[i])
used[i] = Trueself.backtracking(nums, i + 1, used, path, res)
used[i] = False
path.pop()
17. 电话号码的字母组合
选下一个数字对应的字母时,用 index + 1
classSolution:
defletterCombinations(self, digits: str) -> List[str]:
res = []
self.backtracking(digits, 0, [], res)
return res
defbacktracking(self, digits, index, path, res):
phone_map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
}
iflen(digits) == len(path):
res.append(''.join(path))
return
possibleLetters = phone_map[digits[index]]
for i in possibleLetters:
path.append(i)
self.backtracking(digits, index + 1, path, res)
path.pop()
22. 括号生成
classSolution:
defgenerateParenthesis(self, n: int) -> List[str]:
res = []
self.backtracking(n, 0, 0, [], res)
return res
defbacktracking(self, n, left, right, path, res):
if left == n and right == n:
res.append(''.join(path))
returnif left < n:
path.append('(')
self.backtracking(n, left + 1, right, path, res)
path.pop()
if right < left:
path.append(')')
self.backtracking(n, left, right + 1, path, res)
path.pop()
classSolution:
defclimbStairs(self, n: int) -> int:
if n == 1:
return1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2for i inrange(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
杨辉三角形
暴力递归
classSolution:
defgenerate(self, numRows: int) -> List[List[int]]:
defgetValue(row, col):
if col == 0or col == row:
return1return getValue(row - 1, col - 1) + getValue(row - 1, col)
res = []
for row inrange(numRows):
current = []
for col inrange(row + 1):
current.append(getValue(row, col))
res.append(current)
return res
动态规划
classSolution:
defgenerate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return []
dp = [[0] * (numRows) for _ inrange(numRows)]
res = []
for row inrange(numRows):
current = []
for col inrange(row + 1):
if col == 0or row == col:
dp[row][col] = 1else:
dp[row][col] = dp[row - 1][col - 1] + dp[row - 1][col]
current.append(dp[row][col])
res.append(current)
return res
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
res = 0defbacktrack(start, path):
nonlocal res
res = max(res, len(path))
for i inrange(start, n):
ifnot path or nums[i] > path[-1]:
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return res
暴力递归
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
defrecursion(index, previous):
if index == n:
return0
not_take = recursion(index + 1, previous)
take = 0if nums[index] > previous:
take = 1 + recursion(index + 1, nums[index])
returnmax(take, not_take)
return recursion(0, float('-inf'))
动态规划
需要两个状态所以需要 j
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
dp[0] = 1
res = 1for i inrange(1, len(nums)):
for j inrange(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
res = max(dp[i], res)
return res
343. 整数拆分
利用动态规划(DP)从小到大递推,通过遍历每一个可能的拆分点 j,在'直接拆成两个数'与'拆出 j 后对剩余部分取最优解'之间取最大值,从而逐步构建出目标数字 n 的最大乘积
classSolution:
defintegerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 0
dp[2] = 1for i inrange(3, n + 1):
for j inrange(1, i // 2 + 1):
dp[i] = max(j * (i - j), j * dp[i - j], dp[i])
return dp[n]
classSolution:
defsingleNumber(self, nums: List[int]) -> int:
result = 0for i in nums:
result ^= i
return result
多数元素
classSolution:
defmajorityElement(self, nums: List[int]) -> int:
count = 0
candidate = 0for num in nums:
if count == 0:
candidate = num
if num == candidate:
count += 1else:
count -= 1return candidate
颜色分类
classSolution:
defsortColors(self, nums: List[int]) -> None:
low, index, high = 0, 0, len(nums) - 1while index <= high:
if nums[index] == 0:
nums[low], nums[index] = nums[index], nums[low]
low += 1
index += 1elif nums[index] == 1:
index += 1elif nums[index] == 2:
nums[high], nums[index] = nums[index], nums[high]
high -= 1
下一个排列
classSolution:
defnextPermutation(self, nums: List[int]) -> None:
n = len(nums)
if n < 2:
return
i = n - 2while i >= 0and nums[i] >= nums[i + 1]:
i -= 1if i >= 0:
j = n - 1while j >= 0and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, n - 1while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
寻找重复数
classSolution:
deffindDuplicate(self, nums: List[int]) -> int:
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
fast = 0while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow