# # Leetcode 第62场双周赛题解

## # Problem A - 将一维数组转变成二维数组 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(NM)$
• 空间复杂度$\mathcal{O}(NM)$

class Solution:
def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
if len(original) != m * n:
return []
return [original[i * n:(i + 1) * n] for i in range(m)]

1
2
3
4
5

## # Problem B - 连接后等于目标字符串的字符串对 (opens new window)

### # 方法一：暴力

• 时间复杂度为$\mathcal{O}(N^2|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution {
public:
int numOfPairs(vector<string>& nums, string target) {
int ans = 0, n = nums.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (i != j && nums[i].size() + nums[j].size() == target.size() && nums[i] + nums[j] == target)
ans++;
}
return ans;
}
};

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

### # 方法二：前后缀

• 时间复杂度为$\mathcal{O}(N|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution {
public:
int numOfPairs(vector<string>& nums, string target) {
int n = nums.size(), t = target.size();
vector<bool> pre(n), suf(n);
unordered_map<int, int> suf_map;
for (int i = 0; i < n; ++i) {
auto &num = nums[i];
int m = num.size();
if (m > target.size())
continue;
if (num == target.substr(0, m))
pre[i] = true;
if (num == target.substr(t - m, m))
suf[i] = true, suf_map[m]++;
}

int ans = 0;
for (int i = 0; i < n; ++i) {
if (pre[i]) {
ans += suf_map[t - nums[i].size()];
if (suf[i] && nums[i].size() * 2 == t)
ans--;
}
}

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
26
27
28
29

## # Problem C - 考试的最大困扰度 (opens new window)

### # 方法一：贪心

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
vector<int> T{-1}, F{-1};
for (int i = 0; i < n; ++i) {
T.push_back(i);
else
F.push_back(i);
}
T.push_back(n), F.push_back(n);

if (k >= T.size() - 2 || k >= F.size() - 2)
return n;

int ans = 0;
for (int i = 1; i + k < T.size(); ++i)
ans = max(ans, T[i + k] - T[i - 1] - 1);
for (int i = 1; i + k < F.size(); ++i)
ans = max(ans, F[i + k] - F[i - 1] - 1);

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 D - 分割数组的最多方案数 (opens new window)

### # 方法一：哈希表

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

using ll = long long;

class Solution {
public:
int waysToPartition(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0;
vector<ll> pre(n + 1);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + nums[i - 1];

// Do not change
for (int i = 1; i < n; ++i) {
if (pre[i] * 2 == pre[n])
ans++;
}

// Change one
unordered_map<ll, int> delta;
for (int i = n; i >= 1; --i) {
ll l = pre[i - 1];
ll r = pre[n] - l;
delta[l - r]++;
}

for (int i = 1; i <= n; ++i) {
ll l = pre[i - 1];
ll r = pre[n] - l;
if (i > 1)
delta[r - l]++;
delta[l - r]--;
ans = max(ans, delta[nums[i - 1] - k]);
}

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
26
27
28
29
30
31
32
33
34
35
36
37