一.题目概述
二.代码
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
vector<int> v;
long long ret = 0;
for (char& ch : word) {
ret = (ret * 10 + (ch - '0')) % m;
v.push_back(ret == 0 ? 1 : 0);
}
return v;
}
};
三.思路优化
我们第一思路是每次从左往右拿一个数与之前的数组合然后整除，如果可以整除，那么到i这里的word[i]就可以改成1，但是这样的时间复杂度到了O（N）；
优化：
一个整数我们可以表示为n=a*10+b
我们要知道n%d=（x%d+y%d）%d
所以n%d=（a%d*10+b%d）%d
所以我们不必要每个数表示出来再进行整除操作，可以一边从左往右数字扩展一边计算出来整除的值。
从左到右遍历word，初始化ret=0；每次遇到一个数字x，就把数字ret更新为（ret*10+x）%d
ret是乘和加出来的，防止过大，用long long 存