题目描述
求出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，n1 个位，n2 表示十位，nx 表示最高位，那么num就可以表示为：nxnx-1nx-2...n3n2n1。
比如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的数字个数是：
$$ 高位*当前位数 = 35 *10 =350 $$
当前位是1
假设我们现在计算的是3514，当前位是1，高位是35，低位是4。除了前面说的高位从00到34，低位可以从0到9，之外。仔细观察！！！
351X
如果高位是35的时候，低位是不是可以从0-4，一共五个数。最大的数是3514，所以当前位是1的时候，当前位数出现1的个数是：
$$ 高位当前位数+低位+1 = 3510+4+1 = 355 $$
当前位>1
假设我们现在计算的是3524，当前位是2，高位是35，低位是4。我们发现，当前位是1的时候，高位可以从0到35，而低位是可以从0到9，最小是0010，最大是3519。
因此当前位大于2的时候，所有数字中出现1的个数是：
$$
（高位+1）*当前位数 = （1+35）*10 = 360
$$
每一位上出现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;
}
C++ 代码实现如下：
class Solution {
public:
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;
}
};
不得不说，找到这个规律的人真的超级牛逼！！！
- 时间复杂度 O(log n) ： 循环数字 n 的位数，相当于使用了 log(n)，时间复杂度为 O(log n)
- 空间复杂度 O(1)：