给定一个整数n，返回从1到n的数字钟1出现的个数。
例如 n=5,1~n为1,2,3,4,5所以1出现的次数为1，返回1
n=11，1~11为1,2,3,4,5,6,7,8,9,10，11。所以1出现的次数是4，返回4
方法一：容易理解但是复杂度较高的方法，即逐一考察1~n的每个数里有多少个1.具体请参看如下代码：
public int solution1(int num){
if (num<1) {
return 0;
}
int count=0;
for (int i=1;i!=num+1 ;i++ ) {
count+=get1Nums(i);
}
return count;
}
public int get1Nums(int num){
int res=0;
while(num!=0){
if (num%10==1) {
res++;
}
num/=10;
}
return res;
}十进制的整数N有logN位(这里以10为底)所以考察一个整数含有多少个1的代价是O(logN),总的时间复杂度就是O(NlogN)
方法二：不在依次参考每一个数。而是分析1出现的规律
先看n，如果只有1位的情况，因为1~9中，1只出现1次。所以如果n只有1位时，返回1.接下来以n=114为例来介绍方法。先不看1~14之间出现了多少个1.而是先求出15~114之间一共出现多少个1.15~114之间，那些数百位上能出现1呢？100~114.所以百位上的1出现的次数为15个。15~114之间那些数十位上有1呢？110,111,112,113,114,15,16,17,18,19这些数十位上为1.一共10个。115~114之间呢，哪些数的个位上才有1，101,111,21,31,41,51,61,71,81,91。一共10个。
所以观察发现如下规律。
1.十位上固定是1的话，个位从0变到9都是可以的。
2.个位上固定是1的话，十位从0变到9都是可以的。
3.无非就是最高位取值跟着变化，使构成的数落在15~114区间上即可。
所以15~114之间的数在十位和个位上的1的数量为10+10=20=1*2*10，即（最高位的数字）*（除去最高位后剩下的位数）*（某一位固定是1的情况下，剩下的1位数都可以从0到9自由变化，所以是10的1次方）所以15~114之间1的个数可以求出，同样1~14的数字中1出现的次数可以按照上述方式求出。
再举一例。n=21345.先不看1~1345之间出现了多少个1，而是先求出1346~21345的数之间一共出现了多少次1.1346~21345那些数万位上能出现1呢？毫无疑问，10000~19999这些数万位上都有1，所以万位上的1的出现次数为10000个，与上一个例不同，上面的例子中，n的最高位是1.而这里大于1.如果想上面那样最高位的数字等于1.那么最高位上1的数量=除去最高位后剩下的数+1.而如果想本例那样最高位的数字大于1.那么最高位上的1的数量=10000=10^(k-1)（k为n位数，本例中k为5）1346~21345之间，那些数千位上有1呢？在1346~11345范围上，千位上固定式1的话，百位，十位，个位课自由从0~9变换，10^3个，在11346~21345范围上，千位上固定是1的话，百位十位个位可自由变换。所以有2*10^3个千位上是1.那些数百位上有1呢？在1346~11345范围上，百位上固定是1的话，千位，十位，个位可自由从0~9变换，10^3个。同样的，11346~21345范围上，百位上固定是1的话，千位，十位，个位可自由从0~9变换。10^3个。所以有2*10^3个百位上是1.十位和个位也是一样的情况。所以，千位，百位，十位，个位是1的总数量=2*4*10^3.这样就求出1346~21345之间1的个数。然后1~1345之间1的个数同样可以递归求出。
public int solution2(int num){
if (num<1) {
return 0;
}
int len=getLenOfNum(num);
if (len==1) {
return 1;
}
int tmp1=powerBaseOf10(len-1);
int first=num/tmp1;
int firstOneNum=first==1?num%tmp+1:tmp1;
int otherOneNum=first*(len-1)*(tmp/10);
return firstOneNum+otherOneNum+solution2(num%tmp1);
}
public int getLenOfNum(int num){
int len=0;
while(num!=0){
len++;
num/=10;
}
renturn len;
}
public int powerBaseOf10(int base){
return (int)Math.pow(10,base);
}