首页 > 试题广场 > 整数中1出现的次数(从1到n整数中1出现的次数)
[编程题]整数中1出现的次数(从1到n整数中1出现的次数)
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

802个回答

添加回答
推荐
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
    //主要思路:设定整数点(如1、10、100等等)作为位置点i(对应n的各位、十位、百位等等),分别对每个数位上有多少包含1的点进行分析
    //根据设定的整数位置,对n进行分割,分为两部分,高位n/i,低位n%i
    //当i表示百位,且百位对应的数>=2,如n=31456,i=100,则a=314,b=56,此时百位为1的次数有a/10+1=32(最高两位0~31),每一次都包含100个连续的点,即共有(a%10+1)*100个点的百位为1
    //当i表示百位,且百位对应的数为1,如n=31156,i=100,则a=311,b=56,此时百位对应的就是1,则共有a%10(最高两位0-30)次是包含100个连续点,当最高两位为31(即a=311),本次只对应局部点00~56,共b+1次,所有点加起来共有(a%10*100)+(b+1),这些点百位对应为1
    //当i表示百位,且百位对应的数为0,如n=31056,i=100,则a=310,b=56,此时百位为1的次数有a/10=31(最高两位0~30)
    //综合以上三种情况,当百位对应0或>=2时,有(a+8)/10次包含所有100个点,还有当百位为1(a%10==1),需要增加局部点b+1
    //之所以补8,是因为当百位为0,则a/10==(a+8)/10,当百位>=2,补8会产生进位位,效果等同于(a/10+1)
    int count=0;
    long long i=1;
    for(i=1;i<=n;i*=10)
    {
        //i表示当前分析的是哪一个数位
        int a = n/i,b = n%i;
        count=count+(a+8)/10*i+(a%10==1)*(b+1);
    }
    return count;
    }
};
编辑于 2015-08-18 23:21:43 回复(62)
/*
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位以下(低位)的数字,百位以上(高位)的数字。
① 如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,...,11100~11199,一共1200个。可以看出是由更高位数字(12)决定,并且等于更高位数字(12)乘以 当前位数(100)。
② 如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,则可以知道百位受高位影响出现的情况是:100~199,1100~1199,2100~2199,,....,11100~11199,一共1200个。和上面情况一样,并且等于更高位数字(12)乘以 当前位数(100)。但同时它还受低位影响,百位出现1的情况是:12100~12113,一共114个,等于低位数字(113)+1。
③ 如果百位上数字大于1(2~9),则百位上出现1的情况仅由更高位决定,比如12213,则百位出现1的情况是:100~199,1100~1199,2100~2199,...,11100~11199,12100~12199,一共有1300个,并且等于更高位数字+1(12+1)乘以当前位数(100)。
*/ 
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;//1的个数
        int i = 1;//当前位
        int current = 0,after = 0,before = 0;
        while((n/i)!= 0){           
            current = (n/i)%10; //高位数字
            before = n/(i*10); //当前位数字
            after = n-(n/i)*i; //低位数字
            //如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
            if (current == 0)
                count += before*i;
            //如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1
            else if(current == 1)
                count += before * i + after + 1;
            //如果大于1,出现1的次数由高位决定,//(高位数字+1)* 当前位数
            else{
                count += (before + 1) * i;
            }    
            //前移一位
            i = i*10;
        }
        return count;
    }
}
编辑于 2016-09-20 20:04:57 回复(35)

像类似这样的问题,我们可以通过归纳总结来获取相关的东西。

首先可以先分类:

个位

我们知道在个位数上,1会每隔10出现一次,例如1、11、21等等,我们发现以10为一个阶梯的话,每一个完整的阶梯里面都有一个1,例如数字22,按照10为间隔来分三个阶梯,在完整阶梯0-9,10-19之中都有一个1,但是19之后有一个不完整的阶梯,我们需要去判断这个阶梯中会不会出现1,易推断知,如果最后这个露出来的部分小于1,则不可能出现1(这个归纳换做其它数字也成立)。

