leetcode第249场周赛:数据结构背景的难题,二叉查找树与哈希映射结合

  |  

摘要: 本文是 leetcode 第 249 周赛的记录。主要涉及的算法包括模拟、频数前缀和、计数DP、哈希映射。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


总览

这是 leetcode 第 249 场周赛,本场比赛的赞助公司是商汤,前 1000 名可获得校招免笔试机会,力度依然很大:

本场比赛难度不小,比赛时第四题没做出来,前三题都是一把过并且提交很快,38 分钟。最终成绩反而比以往全过的名次要好,138 名,应该是取得过的最好成绩:

本场比赛的亮点就是 D 题非常难,只有很少人做出来,使得过 3 个题成绩就可以很好。这是比较少见的数据结构背景的难题,需要结合二叉查找树的特性一点一点拆解问题,最终需要哈希映射的辅助解决问题。

各题的算法点以及参考文章如下:


A 题

给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ,数组下标 从 0 开始计数 ,对于所有 0 <= i < n 的 i ,满足下述所有要求:

ans[i] == nums[i]
ans[i + n] == nums[i]
具体而言,ans 由两个 nums 数组 串联 形成。

返回数组 ans 。

1
2
3
4
提示:
n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000

示例 1:
输入:nums = [1,2,1]
输出:[1,2,1,1,2,1]
解释:数组 ans 按下述方式形成:

  • ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
  • ans = [1,2,1,1,2,1]

示例 2:
输入:nums = [1,3,2,1]
输出:[1,3,2,1,1,3,2,1]
解释:数组 ans 按下述方式形成:

  • ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
  • ans = [1,3,2,1,1,3,2,1]

算法: 按要求模拟

将 nums 复制一份,然后将两份拼接起来。

代码: Python

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

B 题

给你一个字符串 s ,返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列,但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符(也可以不删除)且不改变剩余字符之间相对顺序形成的一个新字符串。

例如,”ace” 是 “abcde” 的一个子序列。

1
2
3
提示:
3 <= s.length <= 1e5
s 仅由小写英文字母组成

示例 1:
输入:s = “aabca”
输出:3
解释:长度为 3 的 3 个回文子序列分别是:

  • “aba” (“aabca” 的子序列)
  • “aaa” (“aabca” 的子序列)
  • “aca” (“aabca” 的子序列)

示例 2:
输入:s = “adc”
输出:0
解释:”adc” 不存在长度为 3 的回文子序列。

示例 3:
输入:s = “bbcbaba”
输出:4
解释:长度为 3 的 4 个回文子序列分别是:

  • “bbb” (“bbcbaba” 的子序列)
  • “bcb” (“bbcbaba” 的子序列)
  • “bab” (“bbcbaba” 的子序列)
  • “aba” (“bbcbaba” 的子序列)

算法: 频数前缀和

长度为 3 的子序列如果想构成回文,需要第一个第三个字符相同,中间的字符随意。

假设第一第三个字符为 X,那么 X 至少要在 s 中出现两次以上,由于相同的结果只计一次,我们只需要记录 X 的最左边的位置 left 和最右边的位置 right 即可,[left + 1, right - 1] 范围内的不同字符有多少个,X 就贡献了多少个目标子序列。

我们定义 range,遍历 s 预处理以下信息:range[ch - 'a'][0] 为字符 ch 在 s 中出现的最左位置,range[ch - 'a'][1] 为字符 ch 在 s 中出现的最右位置。

然后枚举 26 个字符,对每个字符 X: 记 left = range[X - 'a'][0]right = range[X - 'a'][1],如果 left + 1 < right,则 s[left + 1, right - 1] 不同字符的个数就是 X 对答案的贡献。

下面问题变成了我们如何能快速查询 s[left + 1, right - 1] 中不同字符的个数,我们对每个字符预处理一个频数前缀和 cntsums:cntsums[ch - 'a'][i] 为字符 ch 在 s[0..i-1] 中出现的次数。有一些类似的题目也用了这个频数前缀和的思路,例如下面这题:

遍历 s 预处理出 cntsums 之后,我们就可以快速响应 s[left + 1, right - 1] 中不同字符的个数的查询了: 具体做法就是枚举 26 个字符,对于字符 ch,如果 cntsums[ch - 'a'][right] - cntsums[ch - 'a'][left] > 0,则答案 +1。

