题目来源
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
一道hard题，怎么感觉也做过了…
做了半天才AC，代码量不大，但是很多边边角角没有考虑好。
我是
class Solution {
public:
int countDigitOne(int n) {
if (n < 1)
return 0;
long div = 1;
long res = 0;
while (n / div) {
res += (n / (div * 10)) * div;
if (n >= div * 10) {
if (n % (div * 10) >= div)
res += min(div, n % (div * 10) - div + 1);
}
else
res += (n - div) >= div ? div : n - div + 1;
div = div * 10;
}
return res;
}
};
看了看别人的做法，有点晕，先记下
int countDigitOne(int n) {
int ones = 0;
for (long long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1);
return ones;
}