我们可以归纳个位上1出现的个数为:

n/10 * 1+(n%10!=0 ? 1 : 0)

十位

现在说十位数,十位数上出现1的情况应该是10-19,依然沿用分析个位数时候的阶梯理论,我们知道10-19这组数,每隔100出现一次,这次我们的阶梯是100,例如数字317,分析有阶梯0-99,100-199,200-299三段完整阶梯,每一段阶梯里面都会出现10次1(从10-19),最后分析露出来的那段不完整的阶梯。我们考虑如果露出来的数大于19,那么直接算10个1就行了,因为10-19肯定会出现;如果小于10,那么肯定不会出现十位数的1;如果在10-19之间的,我们计算结果应该是k - 10 + 1。例如我们分析300-317,17个数字,1出现的个数应该是17-10+1=8个。

那么现在可以归纳:十位上1出现的个数为:

  • 设k = n % 100,即为不完整阶梯段的数字
  • 归纳式为:(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)

百位

现在说百位1,我们知道在百位,100-199都会出现百位1,一共出现100次,阶梯间隔为1000,100-199这组数,每隔1000就会出现一次。这次假设我们的数为2139。跟上述思想一致,先算阶梯数 * 完整阶梯中1在百位出现的个数,即n/1000 * 100得到前两个阶梯中1的个数,那么再算漏出来的部分139,沿用上述思想,不完整阶梯数k199,得到100个百位1,100<=k<=199则得到k - 100 + 1个百位1。

那么继续归纳百位上出现1的个数:

  • 设k = n % 1000
  • 归纳式为:(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)

后面的依次类推....

再次回顾个位

我们把个位数上算1的个数的式子也纳入归纳式中

  • k = n % 10
  • 个位数上1的个数为:n / 10 * 1 + (if(k > 1) 1 else if(k < 1) 0 else k - 1 + 1)

完美!归纳式看起来已经很规整了。 来一个更抽象的归纳,设i为计算1所在的位数,i=1表示计算个位数的1的个数,10表示计算十位数的1的个数等等。

  • k = n % (i * 10)
  • count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)

好了,这样从10到10的n次方的归纳就完成了。

  • sum1 = sum(count(i)),i = Math.pow(10, j), 0<=j<=log10(n)

但是有一个地方值得我们注意的,就是代码的简洁性来看,有多个ifelse不太好,能不能进一步简化呢? 我们可以把后半段简化成这样,我们不去计算i * 2 - 1了,我们只需保证k - i + 1在[0, i]区间内就行了,最后后半段可以写成这样

min(max((n mod (i*10))−i+1,0),i)

下面是代码

public class Solution {
     public int NumberOf1Between1AndN_Solution(int n) {
         if(n <= 0)
             return 0;
         int count = 0;
         for(long i = 1; i <= n; i *= 10){
             long diviver = i * 10;           
             count += (n / diviver) * i + Math.min(Math.max(n % diviver - i + 1, 0), i); 
        }
         return count;
     }
 }

补充一下,测试自己的和别人的代码,输入为Integer.MAX_VALUE的时候,1的个数已经超过Integer.MAX_VALUE,但是函数返回值只能规定为int,所以也很无奈

编辑于 2019-03-13 23:11:14 回复(40)
参考博文:http://www.cnblogs.com/nailperry/p/4752987.html,主要就是从数字出发找规律。
一、1的数目

编程之美上给出的规律:

1. 如果第i位(自右至左,从1开始标号)上的数字为0,则第i位可能出现1的次数由更高位决定(若没有高位,视高位为0),等于更高位数字X当前位数的权重10i-1

2. 如果第i位上的数字为1,则第i位上可能出现1的次数不仅受更高位影响,还受低位影响(若没有低位,视低位为0),等于更高位数字X当前位数的权重10i-1+(低位数字+1)。

3. 如果第i位上的数字大于1,则第i位上可能出现1的次数仅由更高位决定(若没有高位,视高位为0),等于(更高位数字+1)X当前位数的权重10i-1

二、X的数目

