# # Leetcode 第204场周赛题解

## # Problem A - 重复至少 K 次且长度为 M 的模式 (opens new window)

class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
n = len(arr)
ans = 1
for i in range(n - m):
j = i + m
cnt = 1
while j + m - 1 < n:
if arr[i:i+m] == arr[j:j+m]:
cnt += 1
else:
break
j += m
ans = max(ans, cnt)
return ans >= k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var containsPattern = function(arr, m, k) {
return new RegExp((\\d{${m}})\\1{${k - 1}}).test(arr.join(''));
};

1
2
3

## # Problem B - 乘积为正数的最长子数组长度 (opens new window)

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int ans = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] == 0)
continue;
int j = i;
while (j + 1 < n && nums[j + 1] != 0)
j++;
vector<int> first(2, n + 1);
first[0] = i - 1;
int now = 0;
for (int k = i; k <= j; ++k) {
if (nums[k] < 0)
now ^= 1;
ans = max(ans, k - first[now]);
first[now] = min(first[now], k);
}
i = j;
}
return ans;
}
};

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

## # Problem C - 使陆地分离的最少天数 (opens new window)

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

class Solution {
int idx = 0;
bool found = false;
vector<int> p, sz, dfn, low;
void tarjan(int u, int p) {
dfn[u] = low[u] = ++idx;
int children = 0;
for (int v : adj[u]) {
if (!dfn[v]) {
children++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (p == -1 && children >= 2)
found = true;
else if (p != -1 && low[v] >= dfn[u])
found = true;
}
else if (v != p)
low[u] = min(low[u], dfn[v]);
}
}

int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}

void connect(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv)
return;
if (sz[pu] >= sz[pv]) {
p[pv] = pu;
sz[pu] += sz[pv];
} else {
p[pu] = pv;
sz[pv] += sz[pu];
}
}

public:
int minDays(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int N = n * m;
p = vector<int>(N, -1);
sz = vector<int>(N, 1);
int ans = N;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
if (!grid[i][j])
continue;
int u = i * m + j;
if (p[u] == -1)
p[u] = u;
int cnt = 0;
for (int k = 0; k < 4; ++k) {
int ni = i + dy[k], nj = j + dx[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= m || !grid[ni][nj])
continue;
int v = ni * m + nj;
cnt++;
if (p[v] == -1)
p[v] = v;
connect(u, v);
}
ans = min(ans, cnt);
}
int components = 0;
for (int i = 0; i < N; ++i) {
if (p[i] != -1 && i == find(i))
components++;
}
if (components >= 2 || components == 0)
return 0;

for (int i = 0; i < N; ++i) {
if (p[i] != -1) {
if (sz[find(i)] == 1)
return 1;
dfn = vector<int>(N);
low = vector<int>(N);
tarjan(i, -1);
break;
}
}

return found ? 1 : 2;
}
};

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

## # Problem D - 将子数组重新排序得到同一个二叉查找树的方案数 (opens new window)

#define MAXN 1005

typedef long long ll;
const ll MOD = 1e9 + 7;

ll fac[MAXN], rev[MAXN];

ll fexp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1)
ans = ans * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return ans;
}

ll C(ll n, ll k) {
return fac[n] * rev[k] % MOD * rev[n - k] % MOD;
}

class Solution {
ll dfs(vector<int> &nums) {
if (nums.size() <= 1)
return 1;
vector<int> small, large;
for (int i = 1; i < nums.size(); ++i)
if (nums[i] > nums[0])
large.emplace_back(nums[i]);
else
small.emplace_back(nums[i]);
ll n = large.size(), m = small.size();
ll fn = dfs(large), fm = dfs(small);
return C(n + m, n) * fn % MOD * fm % MOD;
}
public:
int numOfWays(vector<int>& nums) {
fac[0] = 1, rev[0] = 1;
for (int i = 1; i <= nums.size(); ++i) {
fac[i] = fac[i - 1] * i % MOD;
rev[i] = fexp(fac[i], MOD - 2);
}
return (dfs(nums) % MOD - 1 + MOD) % MOD;
}
};

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