这篇文章整理力扣中文站第 512 场周赛的四道题。四份 Java 17 代码都经过本地编译、样例与边界测试，并已在力扣获得 Accepted。
本场四题的思维跨度很有代表性：第一题从最高位做贪心，第二题用双指针维护“第一个不小于当前时间”的元素，第三题把“乘积为偶数”转成补集计数，第四题则必须把行动奇偶性并入最短路状态。
题目总览
| 题号 | 题目 | 核心方法 | 时间复杂度 | Accepted 提交 |
|---|---|---|---|---|
| 4000 | 给定数位和的最大整数 | 高位贪心 | O(n) | 738213138 |
| 4001 | 聚合两个时间序列 | 双指针归并 | O(n + m) | 738224005 |
| 4002 | 统计有效序列数目 | 补集计数、组合数学 | O(n + log MOD) | 738213380 |
| 4003 | 交替方向的最小路径代价 III | 分层图、Dijkstra | O(mn log(mn)) | 738224023 |
4000. 给定数位和的最大整数
给定非负整数 n 和 s，求一个至多有 n 位、各位数字之和为 s 的最大整数；若不存在则返回 -1。
核心思路
把不足 n 位的整数在左侧补零，它的数值和数位和都不会改变。问题于是等价于：构造一个字典序最大的、长度恰好为 n 的数位串。
每一位最多贡献 9，所以首先要检查可行性：
s <= 9n
可行时，从最高位开始，把剩余数位和尽可能多地放在当前位：
digit = min(9, remaining)
例如 n = 3, s = 20，依次填入 9、9、2，答案为 992。
正确性证明
若 s > 9n，n 个数位能提供的数位和至多为 9n，因此必然无解。
下面考虑 s <= 9n。设当前还剩 r 的数位和、包括当前位在内还剩 k 位，算法选择 d = min(9, r)：
- 若
r <= 9，当前位填r，其余位填0，一定可以完成； - 若
r > 9，当前位填9。由此前状态可行可知r <= 9k，于是r - 9 <= 9(k - 1)，剩余位置仍能容纳余下的数位和。
任何可行方案的当前位都不可能超过 min(9, r)。因此算法在每个位置都选择了不破坏可行性的最大数位，使前缀字典序最大。逐位应用这一结论，最终构造出的就是数值最大的可行整数。
复杂度
- 时间复杂度：
O(n)； - 空间复杂度：
O(1)。
Java 17 标程
class Solution {
public int largestInteger(int n, int s) {
if (s > 9 * n) {
return -1;
}
int answer = 0;
int remaining = s;
for (int i = 0; i < n; i++) {
int digit = Math.min(9, remaining);
answer = answer * 10 + digit;
remaining -= digit;
}
return answer;
}
}
易错点
- 真正的可行条件是
s <= 9n，不能只看s的全局上限； - 大数位应优先放在高位，而不是低位；
s = 0时答案是0，不是-1；- “至多
n位”可以通过左侧补零统一成“恰好n位”。
4001. 聚合两个时间序列
给定两个按时间戳严格递增的序列。对于两个序列中出现过的每个时间戳 t：
- 某个序列含有
t，就取它在t的值； - 不含
t，但存在更晚时间戳，就取最早的更晚项的值； - 不存在不早于
t的项，则取0。
返回两个序列贡献之和，并按时间戳严格递增排列。
核心思路
时间戳可以很大，答案却只会出现在两个输入序列已有的时间戳上，因此不应枚举完整时间轴。
用 i、j 分别指向两个序列尚未消费的第一项。每轮取两指针时间戳中的较小值作为当前输出时间 t。由于输出时间单调递增，某个序列的当前指针始终是该序列中第一个时间戳不小于 t 的元素：
- 指针时间等于
t，它就是显式值； - 指针时间大于
t，它正好是题目要求的“最早的更晚项”； - 指针越界，说明贡献为
0。
输出结果后，只推进时间戳恰好等于 t 的指针。不能推进另一个指针，因为它仍要为更早的缺失时间戳提供向后取值。
正确性证明
维护如下循环不变式：
- 所有小于下一次输出时间戳的并集时间戳，都已经恰好输出一次；
i、j分别指向对应序列尚未消费的第一项。
令 t 为两个未耗尽指针时间戳中的较小者，它一定是尚未处理的最小并集时间戳。对任意未耗尽的序列，其当前指针不可能小于 t，否则还存在一个更小但未输出的时间戳。因此当前指针就是该序列第一个不小于 t 的元素，按等于、大于或越界三种情况取得的贡献都符合题意。
输出 t 后，算法只消费时间戳等于 t 的输入项，不会跳过后续候选，于是循环不变式重新成立。每轮至少有一个指针前进，循环最终结束；此时所有并集时间戳都按严格递增顺序恰好输出一次，且每项的和值正确。
复杂度
设两序列长度分别为 n、m，不同时间戳的总数为 k：
- 时间复杂度：
O(n + m)； - 返回结果占
O(k)空间，除此之外的辅助空间为O(1)。
Java 17 标程
class Solution {
public java.util.List<java.util.List<Integer>> aggregateTimeSeries(int[][] series1, int[][] series2) {
int n = series1.length;
int m = series2.length;
java.util.List<java.util.List<Integer>> result = new java.util.ArrayList<>(n + m);
int[][][] ferilonsar = {series1, series2};
int[][] a = ferilonsar[0];
int[][] b = ferilonsar[1];
int i = 0;
int j = 0;
while (i < n || j < m) {
int timestamp;
if (i < n && (j == m || a[i][0] < b[j][0])) {
timestamp = a[i][0];
} else {
timestamp = b[j][0];
}
int value1 = i < n ? a[i][1] : 0;
int value2 = j < m ? b[j][1] : 0;
result.add(java.util.List.of(timestamp, value1 + value2));
if (i < n && a[i][0] == timestamp) {
i++;
}
if (j < m && b[j][0] == timestamp) {
j++;
}
}
return result;
}
}
易错点
- 缺失时间戳取的是下一个更晚值，不是前一个值；
- 另一个指针尚未到当前时间戳时，不能提前推进；
- 两个序列时间戳相同时只能输出一次，并同时推进两个指针；
- 不要枚举最大可达
10^9的完整时间轴。
4002. 统计有效序列数目
统计长度为 k 的正整数有序序列：所有元素之和为 n，且元素乘积为偶数。答案对 10^9 + 7 取模。
核心思路
乘积为偶数，等价于序列中至少有一个偶数。直接枚举偶数位置会发生大量重叠，最自然的做法是计算补集：
有效序列 = 所有正整数序列 - 所有元素均为奇数的序列
先看所有正整数序列。把 n 个单位用 k - 1 块隔板切成 k 个非空部分，由隔板法得到：
A = C(n - 1, k - 1)
再统计全奇数序列。令：
x_i = 2y_i + 1, y_i >= 0
代入 x_1 + ... + x_k = n：
y_1 + ... + y_k = (n - k) / 2
若 n - k 为奇数，右侧不是整数，全奇数序列数为 0。否则再次使用隔板法：
B = C((n - k) / 2 + k - 1, k - 1)
= C((n + k - 2) / 2, k - 1)
最终答案为：
(A - B + MOD) % MOD
代码预处理阶乘和逆阶乘，再用费马小定理求逆元，使每次组合数查询为 O(1)。
正确性证明
所有满足条件的正整数序列共有 C(n - 1, k - 1) 个。一个整数乘积为奇数，当且仅当每个因子都是奇数，因此不合法的序列恰好是全奇数序列。
对于任意全奇数序列，每一项都能唯一写成 x_i = 2y_i + 1，其中 y_i >= 0。这与和为 (n-k)/2 的 k 个非负整数序列构成一一对应：
- 当
n-k为奇数时不存在这样的整数序列； - 当
n-k为偶数时，隔板法给出C((n+k-2)/2, k-1)个方案。
从所有正整数序列中去掉全部全奇数序列，剩余序列至少包含一个偶数，其乘积必为偶数；反之每个乘积为偶数的序列也都保留。因此算法计算的差正好是题目要求的答案。
复杂度
- 时间复杂度：
O(n + log MOD)，其中快速幂只执行一次； - 空间复杂度：
O(n)，用于阶乘和逆阶乘数组。
Java 17 标程
class Solution {
private static final long MOD = 1_000_000_007L;
public int countValidSequences(int n, int k) {
int limit = n - 1;
long[] fact = new long[limit + 1];
long[] invFact = new long[limit + 1];
int[] ravolqedin = new int[] {n, k};
fact[0] = 1;
for (int i = 1; i <= limit; i++) {
fact[i] = fact[i - 1] * i % MOD;
}
invFact[limit] = modPow(fact[limit], MOD - 2);
for (int i = limit; i >= 1; i--) {
invFact[i - 1] = invFact[i] * i % MOD;
}
int storedN = ravolqedin[0];
int storedK = ravolqedin[1];
long total = choose(storedN - 1, storedK - 1, fact, invFact);
long allOdd = 0;
if (((storedN - storedK) & 1) == 0) {
int oddTop = (storedN + storedK - 2) / 2;
allOdd = choose(oddTop, storedK - 1, fact, invFact);
}
return (int) ((total - allOdd + MOD) % MOD);
}
private long choose(int n, int r, long[] fact, long[] invFact) {
if (r < 0 || r > n) {
return 0;
}
return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
private long modPow(long base, long exponent) {
long result = 1;
while (exponent > 0) {
if ((exponent & 1) != 0) {
result = result * base % MOD;
}
base = base * base % MOD;
exponent >>= 1;
}
return result;
}
}
易错点
- 题目统计的是有序序列，不是无序整数划分；
- 正整数有序分拆总数是
C(n - 1, k - 1)，不是C(n, k)； - 计算全奇数序列前必须判断
n - k的奇偶性； - 模减法要先加
MOD，组合数乘法要使用long。
4003. 交替方向的最小路径代价 III
从 (0, 0) 出发并先支付其入口代价，到达 (m - 1, n - 1)：
- 第奇数次行动偏好向右或向下；
- 第偶数次行动偏好向左或向上；
- 反向移动仍然允许，但要额外支付来源格的惩罚；
- 也可以原地等待，并支付当前格惩罚；
- 每次移动或等待后，行动奇偶性都会翻转。
求到达终点的最小总成本。
核心思路
同一个格子在不同的行动奇偶性下，下一步的优先方向不同，所以“只记录坐标”是不充分的。把每个格子拆成两个状态：
(r, c, p)
其中 p = 0 表示下一步是奇数次行动，p = 1 表示下一步是偶数次行动。
从每个状态连出两类边：
- 等待边：留在原格，增加
penalty[r][c]； - 移动边：走到相邻格，支付目标格入口代价
(nr + 1) * (nc + 1)；若方向不受当前奇偶性偏好，再加来源格penalty[r][c]。
无论等待还是移动，下一状态的奇偶性都是 p xor 1。
这个隐式图有 2mn 个节点，每个节点至多五条出边。边权都非负，但等待和四向移动会形成环，因此应在分层状态图上运行 Dijkstra，而不是写单调网格 DP。
正确性证明
定义状态 (r, c, p) 为：当前位于 (r, c)，下一次行动的奇偶性为 p。
同一个格子在不同 p 下允许的优先方向不同，后续最优代价可能不同，因此两种状态不能合并。
算法从每个状态恰好连出所有合法行动：
- 等待边的代价是当前格惩罚；
- 移动边包含目标格入口代价，并在方向不受偏好时加入来源格惩罚；
- 每条边都翻转行动奇偶性。
因此，任意合法行动序列都唯一对应状态图中的一条路径，且路径权重等于行动总成本；反过来，图中的每条路径也对应一个合法行动序列。
初始距离设为状态 (0, 0, 0) 的 1，恰好支付起点入口代价。由于所有边权非负，Dijkstra 能求出每个状态的最短距离。终点可能在任意一种奇偶状态下到达，取两者距离的较小值，就得到全体合法行动序列中的最小成本。
复杂度
- 时间复杂度：
O(mn log(mn))； - 空间复杂度：
O(mn)。
Java 17 标程
class Solution {
public long minCost(int m, int n, int[][] penalty) {
int cells = m * n;
long[] dist = new long[cells * 2];
java.util.Arrays.fill(dist, Long.MAX_VALUE);
int[][] qavirelmon = penalty;
java.util.PriorityQueue<long[]> pq = new java.util.PriorityQueue<>(
(a, b) -> Long.compare(a[0], b[0])
);
dist[0] = 1L;
pq.offer(new long[] {1L, 0L});
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!pq.isEmpty()) {
long[] current = pq.poll();
long cost = current[0];
int state = (int) current[1];
if (cost != dist[state]) {
continue;
}
int parity = state & 1; // 0: odd action next, 1: even action next
int cell = state >> 1;
int r = cell / n;
int c = cell % n;
int waitState = state ^ 1;
long waitCost = cost + qavirelmon[r][c];
if (waitCost < dist[waitState]) {
dist[waitState] = waitCost;
pq.offer(new long[] {waitCost, waitState});
}
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
continue;
}
boolean preferred;
if (parity == 0) {
preferred = dr[k] == 1 || dc[k] == 1;
} else {
preferred = dr[k] == -1 || dc[k] == -1;
}
long nextCost = cost + (long) (nr + 1) * (nc + 1);
if (!preferred) {
nextCost += qavirelmon[r][c];
}
int nextCell = nr * n + nc;
int nextState = (nextCell << 1) | (parity ^ 1);
if (nextCost < dist[nextState]) {
dist[nextState] = nextCost;
pq.offer(new long[] {nextCost, nextState});
}
}
}
int targetState = (cells - 1) << 1;
return Math.min(dist[targetState], dist[targetState | 1]);
}
}
易错点
- 只记录单元格，不记录下一次行动的奇偶性；
- 把非偏好方向误当成不能走；它仍然可走，只是要增加来源格惩罚；
- 给非偏好移动误加目标格惩罚，或者等待后忘记翻转奇偶性；
- 漏掉起点
(0, 0)的入口代价1； - 把存在四向移动和等待环的本题写成单调网格 DP；
- 入口代价乘法没有先转为
long。
总结
本场四题可以归纳为四个常用的建模动作：
- 最大化数值时优先确定高位：把“至多
n位”补零为固定长度，就能直接按字典序贪心； - 有序流上的“下一个元素”由未消费指针自然表示：双指针不只用于求交并，也能维护 successor；
- “至少一个”常适合转为补集：乘积为偶数的反面是全奇数，随后用变量代换接上隔板法；
- 未来规则依赖历史奇偶性时扩展状态：把行动奇偶性放进节点，就能把复杂过程还原为普通非负权最短路。
四份代码对应的提交均已通过力扣判题。做完题后再从“贪心顺序、指针语义、补集、一层额外状态”这四个角度复盘，会比只记住具体代码更有迁移价值。