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)。由于需要进行大量的数字组合枚举和状态压缩操作，实现起来较为复杂。

rust完整代码如下：

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
    );
}

go完整代码如下：

package main

import "fmt"

var offset = []int{
    0,
    1,
    10,
    100,
    1000,
    10000,
    100000,
    1000000,
    10000000,
    100000000,
    1000000000,
}

func countSpecialNumbers(n int) int {
    len := len(n)
    ans := 0
    for 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<<firstNumber)
    return ans
}

func len(n int) int {
    ans := 0
    for n != 0 {
        ans++
        n /= 10
    }
    return ans
}

func all(bits int) int {
    ans := 9
    cur := 9
    for i := 1; i < bits; i++ {
        ans *= cur
        cur--
    }
    return ans
}

func small(bits int, candidates int) int {
    ans := 1
    for i := 0; i < bits; i++ {
        ans *= candidates
        candidates--
    }
    return ans
}

func process(num int, len int, rest int, status int) int {
    if rest == 0 {
        return 1
    }
    cur := (num / offset[rest]) % 10
    cnt := 0
    for i := 0; i < cur; i++ {
        if (status & (1 << i)) == 0 {
            cnt++
        }
    }
    ans := cnt * small(rest-1, 9-(len-rest))
    if (status & (1 << cur)) == 0 {
        ans += process(num, len, rest-1, status|(1<<cur))
    }
    return ans
}

func main() {
    n := 135
    ans := countSpecialNumbers(n)
    fmt.Printf("The number of special numbers between 1 and %d is %d\n", n, ans)
}

c完整代码如下：

#include <stdio.h>

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;
}

c++完整代码如下：

#include <iostream>
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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接