2的个数

[编程题]2的个数

热度指数：7700 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

测试样例：

返回：1

算法知识视频讲解

推荐

首先遇到这个问题的一般解法就是 遍历每一位然后进行累加；
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)

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)

Java

今年夏天不太热

import java.util.*;

public class Count2 {

public int countNumberOf2s(int n) {

// write code here

int sum=0;

String[] tStrings=new String[n];

for (int i = 0; i < n; i++) {

tStrings[i]=i+" ";

}

for (int i = 0; i < tStrings.length; i++) {

if (tStrings[i].contains("2")) {

sum++;

}

return sum;

}

比较直接，但内存超了。。。。

发表于 2017-05-17 12:38:39 回复(0)

Java

涛仔

妹的，这样都说我运行时长过长？

public class Count2 {
	 public int countNumberOf2s(int n) {
		    int count=0;
	        for(int i=1;i<=n;i++){
	        	if(i%10==2||i/10==2){
	        		count++;
	        	}
	        }
	        return count;
	 }
	
	 public static void main(String[] args) {
           Scanner scanner=new Scanner(System.in);
           System.out.print("请输入一个整数：");
           int input=scanner.nextInt();
           Count2 c2=new Count2();
           System.out.println("\"2\"共出现"+c2.countNumberOf2s(input)+"次");
	 }
}

发表于 2017-04-28 23:08:50 回复(0)