题目描述：

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.

题目大意：

给定一个整数n，计算所有小于等于n的非负整数中数字1出现的次数。

例如：

给定 n = 13，

返回6， 因为数字1在下面的数字中出现：1, 10, 11, 12, 13（共6次）。

解题思路：

注意题目要求为统计1出现的次数，而非包含1的数字出现的次数（一开始理解题意时出现了偏差）

在此列出两种解法：

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

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

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

记digit右边（低位）数字片段为n，size为当前位数，cnt为1的总数

若digit > 1，则cnt += digit * ones[size - 1] + 10 ^ (size - 1)

若digit = 1，则cnt += n + ones[size - 1] + 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时可能包含的数字总数

参考：https://leetcode.com/discuss/44314/accepted-c-solution-with-explanation

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

记当前位数为c，curn左边（高位）的数字片段为highn，cur右边（低位）的数字片段为lown，lowc = 10 ^ c

若curn = 0，则高位范围为0 ~ highn - 1，低位0 ~ lowc - 1

若curn = 1，则高位范围为0 ~ highn - 1，低位0 ~ lowc - 1；或者 高位为highn， 低位0 ~ lown

若curn ＞ 1，则高位范围为0 ~ highn， 低位为0 ~ lowc - 1

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;
}

下面的代码思路同前所述，更加精简

摘自：https://leetcode.com/discuss/44281/4-lines-o-log-n-c-java-python

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

 

本文链接：http://bookshadow.com/weblog/2015/07/08/leetcode-number-digit-one/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码