【Leetcode Daily】2999统计强大整数的数目

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，要求你在某个区间内找到所有的“强大整数”，所谓的强大整数，是满足特定后缀（题目给定）的每一位有限制大小的（也是题目给定）的数字。

思路分享

• 作为一道 Hard 题确实不算容易，陆爻齐一开始尝试了暴力回溯，但由于没有合适地剪枝，还是失败了。
• 于是向灵神学习了数位dp来解决此题，所谓的数位就是从数字的位数来看问题。不过既然涉及到了动态规划，就有存储信息从而节省时间的步骤，嘛，具体的下面再说。
• 首先，由于数字很大，需要用字符串来表示。然后从左向右逐位遍历数字，这是要做剪枝。要限制每一位的最高位和最低位，当一位数字前面都是最高数字相同，那么自己这一位最大只能到最大数字的相同位置。如果前面有非最高数字，那么该位可以取任意值0-9；最低值同理。
• 上面是思路清晰的遍历，但对于本题还不够，会超时，这时需要引入记忆数组（dp）。由于如果某一位开始不用受到数值限制，那么这一位到最后产生的结果是固定的，可以记录下来，后续遇到相同的位数且无数值限制，就可以直接调用数组的数字。

代码解答（强烈建议自行解答后再看）

• 憋出来的数位 dp

class Solution {
public:
    inline int c2i(const char &c) {
        return c - '0';
    }

    long long dfs(const int &n, const string &start_str, const string &finish_str, int i, bool limit_high, bool limit_low, int &post_fix_index, const int &limit_num, const string &s, vector<vector<long long>> &memo) {
        if (i == n) {
            return 1;
        }

        if (!limit_high && !limit_low && memo[i][0] != -1) {
            return memo[i][0];
        }
        
        // 限制一个数位的最高和最低的值
        int high_num = limit_high ? c2i(finish_str[i]) : 9;
        int low_num = limit_low ? c2i(start_str[i]) : 0;

        long long result = 0;
        if (i < post_fix_index) {
            for (int new_num = low_num; new_num <= min(high_num,limit_num); new_num++) {
                result += dfs(n, start_str, finish_str, i+1, limit_high && new_num==high_num, limit_low && new_num == low_num, post_fix_index, limit_num, s, memo);
            }
        }
        else {
            int x = c2i(s[i - post_fix_index]);
            if (x >= low_num && x <= min(high_num,limit_num)) {
                result = dfs(n, start_str, finish_str, i+1, limit_high && x==high_num, limit_low && x == low_num, post_fix_index, limit_num, s, memo);
            }
        }

        if (!limit_high && !limit_low) {
            memo[i][0] = result;
        }
        

        return result;
    }

    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        string finish_str = to_string(finish);
        string start_str = to_string(start);

        int n = finish_str.length();

        start_str = string(n - start_str.length(), '0') + start_str;

        int post_index = n - s.size();
        // cout << "post:" << post_index << endl;

        vector<vector<long long>> memo(n, vector<long long>(1, -1));

        long long res = dfs(n, start_str, finish_str, 0, true, true, post_index, limit, s, memo);

        return res;
    }
};