找到一个数字的 K 美丽值

标签: 数学 字符串 滑动窗口

难度: Easy

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

  • 子字符串长度为 k 。
  • 子字符串能整除 num 。

给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

  • 允许有 前缀 0 。
  • 0 不能整除任何值。

一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：

输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。

示例 2：

输入：num = 430043, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

提示：

  • 1 <= num <= 109
  • 1 <= k <= num.length （将 num 视为字符串）

Submission

运行时间: 19 ms

内存: 16.0 MB

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)
        s1 = 0
        for i in range(k):
            s1 = s1 * 10 + int(s[i])
        ans = 0 if num % s1 else 1
        p = pow(10, k)
        for i in range(k, len(s)):
            s1 *= 10 
            s1 = s1 - s1 // p * p 
            s1 += int(s[i])
            if s1 and num % s1 == 0:
                ans += 1
        return ans

Explain

该题解采用滑动窗口的方法来查找所有长度为 k 的子字符串，并检查它们是否能整除 num。首先，将 num 转换为字符串 s。使用一个循环构建初始的长度为 k 的子字符串 s1，并检查它是否能整除 num。然后，滑动窗口遍历整个字符串 s，每次右移一位，更新 s1 以表示当前的长度为 k 的子字符串，并判断它是否为 num 的因子。特别地，更新 s1 时采用了数学运算来避免重新计算子字符串对应的整数值，利用先前的值进行快速更新。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)  # 将数字转换为字符串
        s1 = 0
        # 初始化第一个长度为k的子字符串对应的整数值
        for i in range(k):
            s1 = s1 * 10 + int(s[i])
        # 检查首个子字符串是否能整除num
        ans = 0 if num % s1 else 1
        p = pow(10, k)  # 计算10的k次幂，用于后续计算
        # 遍历字符串，更新每个长度为k的子字符串对应的整数值
        for i in range(k, len(s)):
            s1 *= 10  # 左移一位
            s1 = s1 - s1 // p * p  # 移除最左边的数字
            s1 += int(s[i])  # 添加最新的数字
            # 如果s1不为0且能整除num，则增加计数
            if s1 and num % s1 == 0:
                ans += 1
        return ans

Explore

在题解中，使用pow(10, k)是为了在滑动窗口中快速移除最左边的数字。由于窗口大小始终是k，所以最左边的数字的权重恰好是10的k次幂。例如，对于三位数123，要移除'1'，我们需要从123中减去100，即1乘以10的2次幂。直接乘以10只适用于从一个数字左移一位，而pow(10, k)则是为了正确地在多位数中移除最左位数字。

具体实现方法是，首先将子字符串s1左移一位（即乘以10），然后减去最左边的数字乘以10的k次幂，这样就移除了最左边的数字。接着，将当前新的右边的数字加到s1上。例如，如果子字符串是'123'，右移后'234'，则首先计算'1230'（123乘以10），然后减去'1000'（1乘以10的3次幂），最后加上'4'，得到'234'。这样可以快速更新子字符串的整数值而无需每次都重新计算整个子字符串。

当子字符串的第一个数字是0时，在进行数学运算（移除最左边的数字）的过程中，它自然而然地被移除，因为0乘以任何数都是0。在新的子字符串中，这个0不会影响到最终的整数值，因为它在数值计算中的贡献是零。例如，如果子字符串是'023'，在左移并添加新的数字后，'230'中的'0'不会对计算有任何影响，因为它在数值上的贡献是零。因此，这种情况下无需特殊处理。