Poison

233. Number of Digit One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int countDigitOne(int n) {
long _10k = 1; // 10^k
int res = 0;
for (int i = 0; _10k <= n; i++) { // 当前 _10k = 10^i
long leftPart = n / (_10k * 10);
res += leftPart * _10k;

long rightPart = n % (_10k * 10);
if (rightPart < _10k) {
res += 0;
} else if (rightPart < 2 * _10k) { // 注意此处不包含等于
res += rightPart - _10k + 1;
} else {
res += _10k;
}

_10k *= 10;
}

return res;
}
}
Reference

233. Number of Digit One
剑指 Offer 43. 1~n 整数中 1 出现的次数