Kimi LeetCode 3533. 判断连接可整除性 Java实现

以下是 LeetCode 3533 判断连接可整除性 的 Java 实现。

思路概述

- `n ≤ 13`，使用状压 DP（Bitmask DP）。
- 先对 `nums` 排序，这样 DP 过程中按顺序枚举下一个数字时，找到的第一个合法解就是字典序最小的。
- `dp[mask][mod]`：使用了 `mask` 中的数字，当前余数为 `mod`，是否能形成合法连接。
- 转移：枚举下一个数字 `i`，新的余数 = `(mod * 10^len(nums[i]) + nums[i]) % k`。
- 预处理：`pows[i] = 10^len(nums[i]) % k`。

复杂度

- 时间：`O(n! · n)` 最坏情况，但状压 DP 优化为 `O(2^n · n · k)`，约为 `13 · 8192 · 100 ≈ 10^6`。
- 空间：`O(2^n · k)`

完整代码

```java
class Solution {
public int[] concatenatedDivisibility(int[] nums, int k) {
final int n = nums.length;

// 先排序，保证字典序最小
Arrays.sort(nums);

// 每个数字的位数
int[] lengths = new int[n];
// 10^lengths[i] % k
int[] pows = new int[n];

for (int i = 0; i < n; ++i) {
lengths[i] = String.valueOf(nums[i]).length();
pows[i] = (int) Math.pow(10, lengths[i]) % k;
// 更安全的写法：手动计算模幂避免浮点精度问题
int p = 1;
for (int j = 0; j < lengths[i]; ++j) {
p = (p * 10) % k;
}
pows[i] = p;
}

// mem[mask][mod] = null 未计算, 0 不可行, 1 可行
Integer[][] mem = new Integer[1 << n][k];

// 先判断是否存在解
if (!dp(nums, pows, mem, k, 0, 0)) {
return new int[0];
}

// 重构答案
return reconstruct(nums, pows, mem, k, 0, 0);
}

// 判断是否存在合法方案
private boolean dp(int[] nums, int[] pows, Integer[][] mem, int k, int mask, int mod) {
if (mem[mask][mod] != null) {
return mem[mask][mod] == 1;
}

// 所有数字都用完了，检查余数是否为0
if (mask == (1 << nums.length) - 1) {
mem[mask][mod] = (mod == 0 ? 1 : 0);
return mem[mask][mod] == 1;
}

for (int i = 0; i < nums.length; ++i) {
// i 还没被使用
if ((mask >> i & 1) == 0) {
// 新的余数 = (当前余数 * 10^len + nums[i]) % k
int newMod = (mod * pows[i] + nums[i]) % k;
if (dp(nums, pows, mem, k, mask | (1 << i), newMod)) {
mem[mask][mod] = 1;
return true;
}
}
}

mem[mask][mod] = 0;
return false;
}

// 重构字典序最小的合法排列
private int[] reconstruct(int[] nums, int[] pows, Integer[][] mem, int k, int mask, int mod) {
for (int i = 0; i < nums.length; ++i) {
if ((mask >> i & 1) == 0) {
int newMod = (mod * pows[i] + nums[i]) % k;
if (dp(nums, pows, mem, k, mask | (1 << i), newMod)) {
int[] first = new int[] {nums[i]};
int[] rest = reconstruct(nums, pows, mem, k, mask | (1 << i), newMod);
int[] res = new int[first.length + rest.length];
System.arraycopy(first, 0, res, 0, first.length);
System.arraycopy(rest, 0, res, first.length, rest.length);
return res;
}
}
}
return new int[0];
}
}
```

关键点说明

1. 先排序：`Arrays.sort(nums)` 是关键。因为 `dp` 和 `reconstruct` 都按排序后的顺序枚举 `i`，所以找到的第一个可行解就是字典序最小的。
2. 模幂预处理：`pows[i] = 10^len(nums[i]) % k`，用于拼接时的余数转移。注意用循环计算避免 `Math.pow` 的浮点精度问题。
3. 记忆化数组：`Integer[][]` 用 `null` 表示未计算，`0/1` 表示不可行/可行。也可以用 `int[][]` 配合 `-1/0/1`。
4. 余数转移公式：`newMod = (mod * pows[i] + nums[i]) % k`，等价于把 `nums[i]` 拼到当前数右边。