统计各位数字都不同的数字个数 图解题解

这道题到底在问什么

输入

n = 2

输出

91

输入

n = 3

输出

739

最优解：一步一步想明白

1. 3记住口诀:按位数分组,每组用乘法原理数个数,首位 9 种、之后每位少一个,逐组累加。下面每帧都在套它。
2. 4先搭一张表:每一行是一个「位数组」,列出首位选法、其余位选法、本组个数,最后累加成答案。我们一行行把它填满。
3. 5从最简单的 1 位数开始。0 到 9 这 10 个数,每个都只有一位数字,谈不上重复,所以全部都算。
4. 6一位数没有前导零的顾虑,这一位 0 到 9 都能填,所以首位选法填 10。
5. 7一位数后面没有别的位置,其余位这一格就写「无」,跳过它。
6. 8把首位的 10 种选法乘起来,后面没有别的位,本组个数就是 10。
7. 9累计答案从 0 起步,加上这一组的 10 个,现在累计是 10。第一行填完了。
8. 10进入两位数。关键来了:两位数的首位不能是 0,否则像 05 其实就是一位数,所以首位的选法要受限。
9. 11首位从 1 到 9 里挑,9 种选法,填 9。这就是「首位不能为 0」带来的限制。
10. 12到个位时,0 到 9 一共 10 个数字,首位已经用掉 1 个,剩下 9 个可选。注意这里个位反而可以是 0。
11. 13首位 9 种、个位 9 种,乘起来 9 乘 9 等于 81,两位数里各位不同的有 81 个。
12. 14把上一行累计的 10,加上这一组的 81,累计变成 91。这正好对上 n = 2 的答案。
13. 15进入三位数。规律和两位数一样,只是多了一位,可用的数字会再少一个。
14. 16三位数的首位同样不能是 0,1 到 9 共 9 种,填 9。
15. 17十位可填的还剩 9 个,个位又被前两位用掉两个、只剩 8 个,9 乘 8 等于 72。每多占一位,选择就少一个。
16. 18首位 9 种,乘上其余两位的 72 种,得到 648,三位数里各位不同的有 648 个。
17. 19上一行累计 91,加上这一组的 648,累计来到 739。整张表填满了。
18. 20看累计答案这一列:10、91、739。n 是几,就读到第几行的累计。n = 3 的答案就是 739。
19. 21回头看本质:首位永远是 9 种,从第二位开始,每填一位可用的数字就少一个,9、8、7 这样递减。这就是代码里那个不断乘以「越来越小的数」的来历。
20. 22顺手验证一下:如果问的是 n = 2,就读到第二行的累计 91,和题目示例完全一致。这张表一次算好,各种 n 都能查。
21. 23只有一个特例要单独记:n = 0 时范围是 0 到 1 之间,只剩数字 0 本身一个,答案直接是 1,不走上面的分组流程。
22. 24整体回放一遍:1 位数 10 个,加 2 位数 81 个到 91,再加 3 位数 648 个到 739。按位数分组、乘法原理算个数、逐组累加,这就是全部思路。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        @cache
        def dfs(i: int, mask: int, lead: bool) -> int:
            if i < 0:
                return 1
            ans = 0
            for j in range(10):
                if mask >> j & 1:
                    continue
                if lead and j == 0:
                    ans += dfs(i - 1, mask, True)
                else:
                    ans += dfs(i - 1, mask | 1 << j, False)
            return ans

        return dfs(n - 1, 0, True)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int f[n + 1][1 << 10];
        memset(f, -1, sizeof(f));
        function<int(int, int, bool)> dfs = [&]( int i, int mask, bool lead ) -> int {
            if (i < 0) {
                return 1;
            }
            if (!lead && f[i][mask] != -1) {
                return f[i][mask];
            }
            int ans = 0;
            for (int j = 0; j <= 9; ++j) {
                if (mask >> j & 1) {
                    continue;
                }
                if (lead && j == 0) {
                    ans += dfs(i - 1, mask, true);
                } else {
                    ans += dfs(i - 1, mask | (1 << j), false);
                }
            }
            if (!lead) {
                f[i][mask] = ans;
            }
            return ans;
        };
        return dfs(n - 1, 0, true);
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Integer[][] f;

    public int countNumbersWithUniqueDigits(int n) {
        f = new Integer[n][1 << 10];
        return dfs(n - 1, 0, true);
    }

    private int dfs(int i, int mask, boolean lead) {
        if (i < 0) {
            return 1;
        }
        if (!lead && f[i][mask] != null) {
            return f[i][mask];
        }
        int ans = 0;
        for (int j = 0; j <= 9; ++j) {
            if ((mask >> j & 1) == 1) {
                continue;
            }
            if (lead && j == 0) {
                ans += dfs(i - 1, mask, true);
            } else {
                ans += dfs(i - 1, mask | 1 << j, false);
            }
        }
        if (!lead) {
            f[i][mask] = ans;
        }
        return ans;
    }
}

复杂度

面试官可能追问