首页 > 试题广场 >

2的个数

[编程题]2的个数
  • 热度指数:7591 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个正整数n,请返回0到n(包括n)的数字中2出现了几次。

测试样例:
10
返回:1
推荐
XD头像 XD
首先遇到这个问题的一般解法就是 遍历每一位然后进行累加;
int count = 0;
if(n <= 1)
    return 0;
for(int i=2;i<=n;i++)
{
    while(i>0)
    {
        if(i % 10 == 2)
            count++;
        i /= 10;    
    }
}
    return count;
这样的情况 对于n相对较小可以,但是如果n特别的大,时间将会很大。

所以,需要优化进行求解,我们可以计算各个位置的2数字的个数;
例如:xxxx2 仅仅是个位数字是2的情况 2的高位是0~1999 所以2000*1 2的后面没有低位
同理 计算百位为2的情况:12209 当百位是2的时候,还是有200-299,1200-1299,2200-2299,..11200-11299 有12*100个数,低位有200-209 10个数 所以当百位=2的时候 是
高位数*100+低位数+1;
当百位数<2的时候:包括百位的数以及后面的数都不需要考虑,直接:高位数*100;
当百位数>2的时候:包括这个百位数 有(高位数+1)*100;
这只是仅仅百位是2的情况,所以之后需要求解的是 十位,千位,万位 为2的情形与百位相一致;

代码:
        int count = 0;
        int low = 0;
        int high = 0;
        int cur = 0;
        int flag = 1;
        while(n/flag!=0)
        {
            low = n-(n/flag)*flag;
            cur = (n/flag)%10;
            high = n/(flag*10);
            if(cur == 1 || cur == 0)
                count += high*flag;
            if(cur == 2)
                count += high*flag + low +1;
            if(cur > 2)
                count += (high+1)*flag;
            flag *= 10;
        }
        return count;
    }

分析的时候有一点注意:是单独的某一位是2,例如百位为2,千位为2,不一起考虑同时为2;


编辑于 2015-08-17 16:38:52 回复(0)
更多回答
class Count2 {
public:
	int countNumberOf2s(int n) {

		if (n <= 1) return 0;

		long res = 0, m;
		for (m = 1;m <= n;m *= 10) {
			int tmp1 = n / m, tmp2 = n%m;

			res += (tmp1 + 7) / 10 * m + (tmp1 % 10 == 2)*(tmp2 + 1);
		}
		return res;
	}
};
很经典的题目,leetcode上有数一的个数,可以推广至求任意数字的个数。
发表于 2015-09-04 15:19:03 回复(7)
import java.util.*;

public class Count2 {
    public int countNumberOf2s(int n) {
        int count = 0;
    for (int i = 1; i <= n; i *= 10) {
        int a = n / i,b = n % i;
        //之所以补8,是因为当百位为0,则a/10==(a+8)/10,
        //当百位>=2,补8会产生进位位,效果等同于(a/10+1)
        count += (a + 7) / 10 * i + ((a % 10 == 2) ? b + 1 : 0);
    }
    return count;
    }
}

发表于 2017-06-10 19:27:40 回复(0)
class Count2:
    def countNumberOf2s(self, n):
        cnt, s, t = 0, 1, n
        while t > 0:
            k = n / s % 10
            h = n / (s * 10)
            l = 0 if s == 1 else n % s
            if k < 2:
                cnt += h * s
            elif k == 2:
                cnt += h * s + l + 1
            else:
                cnt += (h + 1) * s
            t /= 10
            s *= 10
        return cnt

发表于 2017-03-17 19:35:34 回复(0)
import java.util.*;
/*
我们假设dp[i]表示正整数i的时候出现2的次数
*///那里越界了,我想不明白
public class Count2 {
    public int countNumberOf2s(int n) {
        // write code here
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i = 1;i<=n;i++){
            if(isContain2(i))
                dp[i] = dp[i-1] + 1;
            else
                dp[i] = dp[i-1];
        }
        return dp[n];
    }
    
    public boolean isContain2(int n){
        String str = String.valueOf(n);
        if(str.contains("2"))
            return true;
        return false;
    }
}
跪求大神知道,为啥说我越界了呢
发表于 2020-06-03 19:18:32 回复(0)
class Count2 {
public:
    int countNumberOf2s(int n) {
        int cnt=0, low=0, high=0, cur=0, w=1;
        while(n/w){
            low = n - (n/w)*w;
            cur = (n/w)%10;
            high = n/(w*10);             if(cur<=1)                  cnt += high*w;             if(cur==2)                 cnt += high*w + low + 1;             if(cur>2)                 cnt += (high+1)*w;             w *= 10;         }         return cnt;
    }
};

