陈东宇的博客

    2269. 找到一个数字的 K 美丽值

    力扣原题（完整题面）

    题意

    把整数 num 看作字符串，统计其中有多少个长度恰好为 k 的连续子串，转换成整数后是 num 的因子。子串可以有前导零，但数值 0 不能作为除数。

    样例 1

    输入：num = 240, k = 2
输出：2

    解释：长度为 2 的子串是 "24" 和 "40"，它们都是 240 的因子。

    样例 2

    输入：num = 430043, k = 2
输出：2

    解释：依次检查 "43"、"30"、"00"、"04"、"43"，只有两个 "43" 符合条件。"00" 转换后为 0，不能拿来做除数；"04" 转换后为 4，但 4 不是 430043 的因子。

    解法一：枚举子串（我的做法）

    先枚举每个子串的右端点 i，再枚举左端点 j。取出 numStr[j..i] 并转换成整数；当子串长度为 k、数值非零且能整除 num 时，给 dp[i] 加一。最后把所有 dp[i] 相加。

    这里的 dp[i] 表示以位置 i 结尾的合法子串数量。因为长度固定为 k，每个右端点最多只有一个候选子串，所以 dp[i] 只能是 0 或 1。它承担的是计数记录，没有用到前面位置的状态转移。

    class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string numStr = to_string(num);
        int n = numStr.size();
        vector<int> dp(n, 0);  // 以当前位置结尾的合法子串数量
        int ans = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                string tempNum = numStr.substr(j, i - j + 1);
                int val = stoi(tempNum);
                if (i - j + 1 == k && val != 0 && num % val == 0) {
                    dp[i] += 1;
                }
            }
            ans += dp[i];
        }
        return ans;
    }
};

    设 n 为 num 的位数。两层循环枚举了 O(n²) 个子串，每次截取和转换最多处理 O(n) 个字符，因此最坏时间复杂度为 O(n³)；dp 和临时字符串占用 O(n) 额外空间。题目中 num ≤ 10⁹，位数很少，这个做法也能通过。

    解法二：定长滑动窗口

    实际上只需要检查长度为 k 的窗口。用整数 window 保存当前窗口的数值：读入新数字时先执行 window = window * 10 + digit；窗口凑够 k 位后判断它是否为非零因子。判断完，把最左边的数字乘以 10^(k-1) 从 window 中减掉，下一轮再读入新数字，就得到右移一格后的窗口。

    例如 num = 240, k = 2：先得到 24，减去左边的 2 × 10 后剩 4；再读入 0，得到下一个窗口 40。前导零也能自然处理，例如 "04" 的数值就是 4。

    class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string numStr = to_string(num);
        int n = numStr.size();
        int place = 1;  // 10^(k-1)，最左边数字的位权
        for (int i = 1; i < k; ++i) {
            place *= 10;
        }

        int window = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            window = window * 10 + (numStr[i] - '0');
            if (i >= k - 1) {
                if (window != 0 && num % window == 0) {
                    ++ans;
                }
                window -= (numStr[i - k + 1] - '0') * place;
            }
        }
        return ans;
    }
};

    每个数字只进出窗口各一次，时间复杂度 O(n)。除了转换得到的数字字符串占用 O(n) 空间，窗口本身只用 O(1) 额外空间。