2的个数

[编程题]2的个数

热度指数：7601 时间限制：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)