Kimi LeetCode 3533. 判断连接可整除性 C语言实现

这是 LeetCode 3533「判断连接可整除性」的 C 语言实现。题目要求找到字典序最小的排列使得按顺序连接后的数能被 k 整除。解题思路本题使用状态压缩动态规划Bitmask DP1. 预处理先对 nums 排序保证从小到大枚举从而确保字典序最小。计算每个数的位数 len[i]以及 pow10[i] 10^len[i] % k2. 状态定义dp[mask][mod] 表示使用状态 mask 中的数已选的数当前余数为 mod是否能形成合法连接3. 状态转移newMod (mod * pow10[i] nums[i]) % k4. 路径重建在 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) % modint 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未计算, 0false, 1trueint 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 % kint *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 → 输出 []无解