本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3550. 数位和等于下标的最小下标 - 力扣（LeetCode）
解题思路
遍历，按要求求数位和，满足条件返回下标
示例代码
python
class Solution:
def smallestIndex(self, nums: List[int]) -> int:
for i, x in enumerate(nums):
s = sum(map(int, str(x)))
if s == i:
return i
return -13551. 数位和排序需要的最小交换次数 - 力扣（LeetCode）
解题思路
排序，找循环节个数，每个循环节交换次数为节的长度 - 1
示例代码
python
class Solution:
def minSwaps(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
a = sorted(range(n), key=lambda p: nums[p])
b = sorted(a, key=lambda p: (sum(map(int, str(nums[p])))))
vis = [False] * n
for i in range(n):
if i != b[i] and not vis[i]:
while i != b[i] and not vis[b[i]]:
vis[i] = True
i = b[i]
ans += 1
return ans3552. 网格传送门旅游 - 力扣（LeetCode）
解题思路
01BFS，不能重新建图套最短路模板，会超时；传送门使用一次后，全部清空，防止再次使用
示例代码
python
class Solution:
def minMoves(self, matrix: List[str]) -> int:
n, m = len(matrix), len(matrix[0])
d = defaultdict(list)
for i, row in enumerate(matrix):
for j, c in enumerate(row):
if c in ascii_uppercase:
d[c].append((i, j))
q = deque([(0, 0)])
dis = [[inf] * m for _ in range(n)]
dis[0][0] = 0
while q:
x, y = q.popleft()
if x == n - 1 and y == m - 1:
return dis[n - 1][m - 1]
c = matrix[x][y]
if c in ascii_uppercase and d[c]:
for nx, ny in d[c]:
if x != nx or y != ny and dis[nx][ny] > dis[x][y]:
dis[nx][ny] = dis[x][y]
q.appendleft((nx, ny))
del d[c]
for dx, dy in (1, 0), (0, 1), (-1, 0), (0, -1):
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] != '#' and dis[x][y] + 1 < dis[nx][ny]:
dis[nx][ny] = dis[x][y] + 1
q.append((nx, ny))
return -13553. 包含给定路径的最小带权子树 II - 力扣（LeetCode）
解题思路
lca 模板题，由于是在树内，三个节点必存在交点，最小子树权值其实也就是交点到三个节点的路径上的权值之和
赛时没做
示例代码
python
class Solution:
def minimumWeight(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
lca = LcaWithWeight(edges)
return [(lca.get_dis(a, b) + lca.get_dis(b, c) + lca.get_dis(a, c)) // 2 for a, b, c in queries]py
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