本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3556. 最大质数子字符串之和 - 力扣（LeetCode）
解题思路
暴力，枚举判断是否为质数
示例代码
python
class Solution:
def sumOfLargestPrimes(self, s: str) -> int:
def isPrime(n: int) -> bool:
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True if n > 1 else False
n = len(s)
ans = set()
for i in range(1, n + 1):
for j in range(n - i + 1):
x = int(s[j: j + i])
if isPrime(x):
ans.add(x)
return sum(sorted(ans)[-3:])3557. 不相交子字符串的最大数量 - 力扣（LeetCode）
解题思路
记忆化搜索，选或不选，二分查找最近的合法位置
划分型贪心，举例，如字符串ab???ba中，选 bb 优于选 aa，因为 a 还可以与后面字符进行匹配
示例代码
python
class Solution:
def maxSubstrings(self, word: str) -> int:
d = defaultdict(list)
for i, c in enumerate(word):
d[c].append(i)
@cache
def dfs(i):
if i == len(word):
return 0
res = dfs(i + 1)
j = bisect_left(d[word[i]], i + 3)
if j < len(d[word[i]]):
res = max(res, dfs(d[word[i]][j] + 1) + 1)
return res
ans = dfs(0)
dfs.cache_clear()
return anspython
class Solution:
def maxSubstrings(self, word: str) -> int:
ans = 0
pos = {}
for i, c in enumerate(word):
if c not in pos:
pos[c] = i
elif i - pos[c] > 2:
ans += 1
pos.clear()
return ans3558. 给边赋权值的方案数 I - 力扣（LeetCode）
解题思路
组合数计算，计算树的深度最大值，求和 C(mx, 1) + C(mx, 3) + … + C(mx, mx - mx % 2)， 其实就是 pow(2, mx - 1)，经验公式吧
简单推导一下，mx 为奇数时， s = sum(C(mx, i) for i in range(1, mx // 2, 2)) + C(mx, (mx + 1) // 2)= (pow(2, mx) - C(mx, (mx + 1) // 2)) // 2 + C(mx, (mx + 1) // 2) mx 为偶数时就是 pow(2, mx - 1)
示例代码
python
class Solution:
def assignEdgeWeights(self, edges: List[List[int]]) -> int:
n = len(edges) + 1
g = defaultdict(list)
depth = [0] * (n + 1)
for x, y in edges:
g[x].append(y)
g[y].append(x)
def dfs(x, fa):
for y in g[x]:
if y == fa: continue
depth[y] = depth[x] + 1
dfs(y, x)
dfs(1, 0)
mx = max(depth)
return pow(2, mx - 1, 1_000_000_007)3559. 给边赋权值的方案数 II - 力扣（LeetCode）
解题思路
就是前一道题加上一个 lca 模板，计算路径距离
示例代码
python
class Solution:
def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
n = len(edges) + 1
# w = 1
lca = LowestCommonAncestor([e + [1] for e in edges])
f = [1] * (n + 1)
for i in range(n):
f[i + 1] = f[i] * 2 % 1_000_000_007
ans = [0] * len(queries)
for i, (u, v) in enumerate(queries):
if u == v: continue
d = lca.get_dis(u, v)
ans[i] = f[d - 1]
return anspy
from typing import List
class LowestCommonAncestor:
__slots__ = ['depth', 'pa']
def __init__(self, edges: List[List[int]]) -> None:
n = len(edges) + 1
m = n.bit_length()
g = [[] for _ in range(n)]
self.depth = depth = [0] * n
self.pa = pa = [[-1] * m for _ in range(n)]
for x, y in edges: # 节点编号从 0 开始
g[x].append(y)
g[y].append(x)
def dfs(x: int, fa: int) -> None:
pa[x][0] = fa
for y in g[x]:
if y != fa:
depth[y] = depth[x] + 1
dfs(y, x)
dfs(0, -1)
for i in range(m - 1):
for x in range(n):
if (p := pa[x][i]) != -1:
pa[x][i + 1] = pa[p][i]
def get_kth_ancestor(self, node: int, k: int) -> int:
"""返回 node 的第 k 个祖先"""
for i in range(k.bit_length()):
if k >> i & 1:
node = self.pa[node][i]
return node
def get_lca(self, x: int, y: int) -> int:
"""返回 x 和 y 的最近公共祖先（节点编号从 0 开始）"""
if self.depth[x] > self.depth[y]:
x, y = y, x
y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x]) # 使 y 和 x 在同一深度
if y == x:
return x
for i in range(len(self.pa[x]) - 1, -1, -1):
px, py = self.pa[x][i], self.pa[y][i]
if px != py:
x, y = px, py # 同时上跳 2**i 步
return self.pa[x][0]
class LcaWithWeight:
__slots__ = ['depth', 'dis', 'pa']
def __init__(self, edges: List[List[int]]) -> None:
n = len(edges) + 1
m = n.bit_length()
g = [[] for _ in range(n)]
self.depth = depth = [0] * n
self.dis = dis = [0] * n
self.pa = pa = [[-1] * m for _ in range(n)]
for x, y, w in edges:
g[x].append((y, w))
g[y].append((x, w))
def dfs(x: int, fa: int) -> None:
pa[x][0] = fa
for y, w in g[x]:
if y != fa:
depth[y] = depth[x] + 1
dis[y] = dis[x] + w
dfs(y, x)
dfs(0, -1)
for i in range(m - 1):
for x in range(n):
if (p := pa[x][i]) != -1:
pa[x][i + 1] = pa[p][i]
def get_kth_ancestor(self, node: int, k: int) -> int:
"""返回 node 的第 k 个祖先"""
for i in range(k.bit_length()):
if k >> i & 1:
node = self.pa[node][i]
return node
def get_lca(self, x: int, y: int) -> int:
"""返回 x 和 y 的最近公共祖先（节点编号从 0 开始）"""
if self.depth[x] > self.depth[y]:
x, y = y, x
y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])
if y == x:
return x
for i in range(len(self.pa[x]) - 1, -1, -1):
px, py = self.pa[x][i], self.pa[y][i]
if px != py:
x, y = px, py
return self.pa[x][0]
def get_dis(self, x: int, y: int) -> int:
"""返回 x 和 y 之间的距离"""
return self.dis[x] + self.dis[y] - self.dis[self.get_lca(x, y)] * 2