2023-05-02：如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

(资料图片)

输入：n = 20。

输出：19。

答案2023-05-02：

可以通过数字组合和状态压缩的动态规划算法来解决。具体过程如下：

1.对于给定的正整数 n，求出其位数 len。

2.枚举所有小于 len 位的数字，计算其中特殊整数的总数。如果数字为 i 位，则特殊整数个数为 9 * 8 * ... * (10 - i)。

3.对于第 len 位上的数字 x，在计算期间将其提取出来。

4.如果 x 是第一个数字，则区间 [1, n] 中，第 len 位之前的数字不受限制，因此可以选取任意一个非零数字，共有 9 种可能。

5.对于区间 [1, n] 中第 len 位之前的每个数字，考虑它们与 x 组合所能得到的所有特殊整数。如果某个数字已经在当前组合中出现过，则不能再重复使用。

6.递归求解所有满足要求的数字组合，每次处理一位，直到组合中所有数字都确定下来。

7.对于区间 [1, n] 中的每个数字，检查其是否为特殊整数，并统计个数。

8.返回特殊整数的总数。

该算法的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。由于需要进行大量的数字组合枚举和状态压缩操作，实现起来较为复杂。

const OFFSET: [i32; 11] = [    0,     // 0位数，一共能解决几个位    1,     // 1位数，一共能解决几个位    10,    // 2位数，一共能解决几个位    100,   // 3位数，一共能解决几个位    1000,  // 4位数，一共能解决几个位    10000, // 5位数，一共能解决几个位    100000, 1000000, 10000000, 100000000, 1000000000,];fn count_special_numbers(n: i32) -> i32 {    let len = len(n);    let mut ans = 0;    for i in 1..len {        ans += all(i);    }    let first_number = n / OFFSET[len as usize];    ans += (first_number - 1) * small(len - 1, 9);    ans += process(n, len, len - 1, 1 << first_number);    return ans;}// 返回n这个数字有几位fn len(mut n: i32) -> i32 {    let mut ans = 0;    while n != 0 {        ans += 1;        n /= 10;    }    return ans;}// 返回所有bits位数，有几个特殊的fn all(bits: i32) -> i32 {    let mut ans = 9;    let mut cur = 9;    for _ in 1..bits {        ans *= cur;        cur -= 1;    }    return ans;}// bits : 8 7 6 5 4位// candidates : 8 可能性// bits : _ _ _ 3位// candidates : 5 可能性fn small(bits: i32, candidates: i32) -> i32 {    let mut ans = 1;    let mut cur_candidate = candidates;    for _ in 0..bits {        ans *= cur_candidate;        cur_candidate -= 1;    }    return ans;}// num : 原始数 46531 固定// len : 原始数有几位，5位，固定// rest : 还剩几位没决定，可变参数// num : 46531//       4 _ _ _ _//       4 0~5//       4 6 _ _ _// status : 4 6 _ _ _// 哪些数字使用了，状态！在status里：// 体系学习班，状态压缩的动态规划！// int status 32位// 9 8 7 6 5 4 3 2 1 0//       1 0 1 0 0 0 0// 4 6 _ _ _ 还有几个达标的！// 哪些数字选了都在status里，用一个status变量表示数字选没选(位信息)fn process(num: i32, len: i32, rest: i32, status: i32) -> i32 {    if rest == 0 {        return 1;    }    // 46531    //   ___    //   5    // 46531 / 100 -> 465 % 10 -> 5    // 比5小的有几股？0 1 2 3 4    //    // n : 454012    //     45_    //       0...    //       1...    //       2...    //       3...    //       4 _ _ _    let cur = (num / OFFSET[rest as usize]) % 10;    let mut cnt = 0;    for i in 0..cur {        if (status & (1 << i)) == 0 {            cnt += 1;        }    }    let mut ans = cnt * small(rest - 1, 9 - (len - rest));    if (status & (1 << cur)) == 0 {        ans += process(num, len, rest - 1, status | (1 << cur));    }    return ans;}fn main() {    let n = 135;    let ans = count_special_numbers(n);    println!(        "The number of special numbers between 1 and {} is {}",        n, ans    );}

package mainimport "fmt"var offset = []int{0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,}func countSpecialNumbers(n int) int {len := len(n)ans := 0for i := 1; i < len; i++ {ans += all(i)}firstNumber := n / offset[len]ans += (firstNumber - 1) * small(len-1, 9)ans += process(n, len, len-1, 1<

#include int offset[] = {0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};int len(int n) {int ans = 0;while (n != 0) {ans++;n /= 10;}return ans;}int all(int bits) {int ans = 9;int cur = 9;while (--bits != 0) {ans *= cur--;}return ans;}int small(int bits, int candidates) {int ans = 1;for (int i = 0; i < bits; i++, candidates--) {ans *= candidates;}return ans;}int process(int num, int len, int rest, int status) {if (rest == 0) {return 1;}int cur = (num / offset[rest]) % 10;int cnt = 0;for (int i = 0; i < cur; i++) {if ((status & (1 << i)) == 0) {cnt++;}}int ans = cnt * small(rest - 1, 9 - (len - rest));if ((status & (1 << cur)) == 0) {ans += process(num, len, rest - 1, status | (1 << cur));}return ans;}int countSpecialNumbers(int n) {int len0 = len(n);int ans = 0;for (int i = 1; i < len0; i++) {ans += all(i);}int firstNumber = n / offset[len0];ans += (firstNumber - 1) * small(len0 - 1, 9);ans += process(n, len0, len0 - 1, 1 << firstNumber);return ans;}int main() {int n = 135;int ans = countSpecialNumbers(n);printf("The number of special numbers between 1 and %d is %d\n", n, ans);return 0;}

#include using namespace std;int offset[11] = {0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};int len(int n) {int ans = 0;while (n != 0) {ans++;n /= 10;}return ans;}int all(int bits) {int ans = 9;int cur = 9;while (--bits != 0) {ans *= cur--;}return ans;}int small(int bits, int candidates) {int ans = 1;for (int i = 0; i < bits; i++, candidates--) {ans *= candidates;}return ans;}int process(int num, int len, int rest, int status) {if (rest == 0) {return 1;}int cur = (num / offset[rest]) % 10;int cnt = 0;for (int i = 0; i < cur; i++) {if ((status & (1 << i)) == 0) {cnt++;}}int ans = cnt * small(rest - 1, 9 - (len - rest));if ((status & (1 << cur)) == 0) {ans += process(num, len, rest - 1, status | (1 << cur));}return ans;}int countSpecialNumbers(int n) {int len0 = len(n);int ans = 0;for (int i = 1; i < len0; i++) {ans += all(i);}int firstNumber = n / offset[len0];ans += (firstNumber - 1) * small(len0 - 1, 9);ans += process(n, len0, len0 - 1, 1 << firstNumber);return ans;}int main() {int n = 135;int ans = countSpecialNumbers(n);cout << "The number of special numbers between 1 and " << n << " is " << ans << endl;return 0;}