剑指offer:从1到n整数中1出现的次数（java）

题目：输入一个整数n，求从1到n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11，和12，1一共出现了5次。

不考虑时间效率的解法，靠它想拿offer有点难

    如果在面试的时候碰到这个问题，应聘者大多能想到最直观的方法，也就是累加1到n中每个整数1出现的次数。我们可疑每次通过对10求余数判断整数的个位数字是不是1.如果这个数字大于10，除以10之后再判断个位数字是不是1.

public int numberOf1BetweenAndN(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 = n/10;
}
return number;
}

   如果希望不用计算每个数字的1的个数，那就只能寻找1在数字中出现的规律了。为了找到规律，我们不妨用一个稍微大一点的数字比如21345作为例子来分析。我们把从1到21345的所有数字分为两段，一段是从1到1345，另一段是从1346到21345.划分的原因是便于利用递归的思路，因为21345去掉最高位就是1345.我们先看1346到21345中1出现的次数。1的出现分为两种情况：1出现在最高位和1出现在其他位。1346到21345，1出现在10000-19999这10000个数字的最高位中，一共出现了10000个，即10^最高位。我们可以发现一般情况：如果是1346到11345，1出现在10000-11345的最高位中，一共出现2346次，也就是除去最高数字之后剩下的数字+1，当万位大于1时，1出现在最高位的次数是10^最高位。

    接下来分析1出现在除最高位之外的其他四位数中的情况。1346-21345这20000个数字中后4位出现的次数，分成两段，1346-11345和11346-21345，每一段剩下的4位数字中，选择其中一位是1，其余三位可以在0-9这10个数字中任意选择，根据排列组合原则，总共出现次数2*4*10^3=8000次。我们可以发现一般情况：如果是1346-n1345那么，可以划分为n段，即1出现在除最高位之外的其他四位数的次数是n*4*1000;

	public static int numberOf1BetweenAndN(int n){
if(n<=0){
return 0;
}
String str=n+"";
return numberOf1(str);
}
public static int numberOf1(String str){
char[] strN=str.toCharArray();
int length=strN.length;
if(length==1&&strN[0]=='0'){
return 0;
}
if(length==1&&strN[0]>'1'){
return 1;
}
int numFirstDigit=0;
if(strN[0]>'1')
numFirstDigit=(int) Math.pow(10,length-1);
else if(strN[0]=='1')
numFirstDigit=Integer.parseInt(str.substring(1))+1;
int numOtherDigits=(int) ((strN[0]-'0')*(length-1)*Math.pow(10, length-2));
int numRecursive=numberOf1(str.substring(1));
return numFirstDigit+numOtherDigits+numRecursive;
}

最后

以上就是害怕店员为你收集整理的剑指offer:从1到n整数中1出现的次数（java）的全部内容，希望文章能够帮你解决剑指offer:从1到n整数中1出现的次数（java）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。