剑指Offer-31.整数中1出现的次数(从1到n整数中1出现的次数)(C++/Java)

题目：

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

分析：

可以编写一个判断一个数字有多少个1的函数，然后遍历1-n依次调用统计函数，最后求和即可，不过这样时间复杂度有些多。

我们可以按数字的位数来依次统计1出现的个数，例如21345这个数，我们先看1346-21345区间1出现的个数。

先统计万位出现1的个数，我们知道，10000-19999，万位共出现了10000次，也就是10^4个1，考虑一下特殊情况，如果是12345这样的数，实际上万位出现1的个数就等于万位后面的数字加1，也就是2345+1=2346次。

再来计算后面，也就是其余4位1出现的次数1346-21345可以拆成两部分来看，一部分是1346-11345，每一段剩下的4位数字中，选择1位是1，其余三位可以选择0-9，也就是出现了10^3次，共4位所以也就是4*10^3次，同理剩下的部分11346-21345也是4*10^3次。

而剩下的1-1345区间出现1的个数可以通过递归求得。

程序：

C++

class Solution {

public:

    int NumberOf1Between1AndN_Solution(int n)

    {

        int length = ;

        int num = n;

        while(num){

            num /= ;

            length++;

        }

        return helper(n, length);

    }

    int helper(int num, int length){

        if(length ==  || num <= )

            return ;

        int numfirst = ;

        int first = num / pow(length-);

        if(length ==  && first > )

            return ;

        if(first > ){

            numfirst = pow(length-);

        }

        if(first == ){

            numfirst = num - pow(length-) + ;

        }

        int numother = first * (length - ) * pow(length-);

        return numfirst + numother + helper(num - first*pow(length-), length-);

    }

    int pow(int num){

        int res = ;

        for(int i = ; i < num; ++i)

            res *= ;

        return res;

    }

};

Java

public class Solution {

    public int NumberOf1Between1AndN_Solution(int n) {

        if(n <= 0)

            return 0;

        int res = 0;

        while(n != 0){

            res += helper(n);

            n--;

        }

        return res;

    }

    public int helper(int n){

        int count = 0;

        while(n != 0){

            if(n % 10 == 1)

                count++;

            n /= 10;

        }

        return count;

    }

}

巴特西

剑指Offer-31.整数中1出现的次数(从1到n整数中1出现的次数)(C++/Java)

题目：

分析：

程序：

最新文章

热门文章