233. Number of Digit One - jiejackyzhang/leetcode-note GitHub Wiki

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.

解题思路为：计算每一位上出现1的次数。

if n = xyzdabc

我们考虑千位上出现1的次数，有三种情形：

(1) xyz * 1000              if d == 0
(2) xyz * 1000 + abc + 1    if d == 1
(3) xyz * 1000 + 1000       if d > 1

因此对每一位都进行计算，求和即为最后的答案。

public class Solution {
    public int countDigitOne(int n) {
        if(n <= 0) return 0;
        int num = n, scale = 1, res = 0;
        do {
            int digit = num % 10;
            num /= 10;
            res += num * scale;
            if(digit == 1) res += n % scale + 1;
            if(digit > 1) res += scale;
            scale *= 10;
        } while(num > 0);
        return res;
    }
}