题目描述

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

 

题目大意

计算[0, n]之间的数字中包含多少1 。

 

示例

E1

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

 

解题思路

根据LeetCode@StefanPochmann的算法，分别在个位、十位、百位、。。。、上将数字分割为两部分，并假设该位置上的数字为1，并在该假设下计算共有多少种可能性，从低位到高位依次计算并相加可得到最终结果。

举例来说，当 n = 3141592时，假设m = 100，即百位为1，此时将n分为两部分，‘3141’和‘92’，在百位为1时，前边共有0 - 3141共3142种可能性，同时之后共有100种可能性（为什么不是92？因为该百位本来为5，即当百位设置为1时仍未超过其位置最大值，因此百位之后的位数数字可以随意）。

但当设置千位为1时，即m = 1000时，最后的数字就不能简单乘1000了，因为n的千位本来就为1 。因此需要计算0 - 313的次数，再加上592即可。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

 

代码

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        for(long long m = 1; m <= n; m *= 10) {
            // a为该位数之前的数字，b为该位数之后的数字
            long long a = n / m, b = n % m;
            // (a + 8)是为了避免判断当前位数是否为1，并加减1的操作
            res += ((a + 8) / 10) * m + (a % 10 == 1) * (b + 1);
        }
        
        return res;
    }
};