剑指Offer（三十一）-- 整数中1出现的次数

• 题目描述
• 输入
• 输出
• 题解
  • 当前位是0
  • 当前位是1
  • 当前位>1

题目描述

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

输入

13

输出

6

题解

这道题如果使用暴力破解，肯定是会超时的，所以我们需要看看这里面有没有啥规律。（这规律并非我自己发现的，从别人的答案中得知，直呼牛逼）

假设现在有一个是为num,num是位数一共为x，n~1~ 个位，n~2~ 表示十位，n~x~ 表示最高位，那么num就可以表示为：n~x~n~x-1~n~x-2~...n~3~n~2~n~1~。比如3504，最高位是3，百位是5，十位是0，个位是4，拿十位来说，比十位更高的位上的数是3，5，比十位更低的位数上的数是4。

当前位是0

假设当前位上的数是0，譬如3504，那么35是高位，4是低位，当前位是十位，也就是10，1出现的可能性是哪些呢？

从001X到341X

猜想一下，前面的千位和百位的组合是不是可以从00到34，有人说为什么不到35，351X明显超出范围了！！！那后面的X是不是可以随意的0到9呢？那肯定是啊，所以前面00到34一共35个数，0到9一共10个数，这个10也就是因为当前的1在十位上。所以当前位是0的时候，该位出现1的数字个数是：

当前位是1

假设我们现在计算的是3514，当前位是1，高位是35，低位是4。除了前面说的高位从00到34，低位可以从0到9，之外。仔细观察！！！

351X

如果高位是35的时候，低位是不是可以从0-4，一共五个数。最大的数是3514，所以当前位是1的时候，当前位数出现1的个数是：

当前位>1

假设我们现在计算的是3524，当前位是2，高位是35，低位是4。我们发现，当当前位是1的时候，高位可以从0到35，而低位是可以从0到9，最小是0010，最大是3519。因此当前位大于2的时候，所有数字中出现1的个数是：

每一位上出现1的次数都依照上面的算法，就可以得出出现1的所有次数。代码如下：

    public static int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int level = 1;
        int high = n / 10;
        int low = 0;
        int cur = n % 10;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                sum = sum + high * level;
            } else if (cur == 1) {
                sum = sum + high * level + low + 1;
            } else {
                sum = sum + (high + 1) * level;
            }
            low = cur * level + low;
            level = level * 10;
            cur = high % 10;
            high = high / 10;
        }
        return sum;
    }

不得不说，找到这个规律的人真的超级牛逼！！！

【作者简介】： 秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。这个世界希望一切都很快，更快，但是我希望自己能走好每一步，写好每一篇文章，期待和你们一起交流。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~