这里的  X[1,9] ,因为  X=0  不符合下列规律,需要单独计算。

首先要知道以下的规律:

  • 从 1 至 10,在它们的个位数中,任意的 X 都出现了 1 次。
  • 从 1 至 100,在它们的十位数中,任意的 X 都出现了 10 次。
  • 从 1 至 1000,在它们的百位数中,任意的 X 都出现了 100 次。

依此类推,从 1 至  10 i ,在它们的左数第二位(右数第  i  位)中,任意的 X 都出现了  10 i1  次。

这个规律很容易验证,这里不再多做说明。

接下来以  n=2593,X=5  为例来解释如何得到数学公式。从 1 至 2593 中,数字 5 总计出现了 813 次,其中有 259 次出现在个位,260 次出现在十位,294 次出现在百位,0 次出现在千位。

现在依次分析这些数据,首先是个位。从 1 至 2590 中,包含了 259 个 10,因此任意的 X 都出现了 259 次。最后剩余的三个数 2591, 2592 和 2593,因为它们最大的个位数字 3 < X,因此不会包含任何 5。(也可以这么看,3<X,则个位上可能出现的X的次数仅由更高位决定,等于更高位数字(259)X101-1=259)。

然后是十位。从 1 至 2500 中,包含了 25 个 100,因此任意的 X 都出现了  25×10=250  次。剩下的数字是从 2501 至 2593,它们最大的十位数字 9 > X,因此会包含全部 10 个 5。最后总计 250 + 10 = 260。(也可以这么看,9>X,则十位上可能出现的X的次数仅由更高位决定,等于更高位数字(25+1)X102-1=260)。

接下来是百位。从 1 至 2000 中,包含了 2 个 1000,因此任意的 X 都出现了  2×100=200  次。剩下的数字是从 2001 至 2593,它们最大的百位数字 5 == X,这时情况就略微复杂,它们的百位肯定是包含 5 的,但不会包含全部 100 个。如果把百位是 5 的数字列出来,是从 2500 至 2593,数字的个数与百位和十位数字相关,是 93+1 = 94。最后总计 200 + 94 = 294。(也可以这么看,5==X,则百位上可能出现X的次数不仅受更高位影响,还受低位影响,等于更高位数字(2)X103-1+(93+1)=294)。

最后是千位。现在已经没有更高位,因此直接看最大的千位数字 2 < X,所以不会包含任何 5。(也可以这么看,2<X,则千位上可能出现的X的次数仅由更高位决定,等于更高位数字(0)X104-1=0)。

到此为止,已经计算出全部数字 5 的出现次数。

总结一下以上的算法,可以看到,当计算右数第  i  位包含的 X 的个数时:

  1. 取第  i  位左边(高位)的数字,乘以  10 i1 ,得到基础值  a
  2. 取第  i  位数字,计算修正值
    1. 如果大于 X,则结果为  a+ 10 i1
    2. 如果小于 X,则结果为  a
    3. 如果等 X,则取第  i  位右边(低位)数字,设为  b ,最后结果为  a+b+1

相应的代码非常简单,效率也非常高,时间复杂度只有  O( log 10 n)

三、上代码
    /**
     * @param n
     * @param x [1,9]
     * @return
     */
    public int NumberOfXBetween1AndN_Solution(int n,int x) {
    	if(n<0||x<1||x>9)
    		return 0;
    	int high,low,curr,tmp,i = 1;
    	high = n;
    	int total = 0;
    	while(high!=0){
    		high = n/(int)Math.pow(10, i);// 获取第i位的高位
    		tmp = n%(int)Math.pow(10, i);
    		curr = tmp/(int)Math.pow(10, i-1);// 获取第i位
    		low = tmp%(int)Math.pow(10, i-1);// 获取第i位的低位
    		if(curr==x){
    			total+= high*(int)Math.pow(10, i-1)+low+1;
    		}else if(curr<x){
    			total+=high*(int)Math.pow(10, i-1);
    		}else{
    			total+=(high+1)*(int)Math.pow(10, i-1);
    		}
    		i++;
    	}
		return total;        
    }

