Leetcode[233] Number of Digit One
29 Nov 2015###Task1 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.
Hint:
Beware of overflow.
###Python
class Solution(object):
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
if n < 0:
return 0
ones, x = [0], 0
imax = (1 << 32) - 1
while 10 ** x < imax:
ones.append(ones[x] * 10 + 10 ** x)
x += 1
count, size = 0, len(str(n))
for digit in str(n):
digit = int(digit)
size -= 1
n -= digit * 10 ** size
if digit == 1:
count += ones[size] + 1 + n
elif digit > 1:
count += digit * ones[size] + 10 ** size
return count
###Java
public class Solution {
public int countDigitOne(int n) {
if (n <= 0) {
return 0;
}
int ones = 0;
for (long m = 1; m <= n; m *= 10) {
long a = n / m;
long b = n % m;
ones += (a + 8) / 10 * m;
if (a % 10 == 1) {
ones += b + 1;
}
}
return ones;
}
}
###Points 预处理数组ones，ones[x]表示[0, 10 ^ x)范围内包含的1的个数
由高位向低位依次遍历数字n的每一位digit
记digit右边（低位）数字片段为n，size为当前位数，cnt为1的总数
若digit > 1，则cnt += digit * ones[size - 1] + 10 ^ size
若digit = 1，则cnt += n + ones[size - 1] + 1
- Pattern: # of 1: < 1, # of 1 < 100, # of 1 < 1000…
- cur = prev * 10 + 10 ** digits