# # Leetcode 第249场周赛题解

## # Problem A - 数组串联 (opens new window)

### # 方法一：模拟

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

class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
return nums + nums

1
2
3

## # Problem B - 长度为 3 的不同回文子序列 (opens new window)

### # 方法一：枚举

• 时间复杂度$\mathcal{O}(|S|+|\sum|^2\log|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution {
public:
int countPalindromicSubsequence(string s) {
int n = s.size();
vector<vector<int>> pos(26);
for (int i = 0; i < n; ++i) {
int ch = s[i] - 'a';
pos[ch].emplace_back(i);
}
int ans = 0;
for (int i = 0; i < 26; ++i) {
if (pos[i].size() >= 2) {
int l = pos[i][0], r = pos[i].back();
for (int j = 0; j < 26; ++j) {
auto it = upper_bound(pos[j].begin(), pos[j].end(), l);
if (it != pos[j].end() && *it < r)
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

## # Problem C - 用三种不同颜色为网格涂色 (opens new window)

### # 方法一：动态规划

$M$很小，提示我们按列进行枚举。首先，对于一列来说，合法的方案数为$3\cdot2^{M-1}$；然后我们再枚举考虑这些方案之间是否可以相邻，从而确定转移矩阵。最后的动态规划是比较显然的。

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

const MOD: usize = 1_000_000_007;

impl Solution {
pub fn color_the_grid(m: i32, n: i32) -> i32 {
let m = m as usize;
let n = n as usize;

let mut upper = 1;
for i in 0..m {
upper *= 3;
}

let mut codes = vec![];
for i in 0..upper {
let mut code = vec![0; m];
let mut num = i;
for j in 0..m {
if num == 0 {
break;
}
code[j] = num % 3;
num /= 3;
}
let mut valid = true;
for j in 0..m - 1 {
if code[j] == code[j + 1] {
valid = false;
break;
}
}
if valid {
codes.push(code);
}
}

let k = codes.len();
let mut trans = vec![vec![]; k];
for i in 0..k {
for j in i + 1..k {
let mut valid = true;
for t in 0..m {
if codes[i][t] == codes[j][t] {
valid = false;
break;
}
}
if valid {
trans[i].push(j);
trans[j].push(i);
}
}
}

let mut dp = vec![1; k];
for i in 1..n {
let mut ndp = vec![0; k];
for j in 0..k {
for &t in trans[j].iter() {
ndp[t] = (ndp[t] + dp[j]) % MOD;
}
}
dp = ndp;
}

let mut ans = 0;
for i in 0..k {
ans = (ans + dp[i]) % MOD;
}

ans as i32
}
}

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

## # Problem D - 合并多棵二叉搜索树 (opens new window)

### # 方法一：模拟

• 有且仅有一个根节点，无法替换任何一个其他二叉搜索树叶子节点。这个根节点也就是结果二叉树的根节点。
• 其余的根节点，有且仅有一个其他二叉搜索树的叶子节点与其具有相同取值。

1. 如果没有这样的根节点，则我们最后结果二叉树的根节点必然与某个原来的叶子节点取值相同，这样显然不是二叉搜索树。而如果有两个或更多这样的根节点，我们最后会得到一个森林，而无法得到一棵树。
2. 对于其余的根节点，如果没有取值相同的叶子节点，则其将无法合并到结果二叉树中；而如果有两个或更多与其取值相同的叶子节点，因为所有根节点的取值都不同，所以最后的二叉树中将至少包含两个具有相同取值的节点，显然不是二叉搜索树。

1. 它确实是一棵二叉搜索树。
2. 它包含了正确的节点数目，也即原来的所有二叉树的总节点数减去$N-1$（因为要进行$N-1$次合并）。比如在[[1, null, 3], [3, 1], [4]]这个例子，我们最后检查以4为根节点的这棵树，它确实是一棵二叉搜索树，但没有包含全部的节点。
• 时间复杂度$\mathcal{O}(N)$。其中$N$为所有二叉搜索树的节点总数。
• 空间复杂度$\mathcal{O}(N)$

const int N = 50005;
int cnt = 0;

bool valid(TreeNode* root, int lower, int upper) {
if (!root)
return true;
cnt++;
if (root->val < lower || root->val > upper)
return false;
return valid(root->left, lower, root->val - 1) && valid(root->right, root->val + 1, upper);
}

class Solution {
public:
TreeNode* canMerge(vector<TreeNode*>& trees) {
int n = trees.size();
vector<TreeNode*> parent(N, nullptr);
int tot = 0;
for (TreeNode *tree : trees) {
tot++;

if (tree->left) {
tot++;
if (parent[tree->left->val])
return nullptr;
parent[tree->left->val] = tree;
}

if (tree->right) {
tot++;
if (parent[tree->right->val])
return nullptr;
parent[tree->right->val] = tree;
}
}

TreeNode *root = nullptr;
for (TreeNode *tree : trees) {
if (!parent[tree->val]) {
if (root)
return nullptr;
root = tree;
} else {
TreeNode *p = parent[tree->val];
if (p->val > tree->val)
p->left = tree;
else
p->right = tree;
}
}

cnt = 0;
if (valid(root, 1, N) && cnt == tot + 1 - n)
return root;

return nullptr;
}
};

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