1.双指针:只有一个输入,从两端开始遍历
def fn(arr):
left = 0
right = len(arr) - 1
ans = 0
while left < right:
#一些根据left和right相关的代码补充
if CONDITION:
left += 1
else:
right -= 1
return ans
对撞指针:
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/
快慢指针:
https://leetcode.cn/problems/linked-list-cycle/description/
2.双指针:有两个输入,两个输入都要遍历完
def fn(arr1, arr2):
i = j = ans = 0
while i < len(arr1) and j < len(arr2):
#根据题意补充代码
if CONDITION:
i += 1
else:
j -= 1
while i < len(arr1):
#根据题意补充代码
i += 1
while j < len(arr2):
#根据题意补充代码
j -= 1
return ans
https://leetcode.cn/problems/merge-sorted-array/
3.滑动窗口
def fn(arr):
left = right = ans = cur = 0
while right < len(arr):
# 根据题意补充代码来将 arr[right] 添加到 cur
# or right += 1 分情况而定
while WINDOW_CONDITION_BROKEN:
# 从 cur 中删除 arr[left]
left += 1
#更新 ans
right += 1
def fn(arr):
left = ans = curr = 0
for right in range(len(arr)):
# 根据题意补充代码来将 arr[right] 添加到 curr
while WINDOW_CONDITION_BROKEN:
# 从 curr 中删除 arr[left]
left += 1
# 更新 ans
return ans
https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/
4.构造前缀和
def fn(arr):
prefix = [arr[0]]
for i in range(1,len(arr)):
prefix.append(prefix[-1] + arr[i])
return prefix
5.高效的字符串构建
# arr是一个字符列表
def fn(arr):
ans = []
for c in arr:
ans.append(c)
return "".join(ans)
6.链表:快慢指针
def fn(head):
# 涉及删除操作,需要将slow前置
slow = ListNode()
slow.next = head
# slow = head 正常情况
fast = head
ans = 0
while fast and fast.next:
#根据题意补充代码
slow = slow.next
fast = fast.next
return ans
7.反转链表
def fn(head):
curr = head
prev = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
想象一个气球从前往后传,每个人原本是向右排队,所有拿过气球的人 都朝向左。
每个队中元素都有相同的操作,当前的下一步先缓存起来,然后把当前的下一步指向前置指针,前置指针后移到当前指针指向元素,当前元素后移 将第一步缓存的当前下一步赋值给当前,完成当前指针的后移。
前置指针指向空,
当前指针指向头,
当前指针不为空
循环体内
创建下一步指针
指向当前后一步
当前转指前指针
前指针移步当前
当前移步后一步
循环体结束
返回前置指针。
https://leetcode.cn/problems/reverse-linked-list/submissions/
8. 找到符合确切条件的子数组数
from collections import defaultdict
def fn(arr, k):
counts = defaultdict(int)
counts[0] = 1
ans = curr = 0
for num in arr:
# 根据题意补充代码来改变 curr
ans += counts[curr - k]
counts[curr] += 1
return ans
- 创建一个哈希映射 counts,用于跟踪累积和出现的次数。
- 初始化 ans 和 curr 为0,其中 ans 用于记录符合条件的子数组数量,curr 用于跟踪当前的累积和。
- 遍历输入数组 arr 中的每个元素,根据题目要求修改 curr 的值。
- 在每次迭代中,计算当前累积和 curr 下,有多少子数组的累积和等于 curr - k,并将这个数量累加到 ans 中。
- 更新 counts 映射,以记录当前累积和 curr 出现的次数。
- 循环结束后,返回 ans,它代表了满足条件的子数组的数量。
https://leetcode.cn/problems/subarray-sum-equals-k/description/
9.单调递增栈
def fn(arr):
stack = []
ans = 0
for num in arr:
# 对于单调递减的情况,只需将 > 翻转到 <
while stack and stakc[-1] > num:
# 根据题意补充代码
stack.pop()
stack.append(num)
return ans
判别是否需要使用单调栈,如果需要找到左边或者右边第一个比当前位置的数大或者小,则可以考虑使用单调栈;单调栈的题目如矩形米面积等等
https://leetcode.cn/problems/daily-temperatures/
10.二叉树:DFS(递归)
def dfs(root):
if not root:
return
ans = 0
# 根据题意补充代码
dfs(root.left)
def(root.right)
return ans
11.二叉树:DFS(迭代)
def dfs(root)
stack = [root]
ans = 0
while stack:
node = stack.pop()
# 根据题意补充代码
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ans
12.二叉树:BFS
from collections import deque
def bfs(root):
queue = deque([root])
ans = 0
while queue:
current_length = len(queue)
# 做一些当前层的操作
for _ in range(current_length):
node = queue.popleft()
# 根据题意补充代码
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return ans
13.图:DFS(递归)
def fn(graph):
def dfs(node):
ans = 0
# 根据题意补充代码
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
ans += dfs(neighbor)
return ans
seen = {START_NODE}
return dfs(START_NODE)
14.图: DFS (迭代)
def fn(graph):
stack = [START_NODE]
seen = {START_NODE}
ans = 0
while stack:
node = stack.pop()
# 根据题意补充代码
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
stack.append(neighbor)
return ans
15.图: BFS
from collections import deque
def fn(graph):
queue = deque([START_NODE])
seen = {START_NODE}
ans = 0
while queue:
node = queue.popleft()
# 根据题意补充代码
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return ans
16.找到堆的前k个元素
import heapq
def fn(arr, k):
heap = []
for num in arr:
# 根据题意补充代码,根据问题的条件来推入堆中
heapq.headpush(heap, (CRITERIA, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for num in heap]
17.二分查找
def fn(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
# 根据题意补充代码
return
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
# left是插入点
return left
18. 二分查找: 重复元素,最左边的插入点
def fn(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] >= target:
right = mid
else:
left = mid + 1
return left
19. 二分查找: 重复元素,最右边的插入点
def fn(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] > target:
right = mid
else:
left = mid + 1
return left
20. 二分查找:贪心问题
寻找最小值:
def fn(arr):
def check(x):
# 这个函数的具体实现取决于问题
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1:
else:
left = mid + 1
return left
寻找最大值:
def fn(arr):
def check(x):
# 这个函数的具体实现取决于问题
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1
return right
21.回溯
「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,当遇到正确的解则将其记录,直到找到解或者尝试了所有可能的选择都无法找到解为止。
- 回溯算法通常采用“深度优先搜索”来遍历解空间。也可以使用缓存池来节省空间
- 之所以称之为回溯算法,是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时,它会撤销上一步的选择,退回到之前的状态,并尝试其他可能的选择。
- 复杂的回溯问题通常包含一个或多个约束条件,约束条件通常可用于“剪枝”。
def backtrack(state: State, choices: list[choice], res: list[state]):
"""回溯算法框架"""
# 判断是否为解
if is_solution(state):
# 记录解
record_solution(state, res)
# 不再继续搜索
return
# 遍历所有选择
for choice in choices:
# 剪枝:判断选择是否合法
if is_valid(state, choice):
# 尝试:做出选择,更新状态
make_choice(state, choice)
backtrack(state, choices, res)
# 回退:撤销选择,恢复到之前的状态
undo_choice(state, choice)
def backtrack(curr, OTHER_ARGUMENTS...):
if (BASE_CASE):
# 修改答案
return
ans = 0
for (ITERATE_OVER_INPUT):
# 修改当前状态
ans += backtrack(curr, OTHER_ARGUMENT...)
# 撤销对当前状态的修改
return ans
22. 动态规划:自顶向下法
def fn(arr):
def dp(STATE):
if BASE_CASE:
return 0
if STARE in memo:
return memo[STATE]
ans = RECURRENCE_RELATION(STATE)
memo[STATE] = ans
return ans
memo = []
return de(STATE_FOR_WHOLE_INPUT)
- dp(STATE): 这是一个递归函数,它返回基于当前状态STATE的答案。
- BASE_CASE: 基本情况,通常在递归中会有一个或多个基本情况,以结束递归。
- STATE: 代表了当前的问题状态。这通常是一个或多个变量的组合,这些变量描述了当前的问题。
- memo: 用于存储已经计算过的状态的答案,防止重复计算。
- RECURRENCE_RELATION(STATE): 递归关系。这通常是动态规划中的核心部分,描述了如何基于其他状态来计算当前状态的答案。
- STATE_FOR_WHOLE_INPUT: 这描述了整个输入的初始状态。当你开始递归时,你会从这个状态开始。
23.构建前缀树(字典树)
# 注意:只有需要在每个节点上存储数据时才需要使用类。
# 否则,您可以只使用哈希映射实现一个前缀树。
class TrieNode:
def __init__(self):
# you can store data at nodes if you wish
self.data = None
self.children = {}
def fn(words):
root = TrieNode()
for word in words:
curr = root
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
# 这个位置上的 curr 已经有一个完整的单词
# 如果你愿意,你可以在这里执行更多的操作来给 curr 添加属性
return root
24.二叉树
总结:
前序:根左右
中序:左根右
后序:左右根;
中序常用来在二叉搜索数中得到递增的有序序列
后序可用于数学中的后缀表示法,结合栈处理表达式,每遇到一个操作符,就可以从栈中弹出栈顶的两个元素,计算并将结果返回到栈中
25.分治算法
分治通常基于递归实现,包括“分”和“治”两个步骤。
- 分(划分阶段):递归地将原问题分解为两个或多个子问题,直至到达最小子问题时终止。
- 治(合并阶段):从已知解的最小子问题开始,从底至顶地将子问题的解进行合并,从而构建出原问题的解。
如何判断分治问题
- 问题可以分解:原问题可以分解成规模更小、类似的子问题,以及能够以相同方式递归地进行划分。
- 子问题是独立的:子问题之间没有重叠,互不依赖,可以独立解决。
- 子问题的解可以合并:原问题的解通过合并子问题的解得来。
26.贪心算法
「贪心算法 greedy algorithm」是一种常见的解决优化问题的算法,其基本思想是在问题的每个决策阶段,都选择当前看起来最优的选择,即贪心地做出局部最优的决策,以期获得全局最优解。贪心算法简洁且高效,在许多实际问题中有着广泛的应用。
贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处,比如都依赖最优子结构性质,但工作原理不同。
- 动态规划会根据之前阶段的所有决策来考虑当前决策,并使用过去子问题的解来构建当前子问题的解。
- 贪心算法不会考虑过去的决策,而是一路向前地进行贪心选择,不断缩小问题范围,直至问题被解决。
一般情况下,贪心算法的适用情况分以下两种。
- 可以保证找到最优解:贪心算法在这种情况下往往是最优选择,因为它往往比回溯、动态规划更高效。
- 可以找到近似最优解:贪心算法在这种情况下也是可用的。对于很多复杂问题来说,寻找全局最优解非常困难,能以较高效率找到次优解也是非常不错的。