直径长度 def diameter(self, edges: List[List[int]]) -> int: g = [[] for _ in range(len(edges) + 1)] for x, y in edges: g[x].append(y) g[y].append(x) res = 0 # 用于存储树的直径 def dfs(…

Q：为什么灵茶山艾府喜欢用 Go 语言刷题？ A：我需要一个库函数丰富、有零拷贝切片、运行效率高且语法简单的语言，综合来看选了 Go。目前已基于 Go 实现了大部分竞赛算法，见 【算法竞赛模板库】 https://github.com/EndlessCheng/codeforces-go 【Go 语言相关资料】 快速入门 https://gobye…

状态压缩是一种常用于动态规划问题的技术，尤其适用于解决涉及多个状态的组合问题。它通过使用一个整数的位表示多个状态，从而大幅降低空间和时间复杂度。 状态压缩是用二进制进行压缩的,你需要了解位运算的基本运用:从集合论到位运算,当我们遇到处理数据很小的时候,比如n<20以内,可以考虑下状压。其中状压dp有相邻相关,相邻无关等类型，下面我会概述一下这…

我们在写某些字符串问题上经常需要用到一些基础架构, 当然你可以选择直接暴力。一般，我会选择一些效率够高的函数模板,因为你需要多次调用。以下是我总结的几个关于常用的字符串操作模板: 判断x是否为y的子序列: class Solution: def isSubsequence(self, s: str, t: str) -> bool: i = …

离散化（discretization）是一种数据处理技术，特别适用于数值范围较大但实际数据分布较稀疏的情况。以下是一些离散化的主要用途和优点： 减少数值范围： 离散化可以将较大范围的数值数据映射到较小范围的整数，减少处理复杂度和计算开销。 处理重复值： 在原始数据中，可能存在重复值，通过离散化可以将这些值映射到同一个整数值，从而更容易进行后续的处理…

kmp def prep(p): pi = [0] * len(p) j = 0 for i in range(1, len(p)): while j != 0 and p[j] != p[i]: j = pi[j - 1] if p[j] == p[i]: j += 1 pi[i] = j return pi 匹配： $ 仅作为标识符，分割战场。…

先从一个例题出发 假设有一个数组array[0…n-1]，里面有n个元素，现在我们要经常对这个数组做两件事： 更新数组元素的数值 求数组任意一段区间里元素的总和（或者平均值） 我有哪些方法实现上述操作? 1. 方法一：遍历一遍数组 时间复杂度：O(n) 方法二：线段树☑️ 时间复杂度：O(logn) 直接奉上线段树模板： 线段树：单点修改，区间查询…

字典树 https://leetcode.cn/problems/implement-trie-prefix-tree/description/ # 定义Trie节点类 class TrieNode: __slots__ = 'children', 'is_end_of_word' def __init__(…

树状数组（时间复杂度On）：常用于处理动态数组的前缀和/区间和查询和单点更新 leetcode原题链接：https://leetcode.cn/problems/range-sum-query-mutable/description/?envType=daily-question&envId=2023-11-13 class Fenwick…

时间复杂度不高，复杂度为logU（U为遍历最大值） https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/description/ class Solution: def numberOfPairs(self, nums1: List[int], nums2: List[int]…