LeetCode 2376. 统计特殊整数

◎

本节目标

用数位状态和已用数字掩码统计无重复数字的正整数。

题意与约束

统计 1 到 n 中各位数字互不相同的正整数数量。

第一反应与重复子问题

对每个数字逐位判断会重复处理相同前缀；未开始的前导零又不能占用数字 0。

状态定义与转移推导

DFS 状态为位置、tight、started 和已用数字 mask。开始前选零保持未开始；开始后只能选择未在掩码中的数字。

正确性依据

每个正整数的标准十进制写法在第一次非零位开始，后续每位唯一写入掩码，因此所有合法整数被恰好计数一次。

样例执行过程

n=100 时一位数 9 个、两位无重复数 81 个，100 重复零不计，结果 90。

代码实现

C++

C++17

#include <cstring>
#include <functional>
#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int countSpecialNumbers(int n) {
        string digits = to_string(n);
        int memo[10][2][1 << 10];
        memset(memo, -1, sizeof memo);
        function<int(int, bool, bool, int)> dfs = [&](int position, bool tight, bool started, int mask) -> int {
            if (position == static_cast<int>(digits.size())) {
                return started;
            }
            int& cached = memo[position][started][mask];
            if (!tight && cached != -1) {
                return cached;
            }
            int result = 0;
            int upper = tight ? digits[position] - '0' : 9;
            for (int digit = 0; digit <= upper; digit++) {
                if (!started && digit == 0) {
                    result += dfs(position + 1, tight && digit == upper, false, mask);
                } else if (!(mask & (1 << digit))) {
                    result += dfs(position + 1, tight && digit == upper, true, mask | (1 << digit));
                }
            }
            if (!tight) {
                cached = result;
            }
            return result;
        };
        return dfs(0, true, false, 0);
    }
};

Python

Python 3

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        digits = str(n)
        memo = {}

        def dfs(position, tight, started, mask):
            if position == len(digits):
                return int(started)
            if not tight and (position, started, mask) in memo:
                return memo[position, started, mask]
            upper = int(digits[position]) if tight else 9
            result = 0
            for digit in range(upper + 1):
                if not started and digit == 0:
                    result += dfs(position + 1, tight and digit == upper, False, mask)
                elif not mask >> digit & 1:
                    result += dfs(position + 1, tight and digit == upper, True, mask | (1 << digit))
            if not tight:
                memo[position, started, mask] = result
            return result

        return dfs(0, True, False, 0)

复杂度分析

状态数约为位数乘 2×2×2^10，对 32 位范围很小。

边界与易错点

前导零不能加入 mask，否则所有短数都会错误占用零；递归结束时只统计已经开始的数。

模式迁移

数位限制来自已出现集合时使用掩码；本题不需要、也不扩展到数位自动机。回到数位动态规划。