代码(C++)

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
class Solution {
public:
int countPalindromicSubsequence(string s) {
vector<vector<int>> range(26, vector<int>(2, -1));
int n = s.size();
vector<vector<int>> cntsums(26, vector<int>(n + 1 , 0));
for(int i = 0; i < n; ++i)
{
if(range[s[i] - 'a'][0] == -1)
range[s[i] - 'a'][0] = i;
range[s[i] - 'a'][1] = i;
for(char ch = 'a'; ch <= 'z'; ++ch)
{
if(s[i] == ch)
cntsums[ch - 'a'][i + 1] = cntsums[ch - 'a'][i] + 1;
else
cntsums[ch - 'a'][i + 1] = cntsums[ch - 'a'][i];
}
}
int ans = 0;
for(char ch = 'a'; ch <= 'z'; ++ch)
{
int left = range[ch - 'a'][0];
int right = range[ch - 'a'][1];
if(left + 1 >= right)
continue;
for(char ch_mid = 'a'; ch_mid <= 'z'; ++ch_mid)
if(cntsums[ch_mid - 'a'][right] - cntsums[ch_mid - 'a'][left + 1] > 0)
++ans;
}
return ans;
}
};

C 题

给你两个整数 m 和 n 。构造一个 m x n 的网格,其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足:不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大, 返回 对 1e9 + 7 取余 的结果。

1
2
3
提示:
1 <= m <= 5
1 <= n <= 1000

示例 1:
输入:m = 1, n = 1
输出:3
解释:如下所示,存在三种可能的涂色方案。

示例 2:
输入:m = 1, n = 2
输出:6
解释:如下所示,存在六种可能的涂色方案。

示例 3:
输入:m = 5, n = 5
输出:580986

算法: 计数DP

网格宽度为 m(1 ~ 5),长度为 N,也就是 N 行 m 列。对于固定的一行,由于只有 m 个格子,每个格子有三种颜色可选,因此一行的颜色组合可能有 3 ^ m 种,对于 m 的最大值 5,颜色组合有 243 种。

我们用一个整数最低的 3m 个位来编码一行的颜色组合,每 3 位代表第一列的颜色。001, 010, 100 分别表示三种颜色。

将所有可能的颜色组合的编码结果放到一个数组 node 中,其中 node[i] 表示第 i 种颜色组合。

各个颜色组合有的可以相邻,有的不能相邻,颜色组合 node[i] 和颜色组合 node[j] 可以相邻的条件是 node[i] & node[j] == 0。我们可以预处理出可以相邻的颜色组合,记为 D。如果 node[i] 和 node[j] 可以相邻,则记 D[i][j] = 1,否则 D[i][j] = 0

有了一行的颜色编码和可以相邻的颜色编码组合后,我们可以写动态规划的算法了。

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[v][i] := 考虑 [0..i] 行且当前的第 i 行在状态 v 的方案数

答案:
sum(dp[v][n - 1])

初始化:
dp[v][0] = 1

状态转移:
dp[v][i] = dp[u][i - 1] 其中 D[u][v] == 1

下面这题与本题的思路完全一样:

代码(C++)

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
class Solution {
public:
int colorTheGrid(int m, int n) {
for(int i = 1; i <= 3; ++i)
{
int state = (1 << (i - 1));
dfs(state, i, 1, m);
}
int N = node.size();
D = vector<vector<int>>(N, vector<int>(N));
for(int i = 0; i < N - 1; ++i)
for(int j = i + 1; j < N; ++j)
if(check(i, j))
D[i][j] = D[j][i] = 1;

vector<vector<int>> dp(N, vector<int>(n));
for(int u = 0; u < N; ++u)
dp[u][0] = 1;
for(int i = 1; i < n; ++i)
for(int u = 0; u < N; ++u)
for(int v = 0; v < N; ++v)
if(D[u][v] == 1)
dp[u][i] = (dp[u][i] + (ll)dp[v][i - 1]) % MOD;

int ans = 0;
for(int u = 0; u < N; ++u)
ans = (ans + (ll)dp[u][n - 1]) % MOD;
return ans;
}

private:
vector<int> node; // node[i] := 节点 i 代表的一行颜色状态为 node[i]
vector<vector<int>> D;
using ll = long long;
const int MOD = 1e9 + 7;

bool check(int i, int j)
{
return (node[i] & node[j]) == 0;
}

void dfs(int state, int prev, int len, const int m)
{
if(len == m)
{
node.push_back(state);
return;
}
for(int j = 1; j <= 3; ++j)
{
if(j == prev) continue;
int nxt = state;
nxt <<= 3;
nxt |= (1 << (j - 1));
dfs(nxt, j, len + 1, m);
}
}
};

D 题

给你 n 个 二叉搜索树的根节点 ,存储在数组 trees 中(下标从 0 开始),对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 ,且不存在值相同的两个根节点。在一步操作中,将会完成下述步骤:

  • 选择两个 不同的 下标 i 和 j ,要求满足在 trees[i] 中的某个 叶节点 的值等于 trees[j] 的 根节点的值 。
  • 用 trees[j] 替换 trees[i] 中的那个叶节点。
  • 从 trees 中移除 trees[j] 。

如果在执行 n - 1 次操作后,能形成一棵有效的二叉搜索树,则返回结果二叉树的 根节点 ;如果无法构造一棵有效的二叉搜索树,返回 null 。

