编写一个方法,数出从0到n中数字2出现了几次

原创
2016/11/28 14:17
阅读数 874

编写一个方法,数出从0到n中数字2出现了几次?
例如:如果n为20,那么0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 中共2共出现了3次。

思路:

1、暴力方法,数出每个数字包含几个2,然后累加起来。

2、分析:分别考虑数字n每一位出现2的次数,如123123;

从左往右考虑4123123;

考虑第一个1(即第6位),该位出现2的次数为4*10^6/10;

考虑第一个2(即第5位),该位出现2的次数为41*10^5/10+3123+1;

考虑第一个3(即第4位),该位出现2的次数为(412+1)*10^4/10;

附:除以10的原因在于:每10个数字,任意位出现2的概率为1/10.

总结规律:

第i位出现2个次数与该位所在的数字有关:

当第i位的数字小于2,出现次数就等于比其高位部分的数字*10^i/10,

当第i位的数字等于2,出现次数就等于比其高位部分的数字*10^i/10+n%(10^i),

当第i位的数字大于2,出现次数就等于(比其高位部分的数字+1)*10^i/10。

  1. int countAtSomeDigit(int num, int d)    //0到num之间,第d位2的个数  
  2. {  
  3.     int powerOf10 = (int)pow(10.0, d);  
  4.     int nextPower = powerOf10 * 10;  
  5.     int right = num % powerOf10;  
  6.     int roundDown = num - num % nextPower;  
  7.     int roundUp = roundDown + nextPower;  
  8.     int digit = num / powerOf10 % 10;  
  9.     if (digit < 2)  
  10.     {  
  11.         return roundDown / 10;  
  12.     }  
  13.     else if (digit == 2)  
  14.     {  
  15.         return roundDown / 10 + right + 1;  
  16.     }  
  17.     else  
  18.     {  
  19.         return roundUp / 10;  
  20.     }  
  21. }  
  22. int count2s(int num)    //0到num之间2的个数  
  23. {  
  24.     int len = 0;  
  25.     int temp = num;  
  26.     while (temp)  
  27.     {  
  28.         len++;  
  29.         temp /= 10;  
  30.     }  
  31.     int count = 0;  
  32.     for (int i = 0; i < len; i++)  
  33.     {  
  34.         count += countAtSomeDigit(num, i);  
  35.     }  
  36.     return count;  
  37. }

// 计算1-n中1出现的次数

public class CountOne {

    // 思路:分别计算“1”在每个位上面出现的次数,叠加起来

    public static int countNumOf1(int n) {

        if (n <= 0) {

            return 0;

        }

        int count = 0;

        int factor = 1;

        while(n / factor != 0) {

            int lowerNum = n - n / factor * factor;

            int currentNum = (n / factor) % 10;

            int highNum = n / (factor * 10);

            

            if (currentNum == 0) {

                // 如果为0,出现1的次数由高位决定

                count += highNum * factor;

            } else if (currentNum == 1) {

                // 如果为1,出现1的次数由高位和低位决定

                count += highNum * factor + lowerNum + 1;

            } else {

                // 如果大于1,出现1的次数由高位决定 

                count += (highNum + 1) * factor;

            }

            factor *= 10;

        }

        return count;

    }

    

    public static void main(String[] args) {

        // 测试

        System.out.println(countNumOf1(13));

        System.out.println(countNumOf1(23));

        System.out.println(countNumOf1(33));

        System.out.println(countNumOf1(93));

        System.out.println(countNumOf1(123));

 

    }

 

}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部