LeetCode 3036. Number of Subarrays That Match a Pattern II
原题链接
困难
作者:
_YH_YH_
,
2024-02-20 05:19:25
,
所有人可见
,
阅读 34
算法1
KMP
const int N = 1e6 + 10;
class Solution {
public:
int ne[N];
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
string s, p;
int n = nums.size(), m = pattern.size();
for(int i = 1; i < n; i++){
int x = nums[i] - nums[i - 1];
if(x > 0) s += '1';
if(x < 0) s += '2';
if(x == 0) s += '0';
}
for(int i = 0; i < m; i++){
if(pattern[i] == -1) p += to_string(2);
else p += to_string(pattern[i]);
}
s = ' ' + s, p = ' ' + p;
cout << s << " " << p << endl;
for(int i = 2, j = 0; i <= m; i++){
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
int res = 0;
for(int i = 1, j = 0; i <= n; i++){
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j++;
if(j == m){
res ++;
j = ne[j];
}
}
return res;
}
};
算法2
字符串哈希
typedef unsigned long long ULL;
const int N = 1e6 + 10, P = 131;
class Solution {
public:
ULL h[N], p[N];
void hash(int s) {
p[0] = 1;
for (int i = 1; i <= s; i++)
p[i] = p[i - 1] * P;
}
ULL g(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
int n = nums.size(), m = pattern.size();
hash(n);
vector<int> d;
for (int i = 0; i < n - 1; i++) {
int x = nums[i + 1] - nums[i];
if (x > 0) d.push_back(1);
else if (x < 0) d.push_back(-1);
else d.push_back(0);
}
for (int i = 0; i < d.size(); i++) h[i + 1] = h[i] * P + d[i];
ULL pHash = 0;
for (int i = 0; i < m; i++) pHash = pHash * P + pattern[i];
int res = 0;
for (int i = 0; i + m <= d.size(); i++)
if (g(i + 1, i + m) == pHash)
res++;
return res;
}
};