经典算法题 ：整数中数字3（大众点评笔试题）

• 问题描述

原题：0-999999之间的所有整数数字中，任何一位都不包括数字3的数字总数有多少个？

其实这道题目非常简单，就是9^6 = 531441个。因为每一位不能取3，就有9种可能，六位数就是

9^6。

不妨将题目一般化，及n取任意整数，0-n之间的所有整数数字中，任何一位都不包括数字3的数字总数有多少个？

• 解决方案1（暴力解法）

暴力解法，很简单，将整数转化成字符串，然后判断每一位是否有3。这种方法不可取，但是绝对正确，因此可以用来验证解决方案2中的方法是否正确。直接上代码：

public static int countOfNoThree(int n){
        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) == '3'){
                    count ++;
                    break;
                }
            }
        }
        return n + 1 - count;
    }
           

• 解决方案2（递归）

当n是一个l（l>=2）位数时，首先找到其中的高位，假设为h,则对于没有3的数来说，最高位可能为0，1，2，4，5…h，去掉3，对于0h-1这几种情况，每种情况都有9的(l-1)次方个数满足条件，即除了最高位外，其余位可以取09中除了3之外的任何数；对于高位取l的情况（因为满足条件的数不能超过n,所以不能和前面一样算）,就是l-1位数的结果，所以进行递归运算，代码如下：

public static int countOfNoThree2(int n){
        String s = String.valueOf(n);
        int first = s.charAt(0) - '0';
        if(s.length() == 1){
            return first >= 3 ? first : first + 1;
        }
        int count = 0;
        if(first <= 2){
            count = first * (int)Math.pow(9,s.length() - 1);
            count = count + countOfNoThree2(n % (int)Math.pow(10,s.length() - 1));
        }
        else if(first == 3){
            count = first * (int)Math.pow(9,s.length() - 1);
        }
        else{
            count = (first - 1) * (int)Math.pow(9,s.length() - 1);
            count = count + countOfNoThree2(n % (int)Math.pow(10,s.length() - 1));
        }
        return count;
    }