LeetCode 题解工作台
数字 1 的个数
给定一个整数 n ，计算所有小于等于 n 的非负整数中数字 1 出现的个数。 示例 1： 输入： n = 13 输出： 6 示例 2： 输入： n = 0 输出： 0 提示： 0 9
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
这道题实际上是求在给定区间 中，数字中出现 个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。 对于区间 问题，我们一般会将其转化为 然后再减去 $[1,..l - 1]$ 的问题，即：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13 输出：6
示例 2：
输入：n = 0 输出：0
提示：
0 <= n <= 109
解题思路
方法一：数位 DP
这道题实际上是求在给定区间 中，数字中出现 个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。
对于区间 问题，我们一般会将其转化为 然后再减去 的问题，即：
不过对于本题而言，我们只需要求出区间 的值即可。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
基本步骤如下：
我们首先将数字 转化为字符串 。然后我们设计一个函数 ，其中：
- 数字 表示当前搜索到的位置，我们从高位开始搜索，即 表示最高位。
- 数字 表示当前数字中 出现的次数。
- 布尔值 表示当前是否受到上界的限制。
函数的执行过程如下：
如果 超过了数字 的长度，说明搜索结束，直接返回 。如果 为真，那么 为当前数字的第 位，否则 。接下来，我们遍历 从 到 ，对于每一个 ：
- 如果 等于 ，我们将 加一。
- 递归调用 。
答案为 。
时间复杂度 ，空间复杂度 。其中 为数字 的长度，而 。
相似题目：
class Solution:
def countDigitOne(self, n: int) -> int:
@cache
def dfs(i: int, cnt: int, limit: bool) -> int:
if i >= len(s):
return cnt
up = int(s[i]) if limit else 9
ans = 0
for j in range(up + 1):
ans += dfs(i + 1, cnt + (j == 1), limit and j == up)
return ans
s = str(n)
return dfs(0, 0, True)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(log_{10}(n)) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Checks if candidate recognizes that brute-force counting is too slow and will fail for large n.
- question_mark
Wants a solution that properly models each digit's contribution using DP or mathematical counting.
- question_mark
Looks for handling of boundary cases like n = 0 or digits with zeros in higher places.
常见陷阱
外企场景- error
Forgetting to handle the current digit correctly when it is 1, leading to undercounting.
- error
Using naive iteration through all numbers, which exceeds time limits for large n.
- error
Overflowing integer types when summing counts without considering large n.
进阶变体
外企场景- arrow_right_alt
Count digit 'd' instead of 1 across numbers up to n.
- arrow_right_alt
Compute number of times a substring appears in decimal representation of numbers up to n.
- arrow_right_alt
Adapt the solution for base-k numbers rather than decimal.