题目：输入一个整数n,从1到n这n个十进制整数中1出现的次数。
思路1：对1到n中的任意一个数i对其进行求余数来判断个位是否为1，然后再求除数，判断十位是否为1.统计出1的个数。然后对1到n用一个循环将所有的数都加起来。时间复杂度为O（nlogn）.
思路2：根据数字的规律来求。例如：21344这个数，我们将它分成两部分，第一部分为1345~21344.这部分我们可以先求出最高位上一出现的次数。又分为两种情况，10000~19999这种情况下最高位大于1，1出现的次数为10^4,另一种是10000~13456.1出现的次数为3456+1。第二部分为1~1344。采用递归完成。这种思路时间复杂度为O（logN）。
思路1：Java代码
//从1到n个整数中1出现的次数。时间复杂度为O（nlogn）
public class NumberOf1 {
public int number(int n){
int number=0;
for(int i=1;i<=n;i++){
number+=numberOf1(i);
}
return number;
} public int numberOf1(int n) {
int number=0;
while(n!=0){
if(n%10==1)
number++;
n/=10;
}
return number;
}
public static void main(String[] args){
int n=213;
NumberOf1 no1=new NumberOf1();
int number=no1.number(n);
System.out.println(number);
}
}
思路2：Java代码
//从1到n的整数中，1出现的次数。从数字规律着手提高时间效率例如数字21456
//我们可以把该数字分为两部分，一部分是1到1456，另一不部分为1457到21456.
//首先看一下最高位为1的情况，分为两种，第一种10000到19999，最高位为1的数总共有10^4个。
//第二种10000到12345，那么就是23456个了。我们接下来看一下排列组合剩下的四为数中出现1
//的次数最高位为2，剩下四位中有一位为1，其他的三位符合排列组合0到9中任选一位，总和就是2*4*10^3。
//这种思路，每次做递归的时候就去掉一位，一个数字n有logN位。因此时间复杂度为O（logN）
public class NumberOf1BetweenN {
public int numberOf1(int n){
if(n<=0)
return 0;
String number=String.valueOf(n);
char[] numbers=number.toCharArray();
return numberOf1BetweenN(numbers,0);
} public int numberOf1BetweenN(char[] numbers, int i) {
if(numbers==null||i>numbers.length||i<0)
return 0;
//处理的第一个数字
int first=numbers[i]-'0';
int firstNumber=0;
//处理的数字的位数
int len=numbers.length-i;
//当只有一位数的时候
if(len==1&&first==0)
return 0;
if(len==1&&first>0)
return 1;
if(first>1){
firstNumber=powerBase10(len-1);
}
else if(first==1)
firstNumber=autoi(numbers,i+1)+1;
//处理剩下的位数
int otherNumber=first*(len-1)*powerBase10(len-2);
//处理1到1456这部分数字
int reverseNumber=numberOf1BetweenN(numbers,i+1);
return firstNumber+otherNumber+reverseNumber;
}
//将字符串数组转换为数字
public int autoi(char[] numbers, int i) {
if(numbers==null)
return 0;
int result=0;
for(int j=i;j<numbers.length;j++){
result=result*10+numbers[j]-'0';
}
return result;
} public int powerBase10(int n) {
int result=1;
for(int j=0;j<n;j++){
result*=10;
}
return result;
}
public static void main(String[] args){
int n=213;
NumberOf1BetweenN nobn=new NumberOf1BetweenN();
int numbersOf1=nobn.numberOf1(n);
System.out.println(numbersOf1);
}
}