从1到n整数中1出现的个数

今天在牛客网上做剑指offer上的题，看到剑指offer上的解法确实没不太好理解。这里把看到的一种比较容易理解的方法记录下来，便于整理思路：

原博客解释的非常清楚，在这里。

这道题是要求1-n，这里总共出现了多少次1。

比如输入为12，则包含1的数字有1,10,11,12总共出现了五次。

那我们就从这个例子开始吧（本文会按照原文的记号来说明）：

round=n/10,weight=n%10

首先我们来看个位：

12

如果只有2的话，出现了一次，记录一下count=0+1=1；

12

再到十位，十位为1，个位数字变化的只有0,1,2再加上本身的1位1，总共4次。那么总共会出现的次数为count=count+4=5

这个例子比较简单，也不能说明什么规律，再看一个例子：

678

首先是个位，

678，round=67（代表高位可以从0~9变化67次）,base=1(代表当前在个位),weight=8（代表当前位的权重），count=0

那么这时的高位可以循环67次，代表可以有67次个位数1的数字，加上个位数自己的一次总共为count=67+1=68次。

678，round=6,base=10(十位),weight=7，count=68

此时，高位可以循环的有6*10=60次，7大于1，十位数为1的也可以完全出现，所以count=count+6*10+10=138次

678，round=0,base=100(百位),weight=6，count=68

此时已经没有比百位更高的位了，但是6是大于1的，所以可以出现1*100次完整的百位1，所以共计count=count+100=238次。

结束。

需要注意的是，出现多少次1和当期的weight是相关联的，若当前为weight=0，则不贡献任何1，即为前面的count。若当前为1，如17，则可以贡献个位数个数为former（7）+1次，若大于1的话，意味着可以贡献weight*base+base（当前weight位取1）个。

所以分为三种情况：

当前weight=0：count=round*base

当前weight=1：count=roung*base+former+1

当前weight>1：count=round*base+base

public int NumberOf1Between1AndN_Solution(int n) {
			int count =0;
			int base=1;
			int round=n;
			while(round>0){
				int weight=round%10;
				round/=10;
				count+=round*base;//公共部分
				if(weight==1)
					count+=(n%base)+1;
				else if(weight>1)
					count+=base;
				base*=10;
			}
	    	return count;
    }