LeetCode 902. 最大为 N 的数字组合

Categories:

题目描述
思路分析
1. 解法一：按位计数 + 前缀枚举（推荐）
相似题目

题目描述

✅ 902. 最大为 N 的数字组合

思路分析

解法一：按位计数 + 前缀枚举（推荐）

核心思路：

先统计长度小于 len(n) 的所有数：sum = |D|^1 + ... + |D|^{len-1}。

再按位从高到低枚举：对于当前位 c，统计小于 c 的可选数字数目，乘以剩余位的组合数。

若当前位 c 在集合中，则继续处理下一位，否则终止。

若所有位都匹配，则再加 1。

复杂度分析：

时间复杂度：O(len(n) * D )，其中 |D| 为数字集合大小。

空间复杂度：O(1)。

// 按位计数 + 前缀枚举
class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String s = String.valueOf(n);
        int len = s.length();
        int m = digits.length;

        int res = 0;
        // 统计长度小于 len 的数量
        for (int i = 1; i < len; i++) {
            res += (int) Math.pow(m, i);
        }

        // 按位处理
        for (int i = 0; i < len; i++) {
            boolean match = false;
            char c = s.charAt(i);
            int smaller = 0;
            for (String d : digits) {
                if (d.charAt(0) < c) {
                    smaller++;
                } else if (d.charAt(0) == c) {
                    match = true;
                }
            }
            res += smaller * Math.pow(m, len - i - 1);
            if (!match) {
                return res;
            }
        }

        return res + 1;
    }
}

// 按位计数 + 前缀枚举
func atMostNGivenDigitSet(digits []string, n int) int {
	s := fmt.Sprintf("%d", n)
	length := len(s)
	m := len(digits)

	pow := func(a, b int) int {
		res := 1
		for i := 0; i < b; i++ {
			res *= a
		}
		return res
	}

	res := 0
	for i := 1; i < length; i++ {
		res += pow(m, i)
	}

	for i := 0; i < length; i++ {
		c := s[i]
		smaller := 0
		match := false
		for _, d := range digits {
			if d[0] < c {
				smaller++
			} else if d[0] == c {
				match = true
			}
		}
		res += smaller * pow(m, length-i-1)
		if !match {
			return res
		}
	}

	return res + 1
}

相似题目

题目	难度	考察点
233. 数字 1 的个数	困难	数位统计
357. 统计各位数字都不同的数字个数	中等	数位 DP
600. 不含连续 1 的非负整数	困难	数位 DP
1012. 至少有 1 位重复的数字	困难	数位 DP
400. 第 N 位数字	中等	数位统计
788. 旋转数字	中等	数位 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/18503187