## 题目描述：

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.

## 解题思路：

### 解法I：预处理+从高位向低位枚举1的出现次数

```预处理数组ones，ones[x]表示[0, 10 ^ x)范围内包含的1的个数

## Python代码：

``````class Solution:
# @param {integer} n
# @return {integer}
def countDigitOne(self, n):
if n < 0:
return 0
ones, x = [0], 0
while 10 ** x <= 0x7FFFFFFF:
ones.append(ones[x] * 10 + 10 ** x)
x += 1
cnt, size = 0, len(str(n))
for digit in str(n):
digit = int(digit)
size -= 1
n -= digit * 10 ** size
if digit > 1:
cnt += digit * ones[size] + 10 ** size
elif digit == 1:
cnt += n + ones[size] + 1
return cnt
``````

### 解法II：计数原理，按位统计该位为1时可能包含的数字总数

```由低位向高位依次遍历数字n的每一位curn

## C++代码：

``````int countDigitOne(int n) {
long long int res(0);
int highn(n), lowc(1), lown(0);
while(highn > 0){
int curn = highn % 10;
highn = highn / 10;
if (1 == curn) {
//higher: 0~(highn-1);  lower:  0 ~ (lowc-1)
res += highn * lowc;
//higher: highn ~ highn;     lower:0~lown
res += lown + 1;
} else if (0 == curn) {
//curn < 1
//higher: 0~(highn-1);  lower:  0 ~ (lowc-1)
res += highn * lowc;
} else {
//curn > 1
res += (highn + 1) * lowc;
}
//update lown and lowc
lown = curn * lowc + lown;
lowc = lowc * 10;
}
return res;
}
``````

## Python代码：

``````def countDigitOne(self, n):
ones, m = 0, 1
while m <= n:
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1)
m *= 10
return ones
``````

Pingbacks已关闭。