2575.找出字符串的可整除数组

【LetMeFly】2575.找出字符串的可整除数组：同余问题

力扣题目链接：https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div  是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0

返回 word 的可整除数组。

 

示例 1：

输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

 

提示：

• 1 <= n <= 105
• word.length == n
• word 由数字 0 到 9 组成
• 1 <= m <= 109

方法一：同余问题

解决这道题只需要知道一个公式：$(a\times b+c)% m=((a%m)\times(b%m)+(c%m))%m=((a%m)\times b+c)%m$。

也就是说，$(a\times 10+c)% m=((a%m)+c)%m$。

初始值$val=0$，遍历字符串，每次$val = (val\times10+word[i])%m$，并将其是否非零记录下来即可。

• 时间复杂度$O(len(word))$
• 空间复杂度$O(1)$，力扣返回值不计入算法空间复杂度

AC代码

C++

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        vector<int> ans(word.size());
        long long val = 0;
        for (int i = 0; i < word.size(); i++) {
            val = val * 10 + (word[i] - '0');
            val %= m;
            ans[i] = val == 0;
        }
        return ans;
    }
};

Python

from typing import List

class Solution:  # AC,100.00%,78.26%
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans = [0] * len(word)
        val = 0
        for i in range(len(word)):
            val = val * 10 + (ord(word[i]) - ord('0'))
            val %= m
            ans[i] = 0 if val else 1
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136544808