Leetcode 3448. Count Substrings Divisible By Last Digit

• Leetcode 3448. Count Substrings Divisible By Last Digit
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3448. Count Substrings Divisible By Last Digit

1. 解题思路

这一题的话我们走的是一个累积数组的思路。

首先，我们使用一个cache数组记录下任意段数字对$1$到$9$的余数，即任意cache[i][j] = int(s[:i]) % j。

然后，我们考察任意位置上所有前序数组对$1$到$9$的余数，即$\sum _{j=0}^i{s}_{ji}\equiv mod(k)$，而要求上述问题，我们可以反向求累积数组$\sum _{j=0}^i(s_i-s_j\times 10^{i-j})\equiv mod(k)$。

因此，我们可以用累计数组进行求解。

2. 代码实现

给出python代码实现如下：

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)cache = [[0 for _ in range(10)] for _ in range(n)]mod = [0 for _ in range(10)]for i, ch in enumerate(s):digit = int(ch)for j in range(1, 10):mod[j] = (mod[j] * 10 + digit) % jcache[i][j] = mod[j]def update_cnt(cnt):ans = [[0 for j in range(i)] for i in range(10)]for i in range(1, 10):for j in range(i):r = (j * 10) % ians[i][r] += cnt[i][j]return ansans = 0cnt = [[0 for j in range(i)] for i in range(10)]for i in range(1, 10):cnt[i][0] += 1for i, ch in enumerate(s):cnt = update_cnt(cnt)digit = int(ch) if digit != 0:ans += cnt[digit][cache[i][digit]]for j in range(1, 10):cnt[j][cache[i][j]] += 1return ans

提交代码评测得到：耗时9031ms，占用内存38.3MB。

需要注意的是，事实上上述代码还可以进一步优化，因为至少1，2，5几个数是必然满足只要以对应的数字结尾就一定可以满足条件，因此，我们事实上是可以对上述算法进行优化的，不过这里就不过多展开了，有兴趣的读者可以自行尝试一下。