經典算法題 ：整數中數字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;
    }