发表于 2015-08-23 20:08:00 回复(17)
给一个最简单的代码,具体解释可以去leetcode上面去看。https://leetcode.com/discuss/44281/4-lines-o-log-n-c-java-python
class Solution {
public:
	int NumberOf1Between1AndN_Solution(int n){	
        int ones = 0;
    	for (long long m = 1; m <= n; m *= 10)
        	ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1);
   		 return ones;
	
	}
};
 

发表于 2015-07-08 20:46:44 回复(22)

引用一下骑着炮弹进城这位兄弟的答案,大概看懂了,代码如下

int countDigitOne(int n) {
    int ones = 0;
    for (long long m = 1; m <= n; m *= 10) {
        int a = n/m, b = n%m;
        ones += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
    }
    return ones;
}

我画张表如下:

当n = 3141592时:

<thead></thead>
m a b ones
131415920(3141592+8)/10*1+0=314160
103141592(314159+8)/10*10+0=314160
1003141592(31415+8)/10*100+0=314200
10003141592(3141+8)/101000+1(592+1)=314593

当然后面还有m=10000,100000,1000000三种情况,对应着万位,十万位, 百万位为1时的情况

下面说下a+8的意义:

当考虑个位,十位,百位这三位为1的情况时:

个位 2 ,当个位取值1时,前面的六位数字可由0~314159组成,即314160种情况

十位9,当十位取值1时,前面的五位数字可由0~31415组成,十位之后的一位可由0~9组成,组合情况31416*10=314160种情况

百位5,当百位取值为1时,前面的四位数字可由0~3141组成,百位之后的两位可由0~99组成,组合情况为3142*100=314200种情况


注意:当考虑千位1时:

千位1,千位取值即1,前面的三位数字可由0~314组成,但是当前面的值为314时,后面的三位只有0~592种情况(特殊情况),其余的情况即为前面的值为0~313,后面三位有0~999,情况数为3141000,所以总情况数为3141000 + 593=314593种情况

这时可发现和代码中的公式算的情况是吻合的,a+8的巧妙之处在于当a的最后一位(当前分析位)为0或1时,加8不产生进位,这是为需要单独算的特殊情况做准备,而当前分析位为2~9时,不需要考虑特殊情况,所以允许加8产生的进位。

编辑于 2017-07-04 22:51:30 回复(8)
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
		int count=0;
    	StringBuffer s=new StringBuffer();
    	for(int i=1;i<n+1;i++){
    		 s.append(i);
    	}
    	String str=s.toString();
    	for(int i=0;i<str.length();i++){
    		if(str.charAt(i)=='1')
    			count++;
    	}
    	return count;
    }
}

发表于 2016-08-23 11:08:33 回复(25)
class Solution {
public:
    /*
    	我们从低位到高位求每位1出现的次数,累加求和即可
        例如:求0~abcde中1的个数,现在我们求c这一位中1出现的次数,其他位雷同
        有两部分组成
        第一部分:ab * 100,表示当ab这两位在0~ab-1范围内时,de可以从0~99取值
    	    第二部分:如果c>1时,当ab为ab时1的个数为0~99
                  如果c=1时,当ab为ab时1的个数为de + 1
                如果c<0时,当ab为ab是1的个数为0
    */
    int NumberOf1Between1AndN_Solution(int n)
    {
        int exp = 1;
        int ans = 0; 
        while(n / exp)
        {
        	ans += n / (exp * 10) * exp;
            if(n % (exp * 10) / exp  > 1) ans += exp;
            else if(n % (exp * 10) / exp == 1) ans += (n % exp + 1);
            exp *= 10;
        }
        return ans;
    }
};
发表于 2016-08-02 12:43:14 回复(7)
Python 一行
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        return ''.join(map(str, range(n+1))).count('1')

