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

0 到 10 的 n 次方里,哪些数各位不重复

给一个整数 n(0 ≤ n ≤ 8),数一数在 0 ≤ x < 10 的 n 次方这个范围里,有多少个数各位数字互不相同。比如 121 里有两个 1,不算;120 三位全不同,算。题面给的例子 n = 2 答案 91,n = 3 答案 739。要的是满足条件的个数,不是把它们一个个列出来。

为什么把 0 到 10 的 n 次方逐个查会跑不动

最直接的想法是把范围里每个数都取出来,拆成各位数字逐个查有没有重复。可是 n = 8 时上界是一亿,一个个查要上亿次判断,n 再大范围还成十倍地涨,这条路撑不住。同样位数的数,判重复的规律一样——按位数分组,每组个数一个乘法式子就出来,不必逐个枚举。

按位数分组:每组的个数怎么用乘法数出来

把答案按位数拆开:1 位数一组、2 位数一组、3 位数一组,一直到 n 位数,各组个数加起来就是总数。每一组的个数不用一个个数,用乘法原理(每一位的选法数相乘)算。以两位数为例:首位有几种填法乘上个位有几种填法,就是这一组各位不同的数的个数。要点是逐位算清每一位还剩几个数字能填。

首位为什么是 9 种、后面每位为什么递减

两位及以上时,首位不能填 0——填了 0 像 05 其实就缩成一位数了,所以首位只能从 1 到 9 里挑,9 种。轮到第二位,0 到 9 一共 10 个数字,首位已经占掉 1 个,还剩 9 个可选(注意第二位反而能填 0);再往后每多占一位,可选的数字就再少一个,于是是 9、8、7 这样往下递减。把这一组每一位的选法数乘起来就是本组个数,再把各组个数累加,读到第 n 组的累计就是答案。这就是代码里那串不断乘以「越来越小的数」的来历。

拿 n = 3 亲手把这张表填到 739

1 位数:0 到 9 都能填,10 个,累计 10。2 位数:首位 9 种、个位剩 9 种,9 乘 9 等于 81,累计 10 加 81 等于 91,正好对上 n = 2 的答案。3 位数:首位 9 种、十位剩 9 种、个位再少一个剩 8 种,9 乘 9 乘 8 等于 648,累计 91 加 648 等于 739。读到第 3 组的累计 739,就是 n = 3 的答案。

n = 0 为什么单返 1、首位为 0 为什么会重复计数

按位数循环 n 次、每次一次乘法,时间 O(n);只需累计值和当前可选数两个变量,空间 O(1)。两个边界最容易错。一是 n = 0:范围是 0 ≤ x < 1,只含数字 0 一个,直接返回 1,套不进上面的分组公式。二是首位填 0:2 位及以上时首位只能 1 到 9,允许 0 会让位数缩水、和更短的数重复计数。还有一点,答案是各组之和而不是最后一组——小于 10 的 n 次方包含所有更短位数的数,都要算进去。

Python

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)

C++

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

Java

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