DeepSeek LeetCode 2376.统计特殊整数 C实现

以下是 LeetCode 2376 题「统计特殊整数」的 C 语言实现解法一数位 DP记忆化搜索cint dfs(int pos, int mask, int isLimit, int isNum, char* digits, int m, int*** memo) {if (pos m) {return isNum ? 1 : 0;}// 只有非限制且已开始填数时才使用记忆化if (!isLimit isNum memo[pos][mask] ! NULL) {return *memo[pos][mask];}int res 0;// 跳过当前位继续前导零if (!isNum) {res dfs(pos 1, mask, 0, 0, digits, m, memo);}int upper isLimit ? (digits[pos] - 0) : 9;int start isNum ? 0 : 1;for (int d start; d upper; d) {if (!((mask d) 1)) { // 数字 d 未使用res dfs(pos 1, mask | (1 d),isLimit (d upper), 1, digits, m, memo);}}// 记忆化存储if (!isLimit isNum) {if (memo[pos][mask] NULL) {memo[pos][mask] (int*)malloc(sizeof(int));}*memo[pos][mask] res;}return res;}int countSpecialNumbers(int n) {// 将 n 转换为字符串char str[12];sprintf(str, %d, n);int m strlen(str);char* digits str;// 创建 memo 数组memo[pos][mask]int*** memo (int***)malloc(m * sizeof(int**));for (int i 0; i m; i) {memo[i] (int**)malloc((1 10) * sizeof(int*));for (int j 0; j (1 10); j) {memo[i][j] NULL;}}int result dfs(0, 0, 1, 0, digits, m, memo);// 释放内存for (int i 0; i m; i) {for (int j 0; j (1 10); j) {if (memo[i][j] ! NULL) {free(memo[i][j]);}}free(memo[i]);}free(memo);return result;}解法二简化版使用数组缓存c#define MAX_POS 12#define MAX_MASK (1 10)int memo[MAX_POS][MAX_MASK];char digits[MAX_POS];int m;int dfs(int pos, int mask, int isLimit, int isNum) {if (pos m) {return isNum ? 1 : 0;}if (!isLimit isNum memo[pos][mask] ! -1) {return memo[pos][mask];}int res 0;if (!isNum) {res dfs(pos 1, mask, 0, 0);}int upper isLimit ? (digits[pos] - 0) : 9;int start isNum ? 0 : 1;for (int d start; d upper; d) {if (!((mask d) 1)) {res dfs(pos 1, mask | (1 d), isLimit (d upper), 1);}}if (!isLimit isNum) {memo[pos][mask] res;}return res;}int countSpecialNumbers(int n) {sprintf(digits, %d, n);m strlen(digits);// 初始化 memo 数组for (int i 0; i MAX_POS; i) {for (int j 0; j MAX_MASK; j) {memo[i][j] -1;}}return dfs(0, 0, 1, 0);}解法三数学组合数解法效率更高c// 计算组合数 C(n, k)int combination(int n, int k) {if (k 0 || k n) return 0;long long res 1;for (int i 1; i k; i) {res res * (n - k i) / i;}return (int)res;}// 计算排列数 P(n, k) n!/(n-k)!int permutation(int n, int k) {if (k 0 || k n) return 0;int res 1;for (int i 0; i k; i) {res * (n - i);}return res;}int countSpecialNumbers(int n) {if (n 10) return n;char str[12];sprintf(str, %d, n);int len strlen(str);int total 0;// 1. 统计所有位数小于 len 的特殊整数for (int i 1; i len; i) {// 首位不能为0有 9 种选择1-9// 剩下 i-1 位从 0-9 中选 i-1 个不同数字除去首位的数字total 9 * permutation(9, i - 1);}// 2. 统计位数等于 len 的特殊整数int used[10] {0};for (int i 0; i len; i) {int digit str[i] - 0;int start (i 0) ? 1 : 0;// 尝试放置比当前位小的数字for (int d start; d digit; d) {if (!used[d]) {// 剩余位置可以任意排列未被使用的数字int remaining 10 - (i 1); // 剩余可用数字个数int positions len - i - 1; // 剩余位置数if (positions remaining) {total permutation(remaining, positions);}}}// 如果当前数字已经被使用无法继续if (used[digit]) {break;}used[digit] 1;// 如果遍历到最后一位说明 n 本身就是特殊整数if (i len - 1) {total;}}return total;}测试代码c#include stdio.h#include string.h#include stdlib.h// 这里放上面的函数实现...int main() {// 测试用例printf(%d\n, countSpecialNumbers(20)); // 输出: 19printf(%d\n, countSpecialNumbers(5)); // 输出: 5printf(%d\n, countSpecialNumbers(100)); // 输出: (1-99有90个特殊数 100本身不是)printf(%d\n, countSpecialNumbers(135)); // 测试其他值return 0;}复杂度分析· 解法一/二时间复杂度 O(len × 2^10 × 10)空间复杂度 O(len × 2^10)· 解法三时间复杂度 O(len × 10)空间复杂度 O(1)效率最高关键点说明1. 位掩码 mask10 位二进制记录 0-9 哪些数字已使用2. 前导零处理isNum 区分是否已开始填数避免将 0 误认为已使用3. 记忆化条件只在 !isLimit isNum 时缓存结果4. 数学解法对于大数更优直接计算组合数和排列数推荐使用解法三时间复杂度和空间复杂度都最优。