个人网站的前途,购物网站建设价格一览表,如何注册网站怎么注册,腾讯企业qq注册中心Leetcode 3448. Count Substrings Divisible By Last Digit 1. 解题思路2. 代码实现 题目链接#xff1a;3448. Count Substrings Divisible By Last Digit
1. 解题思路
这一题的话我们走的是一个累积数组的思路。
首先#xff0c;我们使用一个cache数组记录下任意段数字…Leetcode 3448. Count Substrings Divisible By Last Digit 1. 解题思路2. 代码实现 题目链接3448. Count Substrings Divisible By Last Digit
1. 解题思路
这一题的话我们走的是一个累积数组的思路。
首先我们使用一个cache数组记录下任意段数字对 1 1 1到 9 9 9的余数即任意cache[i][j] int(s[:i]) % j。
然后我们考察任意位置上所有前序数组对 1 1 1到 9 9 9的余数即 ∑ j 0 i s j i ≡ m o d ( k ) \sum\limits_{j0}^{i}s_{ji} \equiv mod(k) j0∑isji≡mod(k)而要求上述问题我们可以反向求累积数组 ∑ j 0 i ( s i − s j × 1 0 i − j ) ≡ m o d ( k ) \sum\limits_{j0}^{i}(s_{i} -s_{j} \times 10^{i-j}) \equiv mod(k) j0∑i(si−sj×10i−j)≡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。
需要注意的是事实上上述代码还可以进一步优化因为至少125几个数是必然满足只要以对应的数字结尾就一定可以满足条件因此我们事实上是可以对上述算法进行优化的不过这里就不过多展开了有兴趣的读者可以自行尝试一下。
