本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Q1. 使数组和能被 K 整除的最少操作次数
解题思路
贪心
示例代码
python
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
return sum(nums) % kQ2. 不同 XOR 三元组的数目 I
解题思路
贪心，找规律
示例代码
python
class Solution:
def uniqueXorTriplets(self, nums: List[int]) -> int:
n = len(nums)
if n <= 2:
return n
return 1 << n.bit_length()Q3. 不同 XOR 三元组的数目 II
解题思路
暴力，枚举
示例代码
python
class Solution:
def uniqueXorTriplets(self, nums: List[int]) -> int:
ans1 = set()
ans2 = set()
ans3 = set()
for x in nums:
ans1.add(x)
ans2.update(x ^ y for y in ans1)
ans3.update(x ^ y for y in ans2)
return len(ans3)Q4. 带权树中的最短路径
解题思路
计算 dfs 时间戳，用线段树维护区间和，或用差分树状数组维护区间和。
示例代码
python
class Solution:
def treeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
g = defaultdict(list)
for x, y, w in edges:
g[x].append(y)
g[y].append(x)
in_ = [0] * (n + 1)
out = [0] * (n + 1)
clock = 0
def dfs(x: int, fa: int) -> None:
nonlocal clock
clock += 1
in_[x] = clock
for y in g[x]:
if y == fa: continue
dfs(y, x)
out[x] = clock
dfs(1, 0)
weight = [0] * (n + 1)
diff = Fenwick(n)
def update(x: int, y: int, w: int) -> None:
if in_[x] > in_[y]:
y = x
d = w - weight[y]
weight[y] = w
diff.update(in_[y], d)
diff.update(out[y] + 1, -d)
for x, y, w in edges:
update(x, y, w)
ans = []
for q in queries:
if q[0] == 1:
update(*q[1:])
else:
ans.append(diff.query(in_[q[1]]))
return anspy
class Fenwick:
__slots__ = ["n", "c"]
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int):
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x > 0:
s += self.c[x]
x -= x & -x
return s