算法leetcode

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

字数统计: 3.8k字   |   阅读时长: 16分
, ,

摘要: 本文是 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