统计特殊整数 2376
题目
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入： n = 20
输出： 19
解释： 1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入： n = 5
输出： 5
解释： 1 到 5 所有整数都是特殊整数。
示例 3：
输入： n = 135
输出： 110
解释： 从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 10^9
分析与解答
直觉上，感觉可以分为构造和检查两种思路。看看能不能找到出现的规律。检查好像比较勉强。
检查
如果真的就是暴力检查，那么复杂度大概就是 10^10，先试试再说。利用set检查重复：
CPP
1234567891011121314151617class Solution {
public:
int countSpecialNumbers(int n) {
int res = 0;
for (unsigned long long i = 1; i <= n; i++) {
std::string str = std::to_string(i);
std::set<char> s;
for (char c : str) {
s.insert(c);
}
if (s.size() == str.size()) {
res++;
}
}
return res;
}
};
不出意料的超时了。
构造
直接排列组合还是比较抽象的。n最大是 2000000000，那么最多有10位。我们按数字位数来考虑。我们先思考最大有多少。
对于k位数，需要k个数字。第一位不为0，那么选择是。全部加起来：
CPP
12345678910111213141516class Solution {
public:
int countSpecialNumbers(int n) {
int res = 0;
for (int i = 3; i <= 9; i++) {
int t = 1;
for (int j = 2; j <= i; j++) {
t *= 11 - j;
}
res += 9 * t;
}
res += 9 + 81;
res += 1 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
return res;
}
};
最后一行是10位数的情况，因为第一位只能是1。这样计算的就是最大范围内的特殊整数个数。接下来就是考虑什么时候停止了。
如果n是k位数，那么我们可以考虑从1位数到k-1位数的特殊整数个数。可以直接计算。对于k位，第一位（这里从左到右）必须不比n大。
考虑相等和不相等。如果不相当，后面就是全排列了。如果相等，那就动态的往后考虑。
CPP
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172class Solution {
public:
int choice_left(set<char> &avail, char c) {
int res = 0;
for (char i = '0'; i < c; i++) {
if (avail.find(i) == avail.end()) {
res++;
}
}
return res;
}
int countSpecialNumbers(int n) {
if (n < 999) {
int res = 0;
for (unsigned long long i = 1; i <= n; i++) {
std::string str = std::to_string(i);
std::set<char> s;
for (char c : str) {
s.insert(c);
}
if (s.size() == str.size()) {
res++;
}
}
return res;
}
int res = 9;
int n_digit = std::to_string(n).size();
vector<int> quickq(n_digit, 0); // store n digit num of special int
vector<int> quick_left(n_digit, 0); // store left arr
quickq[0] = 1;
for (int i = 2; i <= n_digit; i++) {
quickq[i-1] = quickq[i-2] * (11 - i);
}
quick_left[n_digit-1] = 1;
for (int i = 1; i < n_digit; i++) {
quick_left[n_digit-i-1] = quick_left[n_digit-i] * (10 - n_digit + i);
}
std::string n_str = std::to_string(n);
set <char> avail;
quickq[n_digit - 1] = quick_left[0] * (choice_left(avail, n_str[0]) - 1);
avail.insert(n_str[0]);
for (int i = 1; i < n_digit; i++) {
quickq[n_digit - 1] += quick_left[i] * choice_left(avail, n_str[i]);
if (avail.find(n_str[i]) != avail.end()) {
break;
}
avail.insert(n_str[i]);
}
for (int i = 1; i < n_digit - 1; i++) {
res += 9 * quickq[i];
}
set<char> s;
for (char c : n_str) {
s.insert(c);
}
if (s.size() == n_str.size()) {
res++;
}
return res + quickq[n_digit - 1];
}
};
主要是注意检查一下n本身是不是特殊整数。两个vector都是用来避免反复求组合数的，其实实际用处不大。
题目不难，但是组合数算错检查了半天。。开始质疑我的代码能力了。