发表于 2018-08-31 10:18:42 回复(2)
 int NumberOf1Between1AndN_Solution(int n)
    {
        int cnt = 0;
        int a=0,b=0;
        for(long long m=1;m<=n;m*=10){
            a = n/m;
            b = n%m;
            cnt+=(a+8)/10*m + (a%10==1)*(b+1);
        }
        return cnt;
    }
注解:参考一位牛友提到的leetcode的链接网址(包括求1~n的所有整数中2,3,4,5,6,7,8,9出现的所有次数)
通过使用一个 位置乘子m 遍历数字的位置, m 分别为1,10,100,1000…etc.(m<=n)

对于每个位置来说,把10进制数分成两个部分,比如说 当m=100的时候, 把十进制数 n=3141592 分成 a=31415 和 b=92 ,以此来分析百位数为1时所有数的个数和。m=100时,百位数的前缀为3141,当百位数大于1时,为3142*100,因为当百位数大于1时,前缀可以为0,即百位数可以从100到199,共100个数;当百位数不大于1时,为3141*100;如何判断百位数是否大于1?假设百位数为x,若(x+8)/10等于1,则大于1,若(x+8)/10等于0,则小于1。因此前缀可用(n/m + 8)/10 *m来计算(若计算2的个数,可以改为(n/m + 7)/10*m,若计算3的个数,改为(n/m + 6)/10*m,…以此类推)。

再例如m=1000时,n分为a=3141和 b=592;千位数的前缀为314,千位数不大于1,故前缀计算为314*1000;因为千位数为1,再加b+1(0到592)。即千位数为1的所有书的个数和为314*1000+592+1;公式(n/m + 8)/10*m + b +1。

注意:只有n的第m位为1时需要计算后缀,后缀计算为 (n/m%10==1)*(b+1),

即(n/m%10==1)判断第m位是否为1,若为1,则加上(b+1),若不为1,则只计算前缀。(若计算2的个数,可以改为(n/m%10==2)*(b+1),若计算3的个数,可以改为(n/m%10==3)*(b+1)…以此类推)


发表于 2017-10-12 20:37:08 回复(1)

python solution

