Kimi LeetCode 3533. 判断连接可整除性 C语言实现
这是 LeetCode 3533「判断连接可整除性」的 C 语言实现。题目要求找到字典序最小的排列，使得按顺序连接后的数能被 `k` 整除。
解题思路
本题使用状态压缩动态规划（Bitmask DP）：
1. 预处理：先对 `nums` 排序，保证从小到大枚举，从而确保字典序最小。计算每个数的位数 `len[i]`，以及 `pow10[i] = 10^len[i] % k`
2. 状态定义：`dp[mask][mod]` 表示使用状态 `mask` 中的数（已选的数），当前余数为 `mod`，是否能形成合法连接
3. 状态转移：`newMod = (mod * pow10[i] + nums[i]) % k`
4. 路径重建：在 DP 后，按字典序从小到大尝试每个未使用的数，如果该路径能到达合法解，则选取该数
时间复杂度：O(n \cdot 2^n \cdot k)，空间复杂度：O(2^n \cdot k)
C 语言代码
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// 计算数字的位数
int numLen(int x) {
int len = 0;
while (x > 0) {
len++;
x /= 10;
}
return len;
}
// 快速幂: (base^exp) % mod
int modPow(int base, int exp, int mod) {
long long result = 1;
long long b = base % mod;
while (exp > 0) {
if (exp & 1) {
result = (result * b) % mod;
}
b = (b * b) % mod;
exp >>= 1;
}
return (int)result;
}
// 动态规划求解是否存在可行解
// dp[mask][mod]: -1=未计算, 0=false, 1=true
int solve(int *nums, int n, int k, int *pow10, int **dp, int mask, int mod) {
if (mask == (1 << n) - 1) {
return mod == 0 ? 1 : 0;
}
if (dp[mask][mod] != -1) {
return dp[mask][mod];
}
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) {
int newMod = (int)((1LL * mod * pow10[i] + nums[i]) % k);
if (solve(nums, n, k, pow10, dp, mask | (1 << i), newMod)) {
dp[mask][mod] = 1;
return 1;
}
}
}
dp[mask][mod] = 0;
return 0;
}
// 重建答案路径
void reconstruct(int *nums, int n, int k, int *pow10, int **dp,
int mask, int mod, int *res, int *idx) {
if (mask == (1 << n) - 1) {
return;
}
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) {
int newMod = (int)((1LL * mod * pow10[i] + nums[i]) % k);
if (solve(nums, n, k, pow10, dp, mask | (1 << i), newMod)) {
res[(*idx)++] = nums[i];
reconstruct(nums, n, k, pow10, dp, mask | (1 << i), newMod, res, idx);
return;
}
}
}
}
int* concatenatedDivisibility(int* nums, int numsSize, int k, int* returnSize) {
int n = numsSize;
// 排序，保证字典序最小
qsort(nums, n, sizeof(int), cmp);
// 预处理：计算每个数的位数和 10^len % k
int *pow10 = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
int len = numLen(nums[i]);
pow10[i] = modPow(10, len, k);
}
// 初始化dp数组: dp[mask][mod]
int totalMask = 1 << n;
int **dp = (int**)malloc(totalMask * sizeof(int*));
for (int i = 0; i < totalMask; i++) {
dp[i] = (int*)malloc(k * sizeof(int));
for (int j = 0; j < k; j++) {
dp[i][j] = -1; // -1 表示未计算
}
}
// 检查是否存在解
int hasSolution = solve(nums, n, k, pow10, dp, 0, 0);
int *res = NULL;
if (hasSolution) {
res = (int*)malloc(n * sizeof(int));
int idx = 0;
reconstruct(nums, n, k, pow10, dp, 0, 0, res, &idx);
*returnSize = n;
} else {
res = (int*)malloc(sizeof(int));
*returnSize = 0;
}
// 释放内存
for (int i = 0; i < totalMask; i++) {
free(dp[i]);
}
free(dp);
free(pow10);
return res;
}
```
关键说明
要点 说明
排序 `qsort` 确保从小到大尝试，保证字典序最小
状态压缩 `mask` 范围 [0, 2^{13})，用位运算表示选了哪些数
取模运算 连接两个数时：`newMod = (oldMod * 10^len + num) % k`
记忆化 `dp[mask][mod]` 避免重复计算，-1/0/1 分别表示未计算/不可行/可行
路径重建 第二次遍历时按相同顺序选择第一个可行的数，保证字典序
示例验证
- `nums = [3,12,45], k = 5` → 输出 `[3,12,45]`（31245 % 5 = 0）
- `nums = [10,5], k = 10` → 输出 `[5,10]`（510 % 10 = 0）
- `nums = [1,2,3], k = 5` → 输出 `[]`（无解）