233. 数字 1 的个数
题目描述
输入一个整数 n。
把 0 到 n 之间（含两端）的每个整数都按十进制写出来，统计数字 1 一共出现了多少次，返回这个次数。
示例 1
输入：n = 13 输出：6
解释：数字 1 出现在 1、10、11（两次）、12、13 中，共 6 次。
示例 2
输入：n = 0 输出：0
解释：只有 0，里面没有 1。
数据范围
0 <= n <= 10^9
解题思路：逐位计数
逐位统计：对每一位（个位、十位……，位权 mul），算出 0..n 中有多少个数在这一位上是 1。把 n 拆成 high（高位部分）、cur（当前位）、low（低位部分）。高位取 0..high-1 时，低位可以任意取，共 high*mul 个；高位取 high 时要看 cur：cur=0 没有，cur=1 有 low+1 个，cur>=2 有 mul 个。把各位贡献加起来就是答案。
为什么正确
处理完位权 mul 后，count 等于 0..n 中在不超过 mul 的各位上出现的 1 的总数。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
cur=1 时高位取 high 的那一组只有 low+1 个，而不是 mul 个；另外 mul*10 在 32 位整数下会溢出，要用 64 位。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def countDigitOne(self, n: int) -> int:
count, mul = 0, 1
while mul <= n:
high, cur, low = n // (mul * 10), n // mul % 10, n % mul
if cur == 0:
count += high * mul
elif cur == 1:
count += high * mul + low + 1
else:
count += (high + 1) * mul
mul *= 10
return countclass Solution {
public int countDigitOne(int n) {
long count = 0, mul = 1;
while (mul <= n) {
long high = n / (mul * 10), cur = n / mul % 10, low = n % mul;
if (cur == 0)
count += high * mul;
else if (cur == 1)
count += high * mul + low + 1;
else
count += (high + 1) * mul;
mul *= 10;
}
return (int) count;
}
}class Solution {
public:
int countDigitOne(int n) {
long long count = 0, mul = 1;
while (mul <= n) {
long long high = n / (mul * 10), cur = n / mul % 10, low = n % mul;
if (cur == 0)
count += high * mul;
else if (cur == 1)
count += high * mul + low + 1;
else
count += (high + 1) * mul;
mul *= 10;
}
return count;
}
};func countDigitOne(n int) int {
count, mul := 0, 1
for mul <= n {
high, cur, low := n/(mul*10), n/mul%10, n%mul
if cur == 0 {
count += high * mul
} else if cur == 1 {
count += high*mul + low + 1
} else {
count += (high + 1) * mul
}
mul *= 10
}
return count
}var countDigitOne = function(n) {
let count = 0, mul = 1;
while (mul <= n) {
const high = Math.floor(n / (mul * 10)), cur = Math.floor(n / mul) % 10, low = n % mul;
if (cur === 0)
count += high * mul;
else if (cur === 1)
count += high * mul + low + 1;
else
count += (high + 1) * mul;
mul *= 10;
}
return count;
};function countDigitOne(n: number): number {
let count = 0, mul = 1;
while (mul <= n) {
const high = Math.floor(n / (mul * 10)), cur = Math.floor(n / mul) % 10, low = n % mul;
if (cur === 0)
count += high * mul;
else if (cur === 1)
count += high * mul + low + 1;
else
count += (high + 1) * mul;
mul *= 10;
}
return count;
}其他解法
逐位计数按 cur 是 0、1 还是更大分类，直接写出每一位的贡献，最快；数位动态规划不需要公式，是通用模板。
解法 2：数位动态规划 时间 O(log² n)，空间 O(log² n)
把 n 写成十进制数位，从高位到低位逐位填数。dfs(i, cnt, tight) 表示已填前 i 位、已经有 cnt 个 1、tight 表示前缀是否和 n 相同时，后面所有填法的 1 的总数。tight 为真时本位最多填 n 的这一位，否则最多填 9。不受限的状态用记忆化保存。
比逐位计数写得长，常数也更大。好处是不用推导分类公式，同一个模板能解决“统计 [0, n] 中满足某种数位条件的数”这一类题。
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n)
L = len(s)
memo = {}
def dfs(i, cnt, tight):
if i == L:
return cnt
if not tight and (i, cnt) in memo:
return memo[(i, cnt)]
up = int(s[i]) if tight else 9
res = 0
for d in range(up + 1):
res += dfs(i + 1, cnt + (d == 1), tight and d == up)
if not tight:
memo[(i, cnt)] = res
return res
return dfs(0, 0, True)class Solution {
private char[] s;
private long[][] memo;
private long dfs(int i, int cnt, boolean tight) {
if (i == s.length) return cnt;
if (!tight && memo[i][cnt] >= 0) return memo[i][cnt];
int up = tight ? s[i] - '0' : 9;
long res = 0;
for (int d = 0; d <= up; d++)
res += dfs(i + 1, cnt + (d == 1 ? 1 : 0), tight && d == up);
if (!tight) memo[i][cnt] = res;
return res;
}
public int countDigitOne(int n) {
s = String.valueOf(n).toCharArray();
memo = new long[s.length][s.length + 1];
for (long[] row : memo) Arrays.fill(row, -1);
return (int) dfs(0, 0, true);
}
}class Solution {
string s;
long long memo[12][12];
long long dfs(int i, int cnt, bool tight) {
if (i == (int)s.size()) return cnt;
if (!tight && memo[i][cnt] >= 0) return memo[i][cnt];
int up = tight ? s[i] - '0' : 9;
long long res = 0;
for (int d = 0; d <= up; d++)
res += dfs(i + 1, cnt + (d == 1), tight && d == up);
if (!tight) memo[i][cnt] = res;
return res;
}
public:
int countDigitOne(int n) {
s = to_string(n);
memset(memo, -1, sizeof(memo));
return (int)dfs(0, 0, true);
}
};func countDigitOne(n int) int {
s := strconv.Itoa(n)
L := len(s)
memo := make([][]int, L)
for i := range memo {
memo[i] = make([]int, L+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(i, cnt int, tight bool) int
dfs = func(i, cnt int, tight bool) int {
if i == L {
return cnt
}
if !tight && memo[i][cnt] >= 0 {
return memo[i][cnt]
}
up := 9
if tight {
up = int(s[i] - '0')
}
res := 0
for d := 0; d <= up; d++ {
c := cnt
if d == 1 {
c++
}
res += dfs(i+1, c, tight && d == up)
}
if !tight {
memo[i][cnt] = res
}
return res
}
return dfs(0, 0, true)
}var countDigitOne = function(n) {
const s = String(n);
const L = s.length;
const memo = Array.from({ length: L }, () => new Array(L + 1).fill(-1));
const dfs = (i, cnt, tight) => {
if (i === L) return cnt;
if (!tight && memo[i][cnt] >= 0) return memo[i][cnt];
const up = tight ? Number(s[i]) : 9;
let res = 0;
for (let d = 0; d <= up; d++)
res += dfs(i + 1, cnt + (d === 1 ? 1 : 0), tight && d === up);
if (!tight) memo[i][cnt] = res;
return res;
};
return dfs(0, 0, true);
};function countDigitOne(n: number): number {
const s = String(n);
const L = s.length;
const memo: number[][] = Array.from({ length: L }, () => new Array(L + 1).fill(-1));
const dfs = (i: number, cnt: number, tight: boolean): number => {
if (i === L) return cnt;
if (!tight && memo[i][cnt] >= 0) return memo[i][cnt];
const up = tight ? Number(s[i]) : 9;
let res = 0;
for (let d = 0; d <= up; d++)
res += dfs(i + 1, cnt + (d === 1 ? 1 : 0), tight && d === up);
if (!tight) memo[i][cnt] = res;
return res;
};
return dfs(0, 0, true);
}