本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3582. 为视频标题生成标签 - 力扣（LeetCode）
解题思路
用库函数实现首字母大写，其余小写
示例代码
python
class Solution:
def generateTag(self, caption: str) -> str:
ans = ['#']
for i, c in enumerate(caption.split()):
ans.append(c.title() if i else c.lower())
return ''.join(ans)[:100]3583. 统计特殊三元组 - 力扣（LeetCode）
解题思路
哈希表，或前后缀分解
示例代码
python
class Solution:
def specialTriplets(self, nums: List[int]) -> int:
mod = 10 ** 9 + 7
d = defaultdict(int)
cnt = defaultdict(int)
ans = s = 0
for i, x in enumerate(nums):
if x == 0:
s += 1
continue
d[(x * 2, x)] += cnt[x * 2]
cnt[x] += 1
ans += d[(x, x // 2)]
return (ans + comb(s, 3)) % modpython
class Solution:
def specialTriplets(self, nums: List[int]) -> int:
mod = 10 ** 9 + 7
suf = Counter(nums)
pre = defaultdict(int)
ans = 0
for x in nums:
suf[x] -= 1
ans += pre[x * 2] * suf[x * 2]
pre[x] += 1
return ans % mod3584. 子序列首尾元素的最大乘积 - 力扣（LeetCode）
解题思路
前后缀最值，代码复用
或脑筋急转弯，见参考
示例代码
python
class Solution:
def maximumProduct(self, nums: List[int], m: int) -> int:
n = len(nums)
def cal(f, initial):
pre = [initial] * (n + 1)
suf = [initial] * (n + 1)
for i, x in enumerate(nums):
pre[i + 1] = f(pre[i], x)
for i in range(n - 1, -1, -1):
suf[i] = f(suf[i + 1], nums[i])
ans = -inf
for i in range(n - m + 1):
ans = max(ans, pre[i + 1] * suf[i + m - 1])
return ans
return max(cal(max, -inf), cal(min, inf))python
class Solution:
def maximumProduct(self, nums: List[int], m: int) -> int:
ans = mx = -inf
mn = inf
for i in range(m - 1, len(nums)):
# 维护左边 [0,i-m+1] 中的最小值和最大值
y = nums[i - m + 1]
mn = min(mn, y)
mx = max(mx, y)
# 枚举右
x = nums[i]
ans = max(ans, x * mn, x * mx)
return ans3585. 树中找到带权中位节点 - 力扣（LeetCode）
解题思路
中心扩展，枚举每个节点，时间复杂度O(n*n)，包超时的
带权 lca，判段左右路径权值，在沿路径寻找中位节点
示例代码
python
class Solution:
def findMedian(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
g = LcaWithWeight(edges)
ans = [0] * len(queries)
for i, (u, v) in enumerate(queries):
if u == v:
ans[i] = u
continue
lca = g.get_lca(u, v)
dis_uv = g.dis[u] + g.dis[v] - 2 * g.dis[lca]
half = (dis_uv + 1) // 2
if g.dis[u] - g.dis[lca] < half:
ans[i] = g.upto_dis(v, dis_uv - half)
else:
to = g.upto_dis(u, half - 1)
ans[i] = g.pa[to][0]
return anspy
from typing import List
class LcaWithWeight:
__slots__ = ["depth", "dis", "pa", "m"]
def __init__(self, edges: List[List[int]]) -> None:
n = len(edges) + 1
g = [[] for _ in range(n)]
self.m = m = n.bit_length()
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))
q = [0]
for u in q:
for v, w in g[u]:
if v == pa[u][0]:
continue
pa[v][0] = u
depth[v] = depth[u] + 1
dis[v] = dis[u] + w
q.append(v)
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, x: int, k: int) -> int:
"""返回 x 的第 k 个祖先"""
for i in range(k.bit_length()):
if k >> i & 1:
x = self.pa[x][i]
if x == -1:
break
return x
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 x == y:
return x
for i in reversed(range(len(self.pa[x]))):
if self.pa[x][i] != self.pa[y][i]:
x = self.pa[x][i]
y = self.pa[y][i]
return self.pa[x][0]
def get_dis(self, x: int, y: int) -> int:
"""返回 x 和 y 之间的路径权值和（distance）"""
return self.dis[x] + self.dis[y] - 2 * self.dis[self.get_lca(x, y)]
def upto_dis(self, x: int, d: int) -> int:
"""返回 x 向上跳至多 d 距离能到达的最远节点"""
dx = self.dis[x]
for i in range(self.m - 1, -1, -1):
p = self.pa[x][i]
if p != -1 and dx - self.dis[p] <= d:
x = p
return x