发表于 2019-03-17 01:47:53 回复(0)
可以推出规律:
为了计算每个位w上出现多少个2,可以将数字分成三段,w位的值,高于w位的hig和低于w位的low。例如计算1231的十位上出现多少个2时,w=3,hig=12,low=1。
为什么这样分呢,主要是因为每个位上出现2的次数不仅和当前位的数字有关,也和hig和low有关。理由如下:
仍然讨论十位上出现多少个2的情况,
如果w<2,那么十位上出现2的次数为hig*10。例如1211,十位上有2的数是20,21,22,23...29(十个),120,121,122...129(十个),220,221,222...229(十个)......1120,1121...1129(十个),所以十位上出现2的次数为hig*10(注意这里是十位,其他位不考虑)。
如果w=2,那么十位上出现2的次数为hig*10+low+1。例如1221,这时除了小于2情况下的数,low=1,还会多出1220,1221,加一的原因是从0开始的。
如果w>2, 这样就明显了,出现2的次数为(hig+1)*10,可以自己推导下。
进而把这个规律推导到百位,w < 2,  hig*100;w = 2, hig*100 + low+1;w > 2, (hig+1)*100。
但是有特例:个位时,low要赋值为0,因为没有比个位更低的位了。最高位时,hig本身就是0。
代码如下:
class Count2 {
public:
    int countNumberOf2s(int n) {
        int hig, w, low,i=-1;  //i等于-1是因为do...while的原因
        int result = 0;
        do{
            i++;
            int m=pow(10,i);
            hig = n/m;
            w = hig%10;
            hig/=10;
            if(i == 0) low=0;
            else low=n%m;
            if( w < 2) result+=hig*pow(10,i);
            else if( w== 2)result+=hig*pow(10,i)+low+1;
            else result+=(hig+1)*pow(10,i);
        }while(hig != 0);   //这里用do...while是因为最高位也需要被计算,即使它的hig为0.
        return result;
    }
};
编辑于 2018-06-29 22:45:34 回复(1)
//方法1   时间复杂度太大,不可取
/*
 public class Count2 {
 public static int countthisnum(int n){
 int temp=0;
 while(n>0){
 if(n%10==2) temp++;
 n/=10;
 }
 return temp;
 }

 public int countNumberOf2s(int n) {
 int count=0;
 for (int i = 0; i <= n; i++) {
 count+=countthisnum(i);
 }
 return count;

 }
 }
 */
//方法二 
//  >2   (高位+1)*iFactor
//  =2     (高位)*iFactor+低位+1
//  <2  高位*iFactor
public class Count2 {

	public int countNumberOf2s(int n) {
		int iCount=0;
		int iFactor=1;
		int iLowerNum=0;
		int iCurrNum=0;
		int iHigherNum=0;
		while(n/iFactor!=0){
			iLowerNum=n-(n/iFactor)*iFactor;
			iCurrNum=(n/iFactor)%10;
			iHigherNum=n/(iFactor*10);
			
		switch(iCurrNum){
		case 0:
			iCount+=iHigherNum*iFactor;
			break;
		case 1:
			iCount+=iHigherNum*iFactor;
			break;
		case 2:
			iCount+=iHigherNum*iFactor+iLowerNum+1;
			break;
		default:
			iCount+=(iHigherNum+1)*iFactor;
			break;
		}
		iFactor*=10;
		}
    return iCount;
	}
}


发表于 2015-09-07 19:40:56 回复(3)
//通过遍历数字n的每一位,按照当前位跟2的关系判断该位置出现2的次数,累计即可
class Count2 {
public:
    int countNumberOf2s(int n) {
        int count = 0;
        int low,high,cur;
        for(int m=1;m<=n;m*=10)
        {
            high = (n/m)/10;
            low = n % m;
            cur = (n/m)%10;
            if(cur < 2)
            {
                count += high * m;
            }else if(cur > 2)
            {
                count += (high+1)*m;
            }else if(cur == 2)
            {
                count += high*m + low + 1;
            }
        }
        return count;
    }
};
发表于 2020-07-16 00:34:27 回复(0)
int count=0;
    	for(int i=0;i<=n;i++)
    	{
    		String s = String.valueOf(i); 
    		for(int j=0;j<s.length();j++)
    		{
    		if(s.charAt(j)=='2')
    			count++;
    		}
    	}
    	return count;
同,内存超。哪位大神可以指点指点 怎么控制内存啊
发表于 2017-07-25 09:51:53 回复(1)
class Count2 {
public:
    int countNumberOf2s(int n) 
    {
        vector<int> dp(10,0);
        dp[1] = 1;
        int res = 0;
        for (int i = 2; i <= 9; ++i) dp[i] = 10 * dp[i - 1] + (int)pow(10, i - 1);
        int i = 1;
        int sz = to_string(n).size();
        while (n > 0)
        {
            int times = (int)pow(10, sz - 1);
            int end = n / times;
            res += end * dp[sz - 1];
            n %= times;
            if (end > 2) res += times;
            else if (end == 2) res += n + 1;
            --sz;
        }

        return res;
    }
};

