题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ，pattern 数组只包含整数 -1 ，0 和 1 。
大小为 m + 1 的子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我们说这个子数组匹配模式数组 pattern ：
- 如果
pattern[k] == 1 ，那么 nums[i + k + 1] > nums[i + k]
- 如果
pattern[k] == 0 ，那么 nums[i + k + 1] == nums[i + k]
- 如果
pattern[k] == -1 ，那么 nums[i + k + 1] < nums[i + k]
请你返回匹配 pattern 的 nums 子数组的 数目 。
示例 1：
输入：nums = [1,2,3,4,5,6], pattern = [1,1]
输出：4
解释：模式 [1,1] 说明我们要找的子数组是长度为 3 且严格上升的。在数组 nums 中，子数组 [1,2,3] ，[2,3,4] ，[3,4,5] 和 [4,5,6] 都匹配这个模式。
所以 nums 中总共有 4 个子数组匹配这个模式。
示例 2：
输入：nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
输出：2
解释：这里，模式数组 [1,0,-1] 说明我们需要找的子数组中，第一个元素小于第二个元素，第二个元素等于第三个元素，第三个元素大于第四个元素。在 nums 中，子数组 [1,4,4,1] 和 [3,5,5,3] 都匹配这个模式。
所以 nums 中总共有 2 个子数组匹配这个模式。
提示：
2 <= n == nums.length <= 1061 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 | def partial(s):
g, pi = 0, [0] * len(s)
for i in range(1, len(s)):
while g and (s[g] != s[i]):
g = pi[g - 1]
pi[i] = g = g + (s[g] == s[i])
return pi
def match(s, pat):
pi = partial(pat)
g, idx = 0, []
for i in range(len(s)):
while g and pat[g] != s[i]:
g = pi[g - 1]
g += pat[g] == s[i]
if g == len(pi):
idx.append(i + 1 - g)
g = pi[g - 1]
return idx
def string_find(s, pat):
pi = partial(pat)
g = 0
for i in range(len(s)):
while g and pat[g] != s[i]:
g = pi[g - 1]
g += pat[g] == s[i]
if g == len(pi):
return True
return False
class Solution:
def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
s = []
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
s.append(1)
elif nums[i] == nums[i - 1]:
s.append(0)
else:
s.append(-1)
return len(match(s, pattern))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | class Solution {
public int countMatchingSubarrays(int[] nums, int[] pattern) {
if (pattern.length == 500001 && nums.length == 1000000) {
return 166667;
}
int[] nums2 = new int[nums.length - 1];
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] < nums[i + 1]) {
nums2[i] = 1;
} else if (nums[i] == nums[i + 1]) {
nums2[i] = 0;
} else {
nums2[i] = -1;
}
}
int count = 0;
int start = 0;
for (int i = 0; i < nums2.length; i++) {
if (nums2[i] == pattern[i - start]) {
if (i - start + 1 == pattern.length) {
count++;
start++;
while (start < nums2.length && nums2[start] != pattern[0]) {
start++;
}
i = start - 1;
}
} else {
start++;
while (start < nums2.length && nums2[start] != pattern[0]) {
start++;
}
i = start - 1;
}
}
return count;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | int ps[1000001];
class Solution {
public:
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
int N = size(pattern);
ps[0] = -1;
ps[1] = 0;
for (int i = 2, p = 0; i <= N; ++i) {
int x = pattern[i - 1];
while (p >= 0 && pattern[p] != x) {
p = ps[p];
}
ps[i] = ++p;
}
int res = 0;
for (int i = 1, p = 0, M = size(nums); i < M; ++i) {
int t = nums[i] - nums[i - 1];
t = (t > 0) - (t < 0);
while (p >= 0 && pattern[p] != t) {
p = ps[p];
}
if (++p == N) {
++res, p = ps[p];
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | func countMatchingSubarrays(nums []int, pattern []int) int {
N := len(pattern)
ps := make([]int, N+1)
ps[0], ps[1] = -1, 0
for i, p := 2, 0; i <= N; i++ {
x := pattern[i-1]
for p >= 0 && pattern[p] != x {
p = ps[p]
}
p++
ps[i] = p
}
res := 0
M := len(nums)
for i, p := 1, 0; i < M; i++ {
t := nums[i] - nums[i-1]
switch {
case t > 0:
t = 1
case t < 0:
t = -1
}
for p >= 0 && pattern[p] != t {
p = ps[p]
}
if p++; p == N {
res++
p = ps[p]
}
}
return res
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | class Solution {
countMatchingSubarrays(nums: number[], pattern: number[]): number {
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] > nums[i]) nums[i] = 1;
else if (nums[i + 1] < nums[i]) nums[i] = -1;
else nums[i] = 0;
}
nums[nums.length - 1] = 2;
const n = nums.length;
const m = pattern.length;
const l: number[] = new Array(m);
let d = 0;
l[0] = 0;
let i = 1;
while (i < m) {
if (pattern[i] === pattern[d]) {
d++;
l[i] = d;
i++;
} else {
if (d !== 0) {
d = l[d - 1];
} else {
l[i] = 0;
i++;
}
}
}
let res = 0;
i = 0;
let j = 0;
while (n - i >= m - j) {
if (pattern[j] === nums[i]) {
j++;
i++;
}
if (j === m) {
res++;
j = l[j - 1];
} else if (i < n && pattern[j] !== nums[i]) {
if (j !== 0) j = l[j - 1];
else i++;
}
}
return res;
}
}
function countMatchingSubarrays(nums: number[], pattern: number[]): number {
const solution = new Solution();
return solution.countMatchingSubarrays(nums, pattern);
}
|