Solutions CS101

Appearance

3448.统计可以被最后一个数位整除的子字符串数目 ​

dp, https://leetcode.cn/problems/count-substrings-divisible-by-last-digit/

给你一个只包含数字的字符串 s 。

请你返回 s 的最后一位 不是 0 的子字符串中，可以被子字符串最后一位整除的数目。

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

注意：子字符串可以有前导 0 。

示例 1：

输入：s = "12936"

输出：11

解释：

子字符串 "29" ，"129" ，"293" 和 "2936" 不能被它们的最后一位整除，总共有 15 个子字符串，所以答案是 15 - 4 = 11 。

示例 2：

输入：s = "5701283"

输出：18

解释：

子字符串 "01" ，"12" ，"701" ，"012" ，"128" ，"5701" ，"7012" ，"0128" ，"57012" ，"70128" ，"570128" 和 "701283" 都可以被它们最后一位数字整除。除此以外，所有长度为 1 且不为 0 的子字符串也可以被它们的最后一位整除。有 6 个这样的子字符串，所以答案为 12 + 6 = 18 。

示例 3：

输入：s = "1010101010"

输出：25

解释：

只有最后一位数字为 '1' 的子字符串可以被它们的最后一位整除，总共有 25 个这样的字符串。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含数字。

主要思想：

优化： 由于直接遍历所有子字符串会导致时间复杂度过高，使用余数来优化，只需要关注每个子字符串的余数是否能被它的最后一位整除，从而避免了计算整个数的整除问题。

作者：灵茶山艾府 链接：https://leetcode.cn/problems/count-substrings-divisible-by-last-digit/solutions/3068623/gong-shi-tui-dao-dong-tai-gui-hua-python-iw4a/

python
class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        f = [[0] * 9 for _ in range(10)]
        for d in map(int, s):
            for m in range(1, 10):  # 枚举模数 m
                # 滚动数组计算 f
                nf = [0] * m
                nf[d % m] = 1
                for rem in range(m):  # 枚举模 m 的余数 rem
                    nf[(rem * 10 + d) % m] += f[m][rem]  # 刷表法
                f[m] = nf
            # 以 s[i] 结尾的，模 s[i] 余数为 0 的子串个数
            ans += f[d][0]
        return ans

超出时间限制683 / 699 个通过的测试用例

python
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0

        # 遍历所有可能的最后一位
        for j in range(n):
            last_digit = int(s[j])
            if last_digit == 0:
                continue
            # 遍历所有可能的起点
            num = 0
            for i in range(j, -1, -1):
                num += int(s[i]) * (10 ** (j - i))
                if num % last_digit == 0:
                    count += 1

        return count

# 测试代码
if __name__ == '__main__':
    s = Solution()
    print(s.countSubstrings("12936"))  # 输出: 11
    print(s.countSubstrings("5701283"))  # 输出: 18
    print(s.countSubstrings("1010101010"))  # 输出: 25