class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
}
};
6368. 找出字符串的可整除数组
给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：
word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1div[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 <= 105word.length == nword 由数字 0 到 9 组成1 <= m <= 109原站题解
rust 解法, 执行用时: 31 ms, 内存消耗: 2.8 MB, 提交时间: 2024-03-07 09:40:54
impl Solution {
pub fn divisibility_array(word: String, m: i32) -> Vec<i32> {
let mut ans = vec![0; word.len()];
let mut x = 0i64;
for (i, &c) in word.as_bytes().iter().enumerate() {
x = (x * 10 + (c - b'0') as i64) % m as i64;
if x == 0 {
ans[i] = 1;
}
}
ans
}
}
java 解法, 执行用时: 7 ms, 内存消耗: 55.7 MB, 提交时间: 2024-03-07 09:40:01
class Solution {
public int[] divisibilityArray(String word, int m) {
char[] s = word.toCharArray();
int[] ans = new int[s.length];
long x = 0;
for (int i = 0; i < s.length; i++) {
x = (x * 10 + (s[i] - '0')) % m;
if (x == 0) {
ans[i] = 1;
}
}
return ans;
}
}
php 解法, 执行用时: 100 ms, 内存消耗: 29.9 MB, 提交时间: 2024-03-07 09:29:52
class Solution {
/**
* @param String $word
* @param Integer $m
* @return Integer[]
*/
function divisibilityArray($word, $m) {
$ans = [];
$x = 0;
foreach (str_split($word) as $d) {
$x = ($x * 10 + intval($d)) % $m;
$ans[] = ($x == 0) ? 1 : 0;
}
return $ans;
}
}
golang 解法, 执行用时: 44 ms, 内存消耗: 7.1 MB, 提交时间: 2023-02-27 14:23:08
func divisibilityArray(word string, m int) []int {
ans := make([]int, len(word))
x := 0
for i, c := range word {
x = (x*10 + int(c-'0')) % m
if x == 0 {
ans[i] = 1
}
}
return ans
}
python3 解法, 执行用时: 228 ms, 内存消耗: 18 MB, 提交时间: 2023-02-27 14:22:41
'''
模运算性质
'''
class Solution:
def divisibilityArray(self, word: str, m: int) -> List[int]:
ans, x = [], 0
for d in map(int, word):
x = (x * 10 + d) % m
ans.append(int(x == 0))
return ans