首页 > 试题广场 >

整数中1出现的次数(从1到n整数中1出现的次数)

[编程题]整数中1出现的次数(从1到n整数中1出现的次数)
  • 热度指数:400692 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个整数 n ,求 1~n 这 n 个整数的十进制表示中 1 出现的次数
例如, 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意:11 这种情况算两次

数据范围:
进阶:空间复杂度 ,时间复杂度
示例1

输入

13

输出

6
示例2

输入

0

输出

0
推荐
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 回复(86)
 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 回复(4)
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 回复(8)

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 回复(8)
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 回复(11)
# -*- 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 回复(25)
最怕遇到这种有逻辑,得小心翼翼的题目了
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)
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)
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count=0
        for i in range(1,n+1):
            while i:
                if i%10==1:
                    count+=1
                i=i/10
        return count

发表于 2018-03-18 11:17:14 回复(4)
思路分析:
    出现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) {
        int count=0;
        for (int i = 0; i <= n; i++) {
            String s = Integer.toString(i);
            char[] chars = s.toCharArray();
            for (char aChar : chars) {
                if(aChar=='1'){
                    count++;
                }
            }
        }
        return count;
    }
}


发表于 2021-09-07 08:59:02 回复(0)

看了一圈似乎都是在数字本身上纠结的,我这个算是另辟奇径,就是把数字先转换为字符串,再连接起来,再数1出现的次数

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        str_n = ''
        for i in range(1, n + 1):
            str_n += str(i)
        res = str_n.count('1')
        return res
发表于 2018-03-10 04:38:11 回复(6)
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        //count表示1出现的总次数
		int count = 0;
		//从1到n循环n次,对每一个数求它包含多少个1
		for (int i = 1; i <= n; i++) {
			int temp = i;
			//求这个数包含多少个1
			while (temp != 0) {
				if (temp % 10 == 1) {
					count++;
				}
				temp = temp / 10;
			}
		}
		return count;
    }
}

编辑于 2016-07-31 21:04:33 回复(4)
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for(int i=1;i<=n;++i)
        {
            int k=i;
            while(k)
            {
                if(k%10==1)
                {
                    count++;
                }
                k/=10;
            }
        }
        return count;
    }
};

发表于 2021-08-05 03:43:09 回复(0)
不用那么复杂,字符串即可解决:
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        string a;
        int ret=0;
        for(int i=0;i<n;i++){
            a.append(to_string(i+1));
        }
        for(auto b:a){
            if(b=='1') ret++;
        }
        return ret;
    }
};

发表于 2020-08-23 20:42:56 回复(0)

一位一位的计算


思路来自B站视频。以下是原链接
https://www.bilibili.com/video/BV1uJ411573j?t=1824
假设n = 7543 [x] 29
如果要让百位的x = 1,那么需要考虑以下几种情况:

  1. 百位的x就是1的时,考虑前面4位数小于7543的情况,一共是0000-7542=7543种可能,而后面2位数的取值可以任意,00-99=100种可能
    • 总次数 = 7543 * 100
  2. 考虑前面4位数就取7543,若百位的x > 1,如n = 7543 [6] 29,那么就可以在比n小的数字中取到百位是1的数字,而后2位数还是可以随便取,还是100种可能
    • 总次数 = 1 * 100
  3. 若百位的x = 1,如 n = 7543 [1] 29,此时后两位就不能随便取值(因为要小于n),那么取值范围就是 00-29=30种可能
    • 总次数 = 1 * 30
  4. 若百位的x = 0,如 n = 7543 [0] 29,那么不可能取到百位是1的情况,因为一定比n大
    class Solution:
        def NumberOf1Between1AndN_Solution(self, n):
            # 运行时间:31ms  占用内存:5860k
            m = len(str(n))  # 数字的长度
            count = 0
            for i in range(1, m+1):
                high = n // 10 ** i                       # 找到当前位之前的位数
                mid = n % 10 ** i // 10 ** (i - 1)        # 找当前位
                low = n % 10 ** (i - 1)                   # 找当前位后面的位数
                # 第(1)个情况
                count += high * (10 ** (i - 1))
    
                if mid > 1:
                    # 第(2.1)个情况
                    count += 10 ** (i - 1)
                elif mid == 1:
                    # 第(2.2)个情况
                    count += (low + 1)
            return count

编辑于 2020-04-22 17:58:30 回复(0)
    # 利用组合数解题
    # 依次遍历每一个数位,计算该位为1的数有多少个,将结果累加返回
    # 每个数位计算的时候,对除去该位的前缀,后缀分别计算组合数
    # 同时需要保证组合出的数字在n的范围之内,所以将情况分为三种,该数位原本为1或者为0,或者为其他
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n == 1:  # 边界情况
            return 1
        ans = 0  # 最后返回的1的个数
        x = str(n)  # n的字符串形式,便于前缀后缀的数字转换
        for i in range(len(x)):  # 遍历每一个数位,计算该数位为1同时整个数在n之内的整数个数
            pre = int(x[:i]) if x[:i] else 0  # 前缀,没有前缀为0
            l = len(x[i + 1:])  # 后缀的长度
            # 该位原本为0的时候,合法数的前缀必小于pre,范围为[0,pre),共有pre种,后缀任意均合法,共有10**l种
            if x[i] == '0':
                ans += pre * 10 ** l
            # 该位原本为1的时候,合法数有两种
            # 一种是前缀范围为[0,pre),共有pre种,后缀任意
            # 另一种是前缀为pre,后缀范围[0,suf],共suf+1种
            elif x[i] == '1':
                suf = int(x[i+1:]) if x[i+1:] else -1  # 后缀范围,没有后缀为-1
                ans += pre * 10 ** l + suf + 1
            # 其他情况下,合法数前缀范围[0,pre],后缀任意
            else:
                ans += (pre+1) * 10 ** l
        return ans
发表于 2019-08-13 17:51:54 回复(0)
function NumberOf1Between1AndN_Solution(n)
{    var count=0;
     var j=0;
     var sum=0;
    for(var i=1;i<=n;i++){
        var kk=i.toString();
        j=0;
        count=0;
        while(kk.indexOf(1,j)!==-1){
                count++;
                j=kk.indexOf(1,j)+1;
            }
        
        sum+=count;
    }
 return sum;
}
数字转换成字符串,匹配字符1的个数,原谅我是个数学渣。。。。。
发表于 2019-06-29 20:12:17 回复(0)
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
    int count=0;
    int high=0,low=0,nor=0;
    for(int i=1;i<=n;i*=10){
      high=n/(i*10);
      low=n%i;
      nor=(n-high*(i*10))/i;
      if(nor==0)count+=high*i;
      else if(nor>1)count+=(high+1)*i;
      else {count+=high*i+low+1;}
    }                
     return count;   
    }
}
这个问题可以先用数学方法化简,可以把时间复杂度降至o(logn),否则直接遍历累加的时间复杂度为o(nlogn),可以说题目真正想问的应该是这种o(logn)的方法。
编辑于 2016-07-12 15:58:49 回复(0)
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        if(n<=0)
          return 0;
        for(int i=1;i<=n;i++)
        {
            while(i>0)
              {
                 if(i%10==1)
                     count++;
                 i=i/10;
              }
        }
        return count;
    }
}
超时,,,,,,

发表于 2015-05-26 21:46:06 回复(3)

问题信息

难度:
1274条回答 184034浏览

热门推荐

通过挑战的用户

查看代码