[{"type":"Heading1","children":[{"text":"二分开区间求最小"}],"slateId":"xzF9FkI1kk2Re7y3S7ugw"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"class Solution:\n # 计算满足 check(x) == True 的最小整数 x\n def binarySearchMin(self, nums: List[int]) -> int:\n # 二分猜答案：判断 mid 是否满足题目要求\n def check(mid: int) -> bool:\n # TODO\n\n left = # 循环不变量：check(left) 恒为 False\n right = # 循环不变量：check(right) 恒为 True\n while left + 1 < right: # 开区间不为空\n mid = (left + right) // 2\n if check(mid): # 说明 check(>= mid 的数) 均为 True\n right = mid # 接下来在 (left, mid) 中二分答案\n else: # 说明 check(<= mid 的数) 均为 False\n left = mid # 接下来在 (mid, right) 中二分答案\n # 循环结束后 left+1 = right\n # 此时 check(left) == False 而 check(left+1) == check(right) == True\n # 所以 right 就是最小的满足 check 的值\n return right\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/SqopEo/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"n80wpWUxQJOtP-k-PgYN1"}],"slateId":"rWnBcVNBLAYBoDLC2m1i5"},{"type":"Heading1","children":[{"text":"网格图dfs"}],"slateId":"s5b8mr22dmOenl3YPYeel"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"# 返回网格图 grid 每个连通块的大小\n# 时间复杂度 O(mn)\ndef dfsGrid(grid: List[List[str]]) -> List[int]:\n m, n = len(grid), len(grid[0])\n vis = [[False] * n for _ in range(m)]\n\n # 返回当前连通块的大小\n def dfs(i: int, j: int) -> int:\n vis[i][j] = True\n size = 1\n for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j): # 左右上下\n # 这里 grid[x][y] == '.' 根据题意修改\n if 0 <= x < m and 0 <= y < n and grid[x][y] == '.' and not vis[x][y]:\n size += dfs(x, y)\n return size\n\n comp_size = []\n for i, row in enumerate(grid):\n for j, ch in enumerate(row):\n if ch != '.' or vis[i][j]: # ch != '.' 根据题意修改\n continue\n size = dfs(i, j)\n comp_size.append(size)\n return comp_size\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/YiXPXW/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"HOwAHH4mDvSElKgeI3RpV"}],"slateId":"vxifnRUe26_1kWoNvWAMP"},{"type":"Heading1","children":[{"text":"网格图bfs"}],"slateId":"dVvOq0IR3iNmXA99g63Ee"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"# 返回从 (start_x, start_y) 出发，到其余格子的最短距离\n# 时间复杂度 O(mn)\ndef bfsGrid(grid: List[List[str]], start_x: int, start_y: int) -> List[List[int]]:\n m, n = len(grid), len(grid[0])\n dis = [[-1] * n for _ in range(m)]\n\n dis[start_x][start_y] = 0\n q = deque([(start_x, start_y)])\n\n while q:\n i, j = q.popleft()\n for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j): # 左右上下\n # 这里 grid[x][y] == '.' 根据题意修改\n if 0 <= x < m and 0 <= y < n and grid[x][y] == '.' and dis[x][y] < 0:\n dis[x][y] = dis[i][j] + 1\n q.append((x, y))\n\n return dis\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/YiXPXW/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"pLQ0nrFXelr9_MCcJHybt"}],"slateId":"xwXm0G-YgZFhPXOAp7r5E"},{"type":"Heading1","children":[{"text":" 深度优先搜索（DFS）"}],"slateId":"UQ5oZHWLRoY0XukaCFby1"},{"type":"Paragraph","children":[{"text":"找连通块、判断是否有环（如 207 题）等。"}],"slateId":"LJ0yT_U6salyx-BLFj64J"},{"type":"Paragraph","slateId":"DzaPj-8I2LVYA7Jm6nJti","children":[{"text":"一般并查集用于无向图判环，dfs三色法用于有向图判环"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"vector solve(int n, vector>& edges) {\n // 节点编号从 0 到 n-1\n vector> g(n);\n for (auto& e : edges) {\n int x = e[0], y = e[1];\n g[x].push_back(y);\n g[y].push_back(x); // 无向图\n }\n\n vector vis(n);\n\n // lambda 递归\n auto dfs = [&](this auto&& dfs, int x) -> int {\n vis[x] = true; // 避免重复访问节点\n int size = 1;\n for (int y : g[x]) {\n if (!vis[y]) {\n size += dfs(y);\n }\n }\n return size;\n };\n\n // 计算每个连通块的大小\n vector ans;\n for (int i = 0; i < n; i++) {\n if (!vis[i]) { // i 没有访问过\n int size = dfs(i);\n ans.push_back(size);\n }\n }\n return ans;\n}\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/01LUak/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"eFZ69nnkf3PGiDPZS4vUO"}],"slateId":"uvq0FMf2hdBT9t_kGNbtO"},{"type":"Heading1","slateId":"BbbXeCD54X_tNmyoOISmw","children":[{"text":"图论广度优先搜索（BFS）"}]},{"type":"Paragraph","children":[{"text":"求边权为1的最短路"}],"slateId":"4s0pQ1P3CUsv_4YBC1eyd"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"# 计算从 start 到各个节点的最短路长度\n# 如果节点不可达，则最短路长度为 -1\n# 节点编号从 0 到 n-1，边权均为 1\ndef bfs(n: int, edges: List[List[int]], start: int) -> List[int]:\n g = [[] for _ in range(n)]\n for x, y in edges:\n g[x].append(y)\n g[y].append(x) # 无向图\n\n dis = [-1] * n # -1 表示尚未访问到\n dis[start] = 0\n q = deque([start])\n while q:\n x = q.popleft()\n for y in g[x]:\n if dis[y] < 0:\n dis[y] = dis[x] + 1\n q.append(y)\n return dis\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/01LUak/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"Nnm6-lGOX77fBalrmKxTC"}],"slateId":"FzYC50QqPwnhVQJCkF-Bt"},{"type":"Heading1","children":[{"text":"拓扑排序"}],"slateId":"z7SRlvRk6Uw0Vv1NmX1FE"},{"type":"Paragraph","children":[{"text":"同样可以判环，但不适合追踪环，本质上是bfs判环"}],"slateId":"5Rys6Ku5QHccSJbu5a-yS"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"# 返回有向无环图（DAG）的其中一个拓扑序\n# 如果图中有环，返回空列表\n# 节点编号从 0 到 n-1\ndef topologicalSort(n: int, edges: List[List[int]]) -> List[int]:\n g = [[] for _ in range(n)]\n in_deg = [0] * n\n for x, y in edges:\n g[x].append(y)\n in_deg[y] += 1 # 统计 y 的先修课数量\n\n topo_order = []\n q = deque(i for i, d in enumerate(in_deg) if d == 0) # 没有先修课，可以直接上\n while q:\n x = q.popleft()\n topo_order.append(x)\n for y in g[x]:\n in_deg[y] -= 1 # 修完 x 后，y 的先修课数量减一\n if in_deg[y] == 0: # y 的先修课全部上完\n q.append(y) # 加入学习队列\n\n if len(topo_order) < n: # 图中有环\n return []\n return topo_order\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/01LUak/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 "}],"slateId":"ui6Q5Rjri9bWjYTu-UvqQ"}],"slateId":"Ydh4f_YKP30MI0c_nAjKv"},{"type":"Heading1","children":[{"text":"堆优化的Dijkstra求单源最短路"}],"slateId":"wCx8ohC3kz-BhZWv3xtBg"},{"type":"Paragraph","children":[{"text":"本质上是bfs+贪心的结合"}],"slateId":"sVwP02HZe60q1Tv7JjZMs"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"# 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = math.inf\n# 要求：没有负数边权\n# 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度。注意堆中有 O(m) 个元素\ndef shortestPathDijkstra(n: int, edges: List[List[int]], start: int) -> List[int]:\n # 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一\n g = [[] for _ in range(n)] # 邻接表\n for x, y, wt in edges:\n g[x].append((y, wt))\n # g[y].append((x, wt)) # 无向图加上这行\n\n dis = [inf] * n\n dis[start] = 0 # 起点到自己的距离是 0\n h = [(0, start)] # 堆中保存 (起点到节点 x 的最短路长度，节点 x)\n\n while h:\n dis_x, x = heappop(h)\n if dis_x > dis[x]: # x 之前出堆过\n continue\n for y, wt in g[x]:\n new_dis_y = dis_x + wt\n if new_dis_y < dis[y]:\n dis[y] = new_dis_y # 更新 x 的邻居的最短路\n # 懒更新堆：只插入数据，不更新堆中数据\n # 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue\n heappush(h, (new_dis_y, y))\n\n return dis\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/01LUak/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"PTwcFVFqmFEopRCts2DEU"}],"slateId":"DmTgEFwQB_OV5YAbQKkii"},{"type":"Heading1","children":[{"text":"Kruskal求最小生成树"}],"slateId":"NgKdwLMt8_G9tx4WaX-xf"},{"type":"Paragraph","children":[{"text":"并查集的应用"}],"slateId":"RTVrUXCqJ6SdalUnoVsSs"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"class UnionFind:\n def __init__(self, n: int):\n # 一开始有 n 个集合 {0}, {1}, ..., {n-1}\n # 集合 i 的代表元是自己\n self._fa = list(range(n)) # 代表元\n self.cc = n # 连通块个数\n\n # 返回 x 所在集合的代表元\n # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元\n def find(self, x: int) -> int:\n # 如果 fa[x] == x，则表示 x 是代表元\n if self._fa[x] != x:\n self._fa[x] = self.find(self._fa[x]) # fa 改成代表元\n return self._fa[x]\n\n # 把 from 所在集合合并到 to 所在集合中\n # 返回是否合并成功\n def merge(self, from_: int, to: int) -> bool:\n x, y = self.find(from_), self.find(to)\n if x == y: # from 和 to 在同一个集合，不做合并\n return False\n self._fa[x] = y # 合并集合。修改后就可以认为 from 和 to 在同一个集合了\n self.cc -= 1 # 成功合并，连通块个数减一\n return True\n\n\n# 计算图的最小生成树的边权之和\n# 如果图不连通，返回 math.inf\n# 节点编号从 0 到 n-1\n# 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度\ndef mstKruskal(n: int, edges: List[List[int]]) -> int:\n edges.sort(key=lambda e: e[2])\n\n uf = UnionFind(n)\n sum_wt = 0\n for x, y, wt in edges:\n if uf.merge(x, y):\n sum_wt += wt\n\n if uf.cc > 1: # 图不连通\n return inf\n return sum_wt\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/01LUak/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"ZsAh68F1kQFu02zyLDrrX"}],"slateId":"Hn66KX25L2eGtFMUjm09j"},{"type":"Heading1","children":[{"text":"字典树Trie"}],"slateId":"98zdIphkVc0_I7sREc5Sj"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"class Node:\n __slots__ = 'son', 'end'\n\n def __init__(self):\n self.son = {}\n self.end = False\n\nclass Trie:\n def __init__(self):\n self.root = Node()\n\n def insert(self, word: str) -> None:\n cur = self.root\n for c in word:\n if c not in cur.son: # 无路可走？\n cur.son[c] = Node() # 那就造路！\n cur = cur.son[c]\n cur.end = True\n\n def find(self, word: str) -> int:\n cur = self.root\n for c in word:\n if c not in cur.son: # 道不同，不相为谋\n return 0\n cur = cur.son[c]\n # 走过同样的路（2=完全匹配，1=前缀匹配）\n return 2 if cur.end else 1\n\n def search(self, word: str) -> bool:\n return self.find(word) == 2\n\n def startsWith(self, prefix: str) -> bool:\n return self.find(prefix) != 0\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/2993894/cong-er-cha-shu-dao-er-shi-liu-cha-shu-p-xsj4/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"0hds6LDJCycWWXfQmbbQX"}],"slateId":"l-CLp5RtY3W6AhjWzZ20B"},{"type":"Heading1","children":[{"text":"并查集"}],"slateId":"wfBX4WwMeTwpkb8fcG1oq"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"python3","name":"","children":[{"text":"# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/\nclass UnionFind:\n def __init__(self, n: int):\n # 一开始有 n 个集合 {0}, {1}, ..., {n-1}\n # 集合 i 的代表元是自己，大小为 1\n self._fa = list(range(n)) # 代表元\n self._size = [1] * n # 集合大小\n self.cc = n # 连通块个数\n\n # 返回 x 所在集合的代表元\n # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元\n def find(self, x: int) -> int:\n fa = self._fa\n # 如果 fa[x] == x，则表示 x 是代表元\n if fa[x] != x:\n fa[x] = self.find(fa[x]) # fa 改成代表元\n return fa[x]\n\n # 判断 x 和 y 是否在同一个集合\n def is_same(self, x: int, y: int) -> bool:\n # 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合\n # 这就是代表元的作用：用来快速判断两个元素是否在同一个集合\n return self.find(x) == self.find(y)\n\n # 把 from 所在集合合并到 to 所在集合中\n # 返回是否合并成功\n def merge(self, from_: int, to: int) -> bool:\n x, y = self.find(from_), self.find(to)\n if x == y: # from 和 to 在同一个集合，不做合并\n return False\n self._fa[x] = y # 合并集合。修改后就可以认为 from 和 to 在同一个集合了\n self._size[y] += self._size[x] # 更新集合大小（注意集合大小保存在代表元上）\n # 无需更新 _size[x]，因为我们不用 _size[x] 而是用 _size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 _size[x]\n self.cc -= 1 # 成功合并，连通块个数减一\n return True\n\n # 返回 x 所在集合的大小\n def get_size(self, x: int) -> int:\n return self._size[self.find(x)] # 集合大小保存在代表元上\n\n作者：灵茶山艾府\n链接：https://leetcode.cn/discuss/post/mOr1u6/\n来源：力扣（LeetCode）\n著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}],"slateId":"8ADBv1CxrBjRlBJDM9tNx"}],"slateId":"G9gsY2hiesHEXqwj-5JW_"}]