发表于 2017-07-01 16:00:14 回复(0)
import java.util.*;

public class Count2 {
    public int countNumberOf2s(int n) {
        // write code here
         int count=0,i;
        if(n<2) return 0;
        else if(n<=10) return 1;
        else
        for(int j=2;j<=n;j++){
           i=j;
          while(i>0){
              if(i%10==2)
                  count++;
                  i/=10;
               if(i==0) break;
          }  
        }
        return count;
    }
}

//最直接的做法,但超时,OMG

发表于 2017-04-29 22:40:12 回复(2)
class Count2 {
public:
    int countNumberOf2s(int n) {
        // write code here
 	int cnt = 0, k;
    for (int i = 1;k = n / i;i *= 10) {
        // k / 10 为高位的数字。
        cnt += (k / 10) * i;
        // 当前位的数字。
        int cur = k % 10;
        if (cur > 2) {
            cnt += i;
        } else if (cur == 2) {
            // n - k * i 为低位的数字。
            cnt += n - k * i + 1;
        }
    }
    return cnt;
 }
};

编辑于 2015-08-20 21:31:33 回复(2)
这道题太easy 不需要太多的思考
发表于 2019-08-07 16:55:05 回复(0)

如果要找包含5的个数,有三种情况:

一、每一位都小于5,如: n = 22222

(1)个位上:

每10个一组,即:1~10, 11~20, ..., 100~110, 111~120, ..., 22211~22220,共2222组,每组个位上是5的只有一个,所以共出现了2222 * 1次

剩下的数字22221、22222中个位数上不包含5,所以个位为5的为0个。

因此:总数为2222 + 0 = 2222。

(2)十位上:

每100个一组,即:1~100, 101~200, ..., 1001~1100, 1101~1200, ..., 22101~22200,共222组,每组数字中十位上是5的有10个,所以共出现了222 * 10 = 2220次

剩余22201 ~ 22222,十位数上不包含5。

因此:总数为2220 + 0 = 2220

 二、每一位都等于5,如: n = 55555

(1)个位上:

每10个一组,即:1~10, 11~20, ..., 100~110, 111~120, ..., 55541~55550,共5555组,每组个位上是5的只有一个,所以共出现了5555 * 1次

剩下的数字55551 ~ 55555中个位数上包含5的为55555,所以是1个。

因此:总数为5555 + 1 = 5556。

 

(2)十位上:

每100个一组,即:1~100, 101~200, ..., 1001~1100, 1101~1200, ..., 55401~55500,共555组,每组数字中十位上是5的有10个,所以共出现了555 * 10 = 5550次

剩余55501 ~ 55555,十位数上包含5的为55550 ~ 55555,共6个。

因此:总数为5550 + 6 = 5556

 

三、每一位都大于5,如: n = 88888

 

(1)个位上:

每10个一组,即:1~10, 11~20, ..., 100~110, 111~120, ..., 88871~88880,共8888组,每组个位上是5的只有一个,所以共出现了8888 * 1次

剩下的数字88881 ~ 88888中个位数上包含1个5。

因此:总数为8888 + 1 = 8889。

 

(2)十位上:

每100个一组,即:1~100, 101~200, ..., 1001~1100, 1101~1200, ..., 88701~88800,共888组,每组数字中十位上是5的有10个,所以共出现了888 * 10 = 8880次

剩余88801 ~ 88888,十位数上包含5的为88851 ~ 88859,共10个。

因此:总数为8880 + 10 = 88890

 

所以,当要找到数字为D时,按照每一位进行计算,并且每位包含2部分组成,分组中的个数,和剩余的个数。

 

对于每一位K:

 

1、分组中:

 

D的个数 = 分组数 * 每组个数 = 总数 / (10 ^ 位数) * (10 ^ 位数)

 

2、剩余:

 

K < D时,剩余为0

K > D时,为1 * (10 ^ 位数)

K = D时,为 总数 % (10 ^ 位数)+ 1

 

程序如下(Rust):

fn calculate_count(maxn: u32, digit: u32) -> u32 {

    let mut base_num: u32 = 1;
    let mut total: u32 = 0;
    
    while maxn > base_num {

        let group_count = maxn / 10 / base_num * base_num;

        let mut remained_count: u32 = 0;
        let bit_num: u32 = maxn % (base_num * 10) / base_num;

        if bit_num > digit {
            remained_count = 1 * base_num;
        } else if bit_num == digit {
            remained_count = maxn % base_num + 1;
        }

        total += group_count + remained_count;

        base_num *= 10;

        println!("{}: {} {}", base_num, group_count, remained_count);
    }

    return total;
}


