• 题目链接
• 发布于LeetCode的题解

思路

最开始尝试枚举，然后不出意外TLE了，于是开始尝试排列组合。

解题过程

1. 给定正整数 n ，设长度为 len ，从最高位到最低位的索引为 0~len-1 。

2. 例如数字 65535，第 0~4 位分别为 6、5、5、3、5。用 a[0]~a[4] 表示。

3. 我们要考虑从 1~65535 中所有的数有多少个特殊整数，可以把分成两部分

   • 1~9999

   • 10000~65535

4. 其中对于 1~9999，我们又可以分为：

   • 1~9
   • 10~99
   • 100~999
   • 1000~9999
   1. 我们可以用 sum[i] 表示 i 位数（首位不为0）总共有多少个特殊整数，那么1~9999中的所有特殊数的个数就可以表示为：$sum[1]+sum[2]+sum[3]+sum[4]$
   2. 想要求出 sum[i]，我们可以考虑从 0~9 这10个数字中选出 i 个不同的然后全排列，即 $sum[i]=A_{10}^i$

5. 对于10000~65535，我们可以分为：

   • 10000~59999
   • 60000~65535

6. 其中，10000~59999 可以分为：10000~19999，……，50000~59999

   • 这里有 a[0]-1 个这种类型的区间，其中每个区间，可以看作10个数字中已经有一个被选了（放在最高位了），然后从剩下 9 个数字中选择不同的 len-1 个出来全排列，每一块的特殊数个数为 $A_9^{len-1}$。

7. 最后是最为复杂的 60000~65535 这一部分。这里我引入两个标记——

   • 一个 flag 表示 n 的第 flag 位（0~len-1）第一次出现（从高位往低位看）重复的数字，那么前 flag 位固定后之后的计算就无效了。（举个例子，65535 的 flag=2，那么就不用再讨论 65500~65535 的所有数字了）如果 n 中不存在重复数字，我们就令 flag=len−1（循环边界）。

   • 第二个 f[11] 数组，f[i] 初始值为0，f[i]=1 表示数字 i 在 n 中出现了。我们特殊处理了 k=0 的最高位，然后从 k=1 枚举到flag位。

   • 枚举时第 k 位时，内循环 i：0~a[k]-1 这 a[k] 个数字。
     （注意这一位不能枚举到 a[k] ！！！）

     a. 如果 f[i] == 1，那么第 k 位就不能取 i 这个数字，continue；

     b. 否则，前面已经确定了 k+1 个数字，后面还剩 len-(k+1)=len-k-1 个位置待枚举，所以我们只能从 10-(k+1)=9-k 个数字中选择 len-k-1 个数字全排列

   1. 即 $C_{9-k}^{len-k-1}\ast A_{len-k-1}^{len-k-1}=\frac{(9-k)!}{(10-len)!}$

   2. 最后记得令 f[a[k]]=1。

   3. 如果 flag==len-1 ，此时有两种情况：

      1. 在最后一位出现重复；
      2. 没有重复。
      3. 所以我们特判一下：if(k==len-1 && !f[a[k]]) ans++;
      4. 因为最后一位必须枚举到 a[k]（而前面的位不能枚举到 a[k]）——思考为什么？

Tip:

可以先把简单的 0~99 部分直接输出：

if(n<=10) return n;
else if(n<=99) return n-n/11;

复杂度

• 时间复杂度: $O(1)$

• 空间复杂度: $O(1)$

Code

class Solution {
public:int countSpecialNumbers(int n) {if(n<=10) return n;else if(n<=99) return n-n/11;int fact[11];bool f[11],af[11];int len,ans=0,flag=20;memset(f,0,sizeof(f));memset(af,0,sizeof(af));memset(fact,0,sizeof(fact));vector<int> a;fact[0]=1;for(int i=1;i<=10;++i) fact[i]=i*fact[i-1];for(int i=0;n>0;i++){a.push_back(n%10);n/=10;}len=a.size();reverse(a.begin(),a.end());for(int i=0;i<len;++i){if(af[a[i]]){flag=i;break;}af[a[i]]=1;}flag=min(flag,len-1);for(int i=1;i<len;++i) ans+=9*fact[9]/fact[10-i];ans+=(a[0]-1)*fact[9]/fact[10-len];f[a[0]]=1;int k=1;while(k<=flag){for(int i=0;i<=a[k]-1;++i){if(f[i]) continue;ans+=fact[9-k]/fact[10-len];}if(k==len-1 && !f[a[k]]) ans++;f[a[k]]=1;k++;}return ans;}
};