2025-08-17：统计可以被最后一个数位整除的子字符串数目。用go语言，给定一个只含数字字符的字符串 s。统计所有满足下列两

福大大架构师每日一题

发布于 2025-12-18 10:18:02

1750

2025-08-17：统计可以被最后一个数位整除的子字符串数目。用go语言，给定一个只含数字字符的字符串 s。统计所有满足下列两点的连续非空子串的数量：其末位不是 0，并且把该子串作为十进制整数后，该整数能被子串的最后一位数字整除。子串可以包含前导零。返回满足条件的子串个数。

1 <= s.length <= 100000。

s 只包含数字。

输入：s = "12936"。

输出：11。

解释：

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

题目来自力扣3448。

解决思路

为了高效地解决这个问题，我们可以利用动态规划的方法来跟踪子串的模数信息。具体来说，对于每个字符（即数字）在字符串中的位置，我们维护一个数组 f，其中 f[m][rem] 表示以当前字符结尾的子串中，模 m 余数为 rem 的子串数量。这里的 m 是可能的模数（即数字 1 到 9），rem 是模 m 的余数（0 到 m-1）。

详细步骤

1. 初始化：
- • 创建一个二维数组 f，大小为 [10][9]。f[m][rem] 表示以当前字符结尾的子串中，模 m 余数为 rem 的子串数量。这里 m 的取值范围是 1 到 9（因为模数只能是 1 到 9，对应数字的最后一位），rem 的取值范围是 0 到 m-1。
- • 初始化 ans 为 0，用于累计满足条件的子串数量。
2. 遍历字符串：
- • 对于字符串 s 中的每一个字符 c（即数字 d = int(c - '0')），我们进行以下操作：
  - • 如果 d 是 0，则跳过（因为子串的最后一个字符不能是 0）。
  - • 否则，对于每一个可能的模数 m（从 1 到 9）：
    - • 创建一个新的临时数组 nf（大小为 9），用于存储更新后的模数信息。
    - • 将当前数字 d 单独作为一个子串，其模 m 的余数为 d % m，因此 nf[d % m] += 1。
    - • 对于之前的所有余数 rem（即 f[m][rem] 的所有可能值），计算新的余数 (rem * 10 + d) % m，并将 f[m][rem] 的值累加到 nf 的对应位置。这相当于将当前数字 d 追加到所有以之前字符结尾的子串后面，形成新的子串。
    - • 将 nf 的值赋给 f[m]，完成滚动更新。
  - • 对于当前数字 d（即子串的最后一位），我们需要统计所有以 d 结尾的子串中，模 d 余数为 0 的数量（即 f[d][0]），并将这个数量累加到 ans 中。
3. 结果统计：
- • 遍历完所有字符后，ans 中存储的就是所有满足条件的子串数量。

示例解析

以 s = "12936" 为例：

• 初始时 f 全为 0，ans = 0。
• 处理 '1'：
- • d = 1，非 0。
- • 对于 m = 1，nf[0] = 1（因为 1 % 1 = 0）。
- • f[1][0] = 1，ans += 1（子串 "1"）。
• 处理 '2'：
- • d = 2，非 0。
- • 对于 m = 1，nf[0] = 1 + f[1][0] = 2（子串 "2" 和 "12"）。
- • 对于 m = 2，nf[0] = 1（子串 "2"），nf[1] = f[2][0]（"12" 的模 2 余数为 0，(0*10 + 2) % 2 = 0，所以 nf[0] += 1）。
- • f[2][0] = 2，ans += 2（子串 "2" 和 "12"）。
• 继续处理 '9'、'3'、'6'，类似地更新 f 和 ans。
• 最终 ans = 11。

时间复杂度和空间复杂度

• 时间复杂度：
- • 外层循环遍历字符串 s，长度为 n。
- • 内层循环遍历模数 m（1 到 9），共 9 次。
- • 对于每个 m，需要遍历余数 rem（最多 9 个）。
- • 因此，总时间复杂度为 O(n * 9 * 9) = O(n)（因为常数可以忽略）。
• 空间复杂度：
- • 使用了一个固定大小的二维数组 f，大小为 10 * 9。
- • 因此，额外空间复杂度为 O(1)（常数空间）。

总结

通过动态规划和滚动数组的技巧，我们高效地统计了满足条件的子串数量。算法的时间复杂度是线性的，空间复杂度是常数。

Go完整代码如下：

package main

import (
    "fmt"
)

func countSubstrings(s string) (ans int64) {
    f := [10][9]int{}
    for _, c := range s {
        d := int(c - '0')
        for m := 1; m < 10; m++ { // 枚举模数 m
            // 滚动数组计算 f
            nf := [9]int{}
            nf[d%m] = 1
            for rem, fv := range f[m][:m] { // 枚举模 m 的余数 rem
                nf[(rem*10+d)%m] += fv // 刷表法
            }
            f[m] = nf
        }
        // 以 s[i] 结尾的，模 s[i] 余数为 0 的子串个数
        ans += int64(f[d][0])
    }
    return
}

func main() {
    s := "12936"
    result := countSubstrings(s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def count_substrings(s: str) -> int:
    # f[m] 保存当前以遍历到的位置结尾的、按模 m 的不同余数分组的子串数量
    # 我们用长度可变的列表存储，每个 f[m] 的长度为 m（m=0 未使用，但保留占位）
    f = [[0] * 9for _ in range(10)]
    ans = 0

    for c in s:
        d = int(c)
        for m in range(1, 10):
            nf = [0] * m
            nf[d % m] = 1  # 只有当前数字本身作为子串
            for rem, fv in enumerate(f[m][:m]):
                if fv:
                    nf[(rem * 10 + d) % m] += fv
            f[m] = nf
        # 以当前字符结尾且末位为 d 的子串中，模 d 为 0 的个数（d==0 时 f[0][0] 为 0）
        ans += f[d][0]
    return ans

if __name__ == "__main__":
    s = "12936"
    print(count_substrings(s))