发表于 2023-08-30 16:37:01 回复(0)
class Count2 {
public:
    /*
        依次计算个位、十位、百位、...、最高位出现2的数的次数
        将n分为三段
        higher   now_bit    lower
        if(now_bit>2) {
            出现2的情况有
                [0,higher]  2   [9,...,9] 9的个数时lower的长度  (higher+1)*(10^lower_bits)
        }则n等价于
        if(now_bit==2){
            出现2的情况有
                higher  2   [0,lower]          lower+1
                [0,higher-1]  2   [0,9....9]   =   higher*(10^lower_bits)
        }
        if(now_bit<2){
            [0,higher-1]  2   [0,9....9]    =   higher*(10^lower_bits)
        }
        从个位开始依次统计即可
    */

    int countNumberOf2s(int n) {
        // write code here
        if(n<2) return 0;
        int ans = 0;
		//求每一位固定为2时的情况数目
		//将n分为   当前位,高位部分,低位部分
		int higher=n/10,now_bit = n%10,lower=0;
		int t = 1;//pow计算是浮点型,有误差,pow(10,i);
        while(higher>0&nbs***bsp;now_bit>0){
			if(now_bit==2){
				ans+=lower+1;//higher 2 lower  的2数目,higher不变,lower从0变为lower 
			}
			//当前位>2时,等价于higher  now_bit  99..99,  lower从0-99.999
			if(now_bit>2){
				ans+=t;
			}
			ans+=t*higher; //  higher从0变为higher-1  low_bit为2  lower从0-99.999
			
			lower+=now_bit*t;
			now_bit = higher%10;
			higher/=10;
			t*=10;
        }
        return ans;
    }
	
};

发表于 2020-02-12 09:53:49 回复(0)
package com.qy.bz.bb; import java.util.Scanner; public class Count2
{ public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in); int n=sc.nextInt();
        Count2 count2=new Count2();
        System.out.println(count2.countNumberOf2s(n));
        sc.close();
    } public int countNumberOf2s(int n) { int count=0; for(int i=1;i<=n;i++) {
            String temp = String.valueOf(i); char ch[] = temp.toCharArray(); for (int j=0;j<ch.length;j++)
            { if(ch[j]=='2')
                {
                    count++;
                }
            }
        } return count;
    }
}
我这样写也提示超时。
发表于 2019-12-09 19:14:29 回复(0)
class Count2 {
public:
    int countNumberOf2s(int n) {
        // write code here
        int count = 0;
        for (int i = 1; n >= i; i = i * 10) {
            //count += n / (10 * i) * i;
            count += n / (10 * i) * i;
            int k = n % (10 * i);
            if (k >= 3 * i - 1) {
                count += i;
            }
            else if (k <= 2 * i - 1) {
                count += 0;
            }
            else {
                count += k - 2 * i + 1;
            }
        }
        return count;
    }
};

运行时间:3ms

占用内存:476k


编辑于 2019-07-14 14:34:35 回复(0)
class Count2 {
public:
    int countNumberOf2s(int n) {
        // write code here
        int div=1,rem,count=0,noi,x,y;
        for(int i=0;div>0;i++){
            x=(int)pow(10,i+1);
            y=(int)pow(10,i);
            div=n/x;
            rem=n%x;
            noi=rem/y;
            rem=rem%y;
            if(noi>2){
                count+=((div+1)*y);
            }
            else if(noi==2){
                count+=(div*y+rem+1);
            }
            else if(noi<2){
                count+=(div*y);
            }
        }
        return count;
    }
};

发表于 2019-06-22 00:56:17 回复(0)
class Count2 {
public:
    //3ms 492k 之前剑指offer有道数1个数的,改两个数字即可,可以去那看哈我的回答,有详细思路
    int countNumberOf2s(int n) {
        // write code here
        if(n<=0)return 0;
        int round=n,weight,base=1;
        int count=0;
        while(round){
            weight=round%10;
            round/=10;
            count+=round*base;
            if(weight==2)
                count+=(n%base)+1;
            if(weight>2)
                count+=base;
            base*=10;
        }
        return count;
    }
};

发表于 2019-03-07 20:43:06 回复(0)
class Count2 {
public:
    int countNumberOf2s(int n) {
        // write code here
        if(n<2)
            return 0;
        if(n<=10)
            return 1;

        int cnt=1;
        while(n/(cnt*10)>0)
            cnt*=10;
        int out=0;
        int bf=0;       
        while (cnt)
        {
            int cur = n / cnt;
            int tp = bf*cnt;

            if (cur > 2)
                tp += cnt;
            else if (cur == 2)           
               tp += n%cnt+1;

            out += tp;
            bf = bf * 10 + cur;
            n %= cnt;
            cnt /= 10;
        }
        return out;
    }
};
发表于 2018-06-28 11:22:09 回复(0)