- 這是一題簡單的定長度 sliding window。
class Solution {
public:
int divisorSubstrings(int num, int k) {
int curr = 0;
string s = to_string(num);
int res = 0;
for (int i = 0; i < s.size()-k+1; i++) {
int div = stoi(s.substr(i, k));
if (div != 0 && num % div == 0) res++;
}
return res;
}
};
- 用原本的 pattern 來做,但要注意 1e9 * 10 會爆掉,整數的範圍大概只有 2e9 (2147483647)。可改用先減再 shift 的方式處理。
class Solution {
public:
int divisorSubstrings(int num, int k) {
int curr = 0;
string s = to_string(num);
int res = 0;
int pk = pow(10, k-1);
for (int i = 0; i < k; i++) {
curr = curr * 10 + (s[i] - '0');
}
if (curr != 0 && num % curr == 0) res++;
for (int i = k; i < s.size(); i++) {
curr = 10 * (curr - (s[i-k] - '0') * pk) + (s[i] - '0');
if (curr != 0 && num % curr == 0) res++;
}
return res;
}
};