算法代码题——模板

1. 双指针: 只有一个输入, 从两端开始遍历

def fn(arr):left = ans = 0right = len(arr) - 1while left < right:# 一些根据 letf 和 right 相关的代码补充if CONDITION:left += 1else:right -= 1return ans

2. 双指针: 有两个输入, 两个都需要遍历完

def fn(arr1, arr2):i = j = ans = 0while i < len(arr1) and j < len(arr2):# 根据题意补充代码if CONDITION:i += 1else:j += 1while i < len(arr1):# 根据题意补充代码i += 1while j < len(arr2):# 根据题意补充代码j += 1return ans

3. 滑动窗口

def fn(arr):left = ans = curr = 0for right in range(len(arr)):# 根据题意补充代码来将 arr[right] 添加到 currwhile WINDOW_CONDITION_BROKEN:# 从 curr 中删除 arr[left]left += 1# 更新 ansreturn ans

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 = headfast = headans = 0while fast and fast.next:# 根据题意补充代码slow = slow.nextfast = fast.next.nextreturn ans

7. 反转链表

def fn(head):curr = headprev = Nonewhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_node return prev

8. 找到符合确切条件的子数组数

from collections import defaultdictdef fn(arr, k):counts = defaultdict(int)counts[0] = 1ans = curr = 0for num in arr:# 根据题意补充代码来改变 currans += counts[curr - k]counts[curr] += 1return ans

9. 单调递增栈

def fn(arr):stack = []ans = 0for num in arr:# 对于单调递减的情况，只需将 > 翻转到 <while stack and stack[-1] > num:# 根据题意补充代码stack.pop()stack.append(num)return ans

10. 二叉树: DFS (递归)]

def dfs(root):if not root:returnans = 0# 根据题意补充代码dfs(root.left)dfs(root.right)return ans

11. 二叉树: DFS (迭代)

def dfs(root):stack = [root]ans = 0while 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 dequedef fn(root):queue = deque([root])ans = 0while 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 (递归)

以下图模板假设节点编号从 0 到 n - 1 ，并且图是以邻接表的形式给出的。

• 根据问题的不同，可能需要在使用模板之前将输入转换为等效的邻接表。

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 ansseen = {START_NODE}return dfs(START_NODE)

14. 图: DFS (迭代)

def fn(graph):stack = [START_NODE]seen = {START_NODE}ans = 0while 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 dequedef fn(graph):queue = deque([START_NODE])seen = {START_NODE}ans = 0while 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 heapqdef fn(arr, k):heap = []for num in arr:# 做根据题意补充代码，根据问题的条件来推入堆中heapq.heappush(heap, (CRITERIA, num))if len(heap) > k:heapq.heappop(heap)return [num for num in heap]

17. 二分查找

def fn(arr, target):left = 0right = len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:# 根据题意补充代码returnif arr[mid] > target:right = mid - 1else:left = mid + 1# left 是插入点return left

18. 二分查找: 重复元素，最左边的插入点

def fn(arr, target):left = 0right = len(arr)while left < right:mid = (left + right) // 2if arr[mid] >= target:right = midelse:left = mid + 1return left

19. 二分查找: 重复元素，最右边的插入点

def fn(arr, target):left = 0right = len(arr)while left < right:mid = (left + right) // 2if arr[mid] > target:right = midelse:left = mid + 1return left

20. 二分查找: 贪心问题

寻找最小值：

def fn(arr):def check(x):# 这个函数的具体实现取决于问题return BOOLEANleft = MINIMUM_POSSIBLE_ANSWERright = MAXIMUM_POSSIBLE_ANSWERwhile left <= right:mid = (left + right) // 2if check(mid):right = mid - 1else:left = mid + 1return left

寻找最大值：

def fn(arr):def check(x):# 这个函数的具体实现取决于问题return BOOLEANleft = MINIMUM_POSSIBLE_ANSWERright = MAXIMUM_POSSIBLE_ANSWERwhile left <= right:mid = (left + right) // 2if check(mid):left = mid + 1else:right = mid - 1return right

21. 回溯

def backtrack(curr, OTHER_ARGUMENTS...):if (BASE_CASE):# 修改答案returnans = 0for (ITERATE_OVER_INPUT):# 修改当前状态ans += backtrack(curr, OTHER_ARGUMENTS...)# 撤消对当前状态的修改return ans

22. 动态规划: 自顶向下法

def fn(arr):def dp(STATE):if BASE_CASE:return 0if STATE in memo:return memo[STATE]ans = RECURRENCE_RELATION(STATE)memo[STATE] = ansreturn ansmemo = {}return dp(STATE_FOR_WHOLE_INPUT)

23. 构建前缀树（字典树）

• 注意:只有需要在每个节点上存储数据时才需要使用类。
• 否则，您可以只使用哈希映射实现一个前缀树。

# 注意:只有需要在每个节点上存储数据时才需要使用类。
# 否则，您可以只使用哈希映射实现一个前缀树。
class TrieNode:def __init__(self):# you can store data at nodes if you wishself.data = Noneself.children = {}def fn(words):root = TrieNode()for word in words:curr = rootfor c in word:if c not in curr.children:curr.children[c] = TrieNode()curr = curr.children[c]# 这个位置上的 curr 已经有一个完整的单词# 如果你愿意，你可以在这里执行更多的操作来给 curr 添加属性return root