算法题基本框架 - Python实现
二叉树
DFS
二叉搜索树的中序遍历即为这棵树叶子节点值从小到大的排列
def dfs(root: TreeNode):
if not root:
return
# 先序遍历
dfs(root.left)
# 中序遍历
dfs(root.right)
# 后续遍历BFS
from collections import deque
def bfs(root: TreeNode, target: TreeNode):
queue = deque()
# 记录访问的节点避免走回头路
vistied = []
# 起点在循环外入队
queue.append(root)
vistied.append(root)
step = 0
while queue:
# 先记录此时队列长度，避免将新入队元素算入本次循环
length = len(queue)
for i in range(length):
cur = queue.popleft()
# 判断是否到达终点（此处需改成符合题意的条件）
if cur is target:
return step
# 将cur相邻节点入队，adj()泛指cur相邻节点
for x in cur.adj():
if x not in vistied:
queue.append(x)
vistied.append(x)
step += 1回溯算法
例题: 46.全排列
本质上为N叉树的遍历 + 决策
class Solution:
def __init__(self):
self.ans = []
self.sub_ans = []
# 主函数
def permute(self, nums: List[int]) -> List[List[int]]:
self.helper(nums)
return self.ans
def helper(self, nums):
# 触发结束条件
if len(self.sub_ans) == len(nums):
self.ans.append(self.sub_ans)
return
for num in nums:
# 排除非法的选择
if num in self.sub_ans:
continue
# 做选择
self.sub_ans.append(num)
# 进入决策树
self.helper(nums)
# 取消当前选择
self.sub_ans = self.sub_ans[:-1]二分查找
精确搜索
def binary_search(nums, target):
"""
:param nums: 递增的排序数组
:param target: 目标
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
return mid
return -1查找左边界
def left_search(nums, target):
"""
:param nums: 递增的排序数组
:param target: 目标
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
right = mid - 1
if left >= len(nums) or nums[left] != target:
return -1
return left查找右边界
def right_search(nums, target):
"""
:param nums: 递增的排序数组
:param target: 目标
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
left = mid + 1
if left < 0 or nums[left] != target:
return -1
return left滑动窗口
有固定长度的目标
例题: 76.最小覆盖子串
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
"""
:param s: "ADOBECODEBANC"
:param t: "ABC"
"""
window = {}
need = Counter(t)
left, right = 0, 0
is_valid = 0
start = 0
length = float("INF")
while right < len(s):
c = s[right]
right += 1
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
is_valid += 1
while is_valid == len(need):
if right - left < length:
start = left
length = right - left
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
is_valid -= 1
window[d] = window[d] - 1
return s[start: length+start] if length != float("INF") else ""无固定长度的目标
例题: 3.无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = {}
left, right = 0, 0
max_window = 0
while right < len(s):
c = s[right]
right += 1
window[c] = window.get(c, 0) + 1
while window[c] > 1:
d = s[left]
left += 1
if d in window:
window[d] -= 1
max_window = max(max_window, right - left)
return max_window并查集
通常情况下使用数组维护的并查集更省空间，因为直接定义了一个n条边的数组，使用下标来维护对应关系。但是遇到二维坐标时，用哈希维护的并查集更合适，因为可以把y映射到x取值范围外，使二维转化为一维。比如: 1584.连接所有点的最小费用
哈希维护(邻接表)
class UnionFind:
def __init__(self):
# 哈希维护的并查集在find()时添加边
self.fa = {}
# size 维护树的高度，尽量将小树连接到大树上
self.size = {}
# 连通分量(当前图有几个连通图),find()时+1，union()时-1
self.count = 0
def find(self, n):
# 当前点不存在
if n not in self.fa:
self.fa[n] = n
self.size[n] = 1
self.count += 1
if n == self.fa[n]:
return n
self.fa[n] = self.find(self.fa[n])
return self.fa[n]
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
# 如果在并查集构建完成中要求查询是否有连通关系，可以直接if uf.union(p, q)判断
return False
if self.size[root_p] < self.size[root_q]:
self.fa[root_p] = root_q
self.size[root_q] += self.size[root_p]
else:
self.fa[root_q] = root_p
self.size[root_p] += self.size[root_q]
self.count -= 1
return True
def is_connect(self, p, q):
# 如果在并查集构建完成后查询是否有连通关系则使用该函数
root_p = self.find(p)
root_q = self.find(q)
return root_p == root_q数组维护(使用下标维护的邻接矩阵，只有一维)
当需要连接的点为二维坐标时，可以用 i * 列数 + j 将二维投射到一维上来初始化
class UnionFind:
def __init__(self, n):
# 因为初始化的时候需要确定点的数量，同时也可把连通分量设为点的数量，即每个点都不与其他点相连
self.count = n
self.fa = [n for n in range(n)]
self.size = [1 for _ in range(n)]
def find(self, x):
while x != self.fa[x]:
x = self.fa[x]
self.fa[x] = self.fa[self.fa[x]]
return x
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
# 如果在并查集构建完成中要求查询是否有连通关系，可以直接if uf.union(p, q)判断
return False
if self.size[root_p] < self.size[root_q]:
self.fa[root_p] = root_q
self.size[root_q] += self.size[root_p]
else:
self.fa[root_q] = root_p
self.size[root_p] += self.size[root_q]
self.count -= 1
return True
def is_connect(self, p, q):
# 如果在并查集构建完成后查询是否有连通关系则使用该函数
root_p = self.find(p)
root_q = self.find(q)
return root_p == root_q变体 Kruskal 算法(贪心+并查集)
求图的最小生成树
其算法流程为：
- 将图 G={V,E}G={V,E} 中的所有边按照长度由小到大进行排序，等长的边可以按任意顺序。
- 初始化图 G’G′为 {V,\varnothing}{V,∅}，从前向后扫描排序后的边，如果扫描到的边 ee 在 G’G′中连接了两个相异的连通块,则将它插入 G’G′中。
- 最后得到的图 G’G′就是图 GG 的最小生成树。
例题: 1584.连接所有点的最小费用
from typing import List
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x):
while x != self.parent[x]:
x = self.parent[x]
self.parent[x] = self.parent[self.parent[x]]
return x
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return False
self.parent[root_p] = root_q
return True
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
edges = []
for i in range(len(points)):
for j in range(i+1, len(points)):
edges.append((self.route_cost(points[i], points[j]), i, j))
edges.sort()
min_cost, num = 0, 0
uf = UnionFind(len(points))
for cost, x, y in edges:
if uf.union(x, y):
min_cost += cost
num += 1
if num == len(points):
break
return min_cost
@staticmethod
def route_cost(a: List, b: List):
return abs(abs(a[1] - b[1]) + abs(a[0] - b[0]))
if __name__ == "__main__":
obj = Solution()
ans = obj.minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]])
print(ans)本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