def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int

        例:对于824883294,先求0-800000000之间(不包括800000000)的,再求0-24883294之间的。
        如果等于1,如1244444,先求0-1000000之间,再求1000000-1244444,那么只需要加上244444+1,再求0-244444之间的1
        如果大于1,例:0-800000000之间1的个数为8个100000000的1的个数加上100000000,因为从1000000000-200000000共有1000000000个数且最高位都为1。
        对于最后一位数,如果大于1,直接加上1即可。
        """
        result = 0
        if n < 0:
            return 0
        length = len(str(n))
        listN = list(str(n))
        for i, v in enumerate(listN):
            a = length - i - 1  # a为10的幂
            if i==length-1 and int(v)>=1:
                result+=1
                break

            if int(v) > 1:
                result += int(10 ** a * a / 10) * int(v) + 10**a
            if int(v) == 1:
                result += (int(10 ** a * a / 10) + int("".join(listN[i+1:])) + 1)
        return result
发表于 2017-10-14 14:26:17 回复(2)
	public int NumberOf1Between1AndN_Solution(int n) {

		int num = n;
		int count = 0;// 计算数字中含有1的数字个数。
		int strLen = 0;//每个数字的长度
		for (int i = 0; i <= num; i++) {
			String str = String.valueOf(i);
			strLen = str.length();
			for (int j = 0; j < strLen; j++) {
				if (str.charAt(j) == '1') {
					count++;
				}
			}
		}

		return count;
	}

发表于 2016-05-01 14:16:40 回复(17)
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # 将1-n全部转换为字符串
        # 只需要统计每个字符串中'1'出现的次数并相加即可
        count = 0
        for i in range(1,n+1):
            for i in str(i):
                if i == '1':
                    count += 1
        return count

发表于 2017-08-03 20:41:37 回复(21)
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;
        for(int i=0; i<=n; i++){
            int temp = i;
            //如果temp的任意位为1则count++
            while(temp){
                if(temp%10 == 1){
                    count++;
                }
                temp /= 10;
            }
        }
        return count;    
    }
};

发表于 2015-10-16 17:28:36 回复(15)
最怕遇到这种有逻辑,得小心翼翼的题目了
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        //统计每一位上1出现的次数
        int ret = 0, base = 1;
        while (n/base) {
            int bit = (n / base) - (n / base) / 10 * 10;
            if (bit == 0)
                ret += n / (base * 10)*base;
            if (bit == 1)
                ret += n / (base * 10)*base + (n - n/base*base ) + 1;
            if (bit > 1)
                ret += (n / (base * 10) + 1)*base;
            base *= 10;
        }
        return ret;
    }
};

编辑于 2017-08-10 17:11:03 回复(0)
思路分析:
    出现1无非是在个位、十位、百位、千位。。。等出现,那对一个数判断是否有1便是判断他的各个位有没有1出现。
例子:
    (1)个位上出现1的数有什么规律呢,个位出现1的数可写作x*10+1, 则有 ((x*10+1)-1)%10<1.
    (2)十位上出现1的数又有什么规律呢,十位出现1的数可写作 x*100+10+y,(y<10),则有 ((x*100+10+y)-10)%100=y<10.
    (3)再来,百位出现1的数字有什么规律呢,百位出现1的数可写作x*1000+100+y,y<100,则有((x*1000+100+y)-100)%1000=y<100
    总结:举例子只是为了方便理解,统一的来说,当10的k次方出现的1的数都可以写作,number=x*10^(k+1)+10^k+y,其中y<10^k,则恒有(number-10^k)%10^(k+1)<=y<10^k
方法:对一个数是否满足条件来说,先求出该数的位数length,然后遍历k=1->length,判断是否有满足上式的k值存在,若存在,则该数符合条件。
代码:
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int res = 0, length;
        for (int i = 1; i <= n; i++) {
            length = 0;
            while (i >= pow(10, length)) {
                if (((i -(int) pow(10, length)) % (int)pow(10, length + 1))<pow(10, length))
                    res++;
                length++;
           }
        }
        return res;
    }
};


note:第一次发表观点,同时也是算法这块的新手,有什么不好的,还请指正(●'◡'●)
编辑于 2017-02-22 14:42:42 回复(2)
代码很简单,但是理解思想比较难。
代码如下:
public int NumberOf1Between1AndN(int n){
   long count=0;
   long i=1;
   for(i=1;i<=n;i*=10){
     long a=n/i,b=n%i;
     count=count+(a+8)/10*i;
     if(a%10==1){
       count+=b+1;
     }
     return (int)count;
  }

发表于 2017-01-04 12:04:27 回复(0)
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
		if (n < 1)
			return 0;
		int len = getLenOfNum(n);
		if (len == 1)
			return 1;
		int tmp = (int) Math.pow(10, len - 1);
		int first = n / tmp;
		int firstOneNum = first == 1 ? n % tmp + 1 : tmp;
		int otherOneNUm = first * (len - 1) * (tmp / 10);
		return firstOneNum + otherOneNUm + NumberOf1Between1AndN_Solution(n % tmp);
	}

	private int getLenOfNum(int n) {
		int len = 0;
		while (n != 0) {
			len++;
			n /= 10;
		}
		return len;
	}
}
左神书中原题,比剑指offer中的讲解好得多,向左神致敬!
发表于 2016-08-04 17:24:59 回复(7)
public class Solution {
  public int NumberOf1Between1AndN_Solution(int n) {
	    if(n<0){
	    	return 0;
	    }
	    String str= Integer.toString(n);
	    int result = getNumberOf1(str, 0);
	    return result;
    }
	public static int getNumberOf1(String str,int index){
		int length = str.length()-index;
		if(length==1 && str.charAt(index)=='0'){
			return 0;
		}
		if(length==1){
			return 1;
		}
		//计算最高位的1
		int first = str.charAt(index)-'0';
		int result = 0;
		if(first>1){
			result += exp(length-1); 
		}else if(first==1){
			result += 1 + Integer.parseInt(str.substring(index+1));
		}
		//计算除了最高位的其他位
		result += first *(length-1)*exp(length-2);
		//计算比如2345中0---345中1的个数进行递归
		result += getNumberOf1(str, index+1);
		
		return result;
	}
	public static int exp(int n){
		int result =1;
		while(n>=1){
			result*=10;
			n--;
		}
		return result;
	}
}

发表于 2016-03-22 09:31:13 回复(1)
给出一个比较精简的代码,除了定义变量和return语句,没有其它语句了;使用的是递归的方法;时间复杂度为O(log10n)
思路:
1. 对于一个数n,先判断是否为个数,如果是且大于等于1,则返回1;如果是且等于0,则返回0;否则执行下一步

2. 取n中第一位为a,取n中后面其它位为b;(如n=123,则a=1,b=23)

3. 如果a大于1,表明数n的最高位经历了最高位为1的全部情况(比如n=223,a=2;n的最高位经历了100,101,102,103,...,199,200,201,...,223这么多数,这里我只计算这些数中最高位为1的个数,为100;类似的,对于n的位数为4时,是1000,为5时,是10000...);如果等于1,表明数n的最高位经历了b+1次为1的情况(比如n=123,a=1;说明n经历了100,101,102,...,123这24次最高位为1的情况,即b+1)【此处只考虑最高位,其它位使用递归】;

4. 此时还需要算除b以外的其它位上经历1的个数,这里直接递归使用a*NumberOf1Between1AndN_Solution(times-1),其中times表示的是和n同位数的最小整数(这里解释一下:比如n=223,a=2,b=23;这里times=100,因为a=2,表明n经历了从1到times-1的全部数有a次,即1到99经历了2次,那么计算99中1的个数乘以2就是除b以外其它位上经历1的个数)

5. 最后还需要算b中经历1的个数,直接调用原函数即可

    public int NumberOf1Between1AndN_Solution(int n) {
        if(n<10)return n>=1?1:0;
        int times=(int)(Math.pow(10,String.valueOf(n).length()-1));
        int a=Integer.parseInt(String.valueOf(n).substring(0,1));
        int b=Integer.parseInt(String.valueOf(n).substring(1,String.valueOf(n).length()));
        return a>1?times+a*NumberOf1Between1AndN_Solution(times-1)+NumberOf1Between1AndN_Solution(b):
                b+1+NumberOf1Between1AndN_Solution(times-1)+NumberOf1Between1AndN_Solution(b);
    }

编辑于 2017-09-30 11:42:49 回复(1)
    /**
       @author zhengyanan
       @date 2017/2/20 @time 15:53
     version_1:
     核心思路:
        1.分别判断每一位上1出现过的次数,从个位往高位递推;
        2.对于当前处理的位,需要根据其值是0,1,还是>1 对应有不同的处理。
            例如,假设当前考虑百位:
            (1 )如果百位>1,那么百位上1的次数 = (n/100 + 1) * 100;由高位和低位共同决定
            (2)如果百位=1,那么百位上1的数次 = (n/100) * 100 + (n%100 + 1);由高位和低位共同决定
            (3)如果百位<1,那么百位上1的次数 = (n/100) * 100;由高位决定。
       3.按照上面举例的思路类推,即可求得结果。
     复杂度:时间O(lgN);空间O(1)
       运行时间:30ms
       占用内存:503k

         其实跟推荐的高票答案一个思路,无非推荐答案对此种思想的具体编码又进行了优化
    */
    public int NumberOf1Between1AndN_Solution(int n) {
        int times = 0,current, addOne = 0,powerOfTen = 0,n2 = n;

        while (n > 0){
            current = n % 10;
            n /= 10;

            if (current > 1) {
                addOne = 1;
            }
            else if (current == 1){
                times += (n2 % Math.pow(10,powerOfTen)) + 1;
            }
            times += (n + addOne) * Math.pow(10, powerOfTen);

            powerOfTen++;
            addOne = 0;
        }

        return times;
    }

发表于 2017-02-20 16:41:05 回复(2)