DeepSeek LeetCode 2376.统计特殊整数 C实现
以下是 LeetCode 2376 题「统计特殊整数」的 C 语言实现：
解法一：数位 DP（记忆化搜索）
```c
int 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)); // 输出: 19
printf("%d\n", countSpecialNumbers(5)); // 输出: 5
printf("%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. 位掩码 mask：10 位二进制记录 0-9 哪些数字已使用
2. 前导零处理：isNum 区分是否已开始填数，避免将 0 误认为已使用
3. 记忆化条件：只在 !isLimit && isNum 时缓存结果
4. 数学解法：对于大数更优，直接计算组合数和排列数
推荐使用解法三，时间复杂度和空间复杂度都最优。