LeetCode-233 Number of Digit One

题目描述

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

 

上一篇:Prime Path POJ-3126


下一篇:【leetcode 数学问题 C++】【剑指 Offer】 43. 1~n 整数中 1 出现的次数 233. Number of Digit One