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

以下是 LeetCode 3533 判断连接可整除性 的 Java 实现。思路概述- n ≤ 13使用状压 DPBitmask 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)完整代码javaclass Solution {public int[] concatenatedDivisibility(int[] nums, int k) {final int n nums.length;// 先排序保证字典序最小Arrays.sort(nums);// 每个数字的位数int[] lengths new int[n];// 10^lengths[i] % kint[] 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;}// 所有数字都用完了检查余数是否为0if (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]) % kint 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] 拼到当前数右边。