二叉搜索树是一种二叉树,且树中每个节点均满足下述属性:

  • 任意节点的左子树中的值都 严格小于 此节点的值。
  • 任意节点的右子树中的值都 严格大于 此节点的值。

叶节点是不含子节点的节点。

提示:

1
2
3
4
5
6
7
n == trees.length
1 <= n <= 5e4
每棵树中节点数目在范围 [1, 3] 内。
输入数据的每个节点可能有子节点但不存在子节点的子节点
trees 中不存在两棵树根节点值相同的情况。
输入中的所有树都是 有效的二叉树搜索树 。
1 <= TreeNode.val <= 5e4.

示例 1:
输入:trees = [[2,1],[3,2,5],[5,4]]
输出:[3,2,5,1,null,4]
解释:
第一步操作中,选出 i=1 和 j=0 ,并将 trees[0] 合并到 trees[1] 中。
删除 trees[0] ,trees = [[3,2,5,1],[5,4]] 。
在第二步操作中,选出 i=0 和 j=1 ,将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ,trees = [[3,2,5,1,null,4]] 。
结果树如上图所示,为一棵有效的二叉搜索树,所以返回该树的根节点。

示例 2:
输入:trees = [[5,3,8],[3,2,6]]
输出:[]
解释:
选出 i=0 和 j=1 ,然后将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ,trees = [[5,3,8,2,6]] 。
结果树如上图所示。仅能执行一次有效的操作,但结果树不是一棵有效的二叉搜索树,所以返回 null 。

示例 3:
输入:trees = [[5,4],[3]]
输出:[]
解释:无法执行任何操作。

算法: 二叉搜索树+哈希表

将所有根节点所在的位置 i 和它的值 val 放到 HashMap 中,i = mapping[val],值 val 对应的根节点为 trees[i]

对某个值 val 最多只能出现在一个树根中,因为如果有两个及以上的树根值均为 val,那么即使可以操作成一棵树,最终的树中也会有两个 val,不满足二叉搜索树的条件。

假设有某个值 val 既是某个树 trees[i] 的根,又是某个树的叶子,那么一定要将叶子替换为树 trees[i],因为如果不这么替换,那么即使可以操作成一棵树,最终的树中也会有两个 val,不满足二叉搜索树的条件。

那么我们就可以枚举所有的叶子,如果该叶子的值在 HashMap 中可以找到对应的根 i = mapping[val],那么就用 trees[i] 替换该叶子,同时将 val 从 HashMap 中删掉。

最终如果 HashMap 中只有一条记录,则该记录对应的根记为最终的一棵树的树根,然后我们再整体判断这棵树是否符合二叉查找树的条件,方法是看中序遍历序列是否单调递增。

还有一个细节需要注意:当枚举到某个叶子,它在 HashMap 中可以查到一个根,而该根与当前枚举到的叶子在之前的操作中可能已经在一颗树里了,此时用根替换掉叶子会形成环。那么最终 HashMap 中剩下的树根对应的树的节点个数就不对了。我们假设操作之前一共有 N 个节点,n 个树根,最终操作成一棵树需要做 n - 1 次替换,每次替换减少一个节点,最终的树应该有 N - (n - 1) 个节点。最终除了看生成的树是否满足二叉搜索树,还要看节点个数是不是对。

代码 (C++)

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
class Solution {
public:
TreeNode* canMerge(vector<TreeNode*>& trees) {
int n = trees.size();
mapping = unordered_map<int, int>();
for(int i = 0; i < n; ++i)
{
if(mapping.count(trees[i] -> val) > 0)
return nullptr;
mapping[trees[i] -> val] = i;
}
int N = n;
for(int i = 0; i < n; ++i)
{
if(trees[i] -> left)
{
++N;
auto it = mapping.find(trees[i] -> left -> val);
if(it != mapping.end())
{
trees[i] -> left = trees[it -> second];
mapping.erase(it);
}
}
if(trees[i] -> right)
{
++N;
auto it = mapping.find(trees[i] -> right -> val);
if(it != mapping.end())
{
trees[i] -> right = trees[it -> second];
mapping.erase(it);
}
}
}
if(mapping.size() != 1)
return nullptr;
TreeNode *root = trees[mapping.begin() -> second];
vector<int> vec;
_inorder(root, vec);
int m = vec.size();
if(m != N - (n - 1))
return nullptr;
int prev = vec[0];
for(int i = 1; i < m; ++i)
{
if(vec[i] <= prev)
return nullptr;
prev = vec[i];
}
return root;
}

private:
unordered_map<int, int> mapping; // val -> root_idx

void _inorder(TreeNode* node, vector<int>& vec)
{
if(node -> left)
_inorder(node -> left, vec);
vec.push_back(node -> val);
if(node -> right)
_inorder(node -> right, vec);
}
};

Share