暴力搜索 复杂度O(NlogN)

暴力法，需要一个函数判断一个数是否是“好数”。
好数可简化为不含3，4，7的且至少含一个2或5或6或9的数。
对每个数，统计每个数字的出现数量再做判断即可。
时间复杂度O(NlogN)，因为要取出每个数的每个数位。

数位DP 复杂度O(logN)

好数的个数 = （只含018，25，69的数字数量） 减去 （只含018）的数字数量
于是需要一个函数快速求1到N中，只含0182569和只含018的数字数量。

定义：F018(n)为区间[0, n)中只含018这3个数字的数的数量。
为了方便计算，需要做以下定义。
1.区间包含0，且左闭右开。
2.该计算方法会为每个数加上前导零，本题中前导零不影响数字合法性。其他题目中若如此分解，可能需要对前导零做特殊处理。

以n=5123为例，该方法将[0, 5123)分解成[0000, 5000)，[5000, 5100), [5100, 5120) 和 [5120, 5123)。递归调用F018函数约logN次（每个数位一次）。
于是时间复杂度是O(logN)。函数具体实现见代码。

代码

暴力

class Solution_BruteForce{
    public:
    int nValidNumbers(int n){
        int ANS = 0;
        for(int i = 1 ; i <= n ; ++i){
            string num = to_string(i);
            int C[10] = {};
            for(auto ch : num)
                C[ch-'0']++;
            ANS += C[3] + C[4] + C[7] == 0 && 
                    C[2] + C[5] + C[6] + C[9] > 0;
        }
        return ANS;
    }
};

数位DP

class Solution {
    vector<int> Mask1, Sum1;
    vector<int> Mask2, Sum2;
    void Initialize(){
        // Mask[k]表示k是否属于合法数字
        // Sum[k]表示小于k的合法数字有多少个

        // 合法数字为018，25，69
        //                   0 1 2 3 4 5 6 7 8 9
        Mask1 = vector<int>({1,1,1,0,0,1,1,0,1,1});
        Sum1  = vector<int>({0,1,2,3,3,3,4,5,5,6});

        // 合法数字为018
        //                   0 1 2 3 4 5 6 7 8 9
        Mask2 = vector<int>({1,1,0,0,0,0,0,0,1,0});
        Sum2  = vector<int>({0,1,2,2,2,2,2,2,2,3});
    }
    // 求a的k次方
    int pow(int a, int k){
        int ANS = 1;
        for(int i = 0 ; i < k ; ++i)
            ANS *= a;
        return ANS;
    }
    // 区间[0, num)中有多少个只包含0182569的数
    int F0182569(string &num, int k, int len){
        // 递归终点
        if(k == len)
            return 0;
        // 取出下标k的数字
        int cntNum = num[k] - '0';
        int ANS = 0;
        // 计算数位k上的数小于cntNum时，有多少个合法的数
        // 以 num = 5123 为例
        // k = 0 时计算[0000, 5000) 中合法数量
        // k = 1 时计算[5000, 5100) 中合法数量
        // k = 2 时计算[5100, 5120) 中合法数量
        // k = 3 时计算[5120, 5123）中合法数量

        // 合法数量 = 小于cntNum的数字数量 * 7^(剩余数位个数)
        ANS += Sum1[cntNum] * pow(7, len - k - 1);

        // 计算数位上的数等于cntNum时，有多少个合法的数
        // 以 num = 5123 为例
        // k = 0 时计算[5000, 5123) 中合法数量
        // k = 1 时计算[5100, 5123) 中合法数量
        // k = 2 时计算[5120, 5123) 中合法数量

        // 当前数字合法时，递归求合法数量
        if(Mask1[cntNum])
            ANS += F0182569(num, k+1, len);
        return ANS;
    }
    // 区间[0, num)中有多少个只包含018的数
    // 注释同上面函数
    int F018(string &num, int k, int len){
        if(k == len)
            return 0;
        int cntNum = num[k] - '0';
        int ANS = 0;
        ANS += Sum2[cntNum] * pow(3, len - k - 1);

        if(Mask2[cntNum])
            ANS += F018(num, k+1, len);
        return ANS;
    }
public:
    Solution(){
        Initialize();
    }
    int nValidNumbers(int n){
        // 将n+1转化为字符串
        string num = to_string(n+1);
        // 答案等于 (只含0182569的数字数量) 减去 (只含018的数字数量)
        int ANS = F0182569(num, 0, num.length()) -
                  F018(num, 0, num.length());
        return ANS;
    }
};