2的个数__牛客网

推荐

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)

jason1990

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)

jiangcw

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)

Aurora1

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)

Java

lmz9509

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)

C/C++

nbgao

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)

C/C++

J.Fan

//通过遍历数字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)

Cavs

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)

LINDAMAN.

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)

C#

吃肉肉肉肉肉肉

这道题太easy 不需要太多的思考

发表于 2019-08-07 16:55:05 回复(0)

C++

会Rust的🐂

如果要找包含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)

C/C++

Shopee内推小虾米

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)

cpppppp

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)

C/C++

无声、

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)

C/C++

风景在云端

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)

C/C++

蛟龙吐火球丰

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)

2的个数

问题信息

热门推荐

通过挑战的用户

相关试题