算法leetcode

leetcode第319场周赛：动态规划所需的信息由另一个动态规划来预处理

字数统计: 3.5k字   |   阅读时长: 14分
,

摘要: 本文是 leetcode 第 319 周赛的记录。主要涉及的算法包括模拟、暴力、BFS、置换环、动态规划

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

总览

2022 年 11 月 13 日进行了 leetcode 第 319 场周赛，之前参加了这场比赛但是文章一直拖着没有写，这里补一下。本场比赛由美团公司赞助，奖品如下：

本场比赛的赞助公司美团不用多介绍了，比较值得一提的是没有内推奖励了，难道侧面说明了美团在减少招人。

本场比赛发挥不佳，只做出了 A、C 两题，取得了有记录的最难看的成绩 2239/6175。成绩如下：

事后来看的话，B 题的暴力法应该是不难的，如果用到数论中的一些性质优化的话会有点难度。

A 题是一个简单的模拟。C 题是一个小众的知识点：置换环算法，直观理解比较简单，要证明的话需要一点抽象代数的基础。

D 题也是赛后冷静一分析才解决的，这个题还是挺有亮点的，算法主框架是一个单串线性 DP，转移时需要频繁查询某种信息，这个信息需要预处理出来，而这个预处理过程是区间 DP。

各个题目涉及到的知识点汇总如下：

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度，以 摄氏度（Celsius）为单位。

你需要将摄氏度转换为 开氏度（Kelvin）和 华氏度（Fahrenheit），并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。

返回数组 ans 。与实际答案误差不超过 10-5 的会视为正确答案。

注意：

  • 开氏度 = 摄氏度 + 273.15
  • 华氏度 = 摄氏度 * 1.80 + 32.00

提示：

1
0 <= celsius <= 1000

示例 1 ：
输入：celsius = 36.50
输出：[309.65000,97.70000]
解释：36.50 摄氏度：转换为开氏度是 309.65 ，转换为华氏度是 97.70 。

示例 2 ：
输入：celsius = 122.11
输出：[395.26000,251.79800]
解释：122.11 摄氏度：转换为开氏度是 395.26 ，转换为华氏度是 251.798 。

算法：模拟

按要求模拟即可。

代码(C++)

1
2
3
4
5
6
7
8
class Solution {
public:
    vector<double> convertTemperature(double celsius) {
        double kelvin = 273.15 + celsius;
        double fahrenheit = celsius * 1.8 + 32.0;
        return {kelvin, fahrenheit};
    }
};

B 题

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

提示：

1
2
1 <= nums.length <= 1000
1 <= nums[i], k <= 1000

示例 1 ：
输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：

  • [3,6]
  • [3,6,2]
  • [6]
  • [6,2]

示例 2 ：
输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。

算法：暴力 + 数论

枚举区间起点 $i$，然后枚举区间终点 $j = i,\cdots,n-1$。

在推进 $j$ 的过程中始终维护 $nums[i..j]$ 的最小公倍数 range_lcm：

1
range_lcm = lcm(range_lcm, nums[j])

若 range_lcm > k ，或者虽然 range_lcm <= k 时，但 k % range_lcm 不为 0，则以 $i$ 为起点的子数组包含 $j$ 点就不合法了，那更右边的点自然更无法包含。此时直接推进 $i$ 即可。

若满足以上两条，则判断 range_lcm 是否等于 k，若等于则答案加 1。若不等于，则 $j$ 不能作为终点，但当前子数组仍然合法，后续可能会出现使得区间最小公倍数等于 k 的终点，继续推进 $j$ 即可。

最小公倍数的时间复杂度为 $O(\log U)$，$U$ 为 $nums$ 中的取值范围。因此整体时间复杂度为 $O(n^{2}\log U)$。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int range_lcm = 1;
            for(int j = i; j < n; ++j)
            {
                range_lcm = lcm<int>(range_lcm, nums[j]);
                if(k < range_lcm || k % range_lcm != 0)
                    break;
                if(range_lcm == k)
                    ans += 1;
            }
        }
        return ans;
    }
};

C 题

给你一个 值互不相同 的二叉树的根节点 root 。

在一步操作中，你可以选择 同一层 上任意两个节点，交换这两个节点的值。

返回每一层按 严格递增顺序 排序所需的最少操作数目。

节点的 层数 是该节点和根节点之间的路径的边数。

提示：

1
2
3
树中节点的数目在范围 [1, 1e5] 。
1 <= Node.val <= 1e5
树中的所有值 互不相同 。

示例 1 ：
输入：root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
输出：3
解释：

  • 交换 4 和 3 。第 2 层变为 [3,4] 。
  • 交换 7 和 5 。第 3 层变为 [5,6,8,7] 。
  • 交换 8 和 7 。第 3 层变为 [5,6,7,8] 。
    共计用了 3 步操作，所以返回 3 。
    可以证明 3 是需要的最少操作数目。

示例 2 ：
输入：root = [1,3,2,7,6,5,4]
输出：3
解释：

  • 交换 3 和 2 。第 2 层变为 [2,3] 。
  • 交换 7 和 4 。第 3 层变为 [4,6,5,7] 。
  • 交换 6 和 5 。第 3 层变为 [4,5,6,7] 。
    共计用了 3 步操作，所以返回 3 。
    可以证明 3 是需要的最少操作数目。

示例 3 ：
输入：root = [1,2,3,4,5,6]
输出：0
解释：每一层已经按递增顺序排序，所以返回 0 。

算法：BFS + 置换环

首先从树根出发 BFS，在每一层记录当前层的所有节点 level_nodes，然后计算将 level_nodes 排序所需的交换次数。计算交换次数的过程是置换环算法。

在数列排序问题中，置换环的概念用于表示需要多少个交换操作才能将一个数列转换为排序后的顺序。根据代数理论我们知道，一个排列可以通过一系列对换，变换成任何其他排列，这些对换形成了一个置换环。

置换环算法通过计算数列中每个元素在排序后应该在的位置，以及实际位置，基于置换环的概念来确定需要多少次交换才能将数列排序。具体做法如下：

对 level_nodes 排序，排行结果为 sorted。然后我们构造一个映射 mapping，将 level_nodes[i] 映射为 sorted[i]。

然后我们一轮一轮地从 mapping 中取出数字，对于每一轮取数过程如下：

首先从 mapping 中取出一个数作为起点 start，然后根据 mapping 中的信息走到下一个点 next = mapping[start]，然后不断迭代地走到下一个点 next = mapping[next]，直至 mapping[next] == start。

这样从 mapping 中取出的若干个节点构成一个环，称其为置换环，如果环的长度为 $len$，则这个环中的元素要各自放到他们排序后的位置，最少需要 $len - 1$ 次交换。

具体过程就是不断从置换环中取出一个元素 $x$，将其交换到排序后应该在的位置 $swap(x, mapping[x])$，这样元素 $x$ 就从置换环中弹出，并交换到了它的目标位置。不断重复以上过程，直至置换环耗尽。

当置换环中只剩两个最后一次取出两个元素时，取出元素 $x$，一次交换 $swap(x, mapping[x])$ 即可同时让两个元素去到目标位置，此时置换环耗尽。根据以上描述，共进行了 $len - 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
int exchange(const vector<int>& a)
{
    vector<int> sorted = a;
    sort(sorted.begin(), sorted.end());
    int n = a.size();
    unordered_map<int, int> mapping; // j = mapping[i] 表示有向边 ij
    for(int i = 0; i < n; ++i)
    {
        mapping[a[i]] = sorted[i];
    }
    int ans = 0;
    vector<int> circle_nums;
    while(!mapping.empty())
    {
        int len = 1;
        // 起点
        int start = mapping.begin() -> first;
        int i = start;
        circle_nums.clear();
        circle_nums.push_back(i);
        while(mapping[i] != start)
        {
            i = mapping[i];
            len++;
            circle_nums.push_back(i);
        }
        ans += len - 1;
        for(int i: circle_nums)
            mapping.erase(i);
    }
    return ans;
}

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> level_nums;
        vector<TreeNode*> level_nodes;
        q.push(root);
        int ans = 0;
        while(!q.empty())
        {
            level_nums.clear();
            level_nodes.clear();
            while(!q.empty())
            {
                TreeNode *node = q.front();
                q.pop();
                level_nums.push_back(node -> val);
                if(node -> left)
                    level_nodes.push_back(node -> left);
                if(node -> right)
                    level_nodes.push_back(node -> right);
            }

            ans += exchange(level_nums);
            for(TreeNode *node: level_nodes)
                q.push(node);
        }
        return ans;
    }
};

D 题

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

  • 每个子字符串的长度 至少 为 k 。
  • 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

提示：

1
2
1 <= k <= s.length <= 2000
s 仅由小写英文字母组成

示例 1 ：
输入：s = “abaccdbbd”, k = 3
输出：2
解释：可以选择 s = “【aba】cc【dbbd】” 中框起来的子字符串。”aba” 和 “dbbd” 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

示例 2 ：
输入：s = “adbcda”, k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。

算法：单串线性DP + 区间DP预处理

也就是问字符串 $s$ 有多少个长度大于等于 $k$ 的回文子字符串。

考虑 $s[0..j]$ 上可分成的回文子串最多的个数，如果对于 $0 \leq i \leq j$，$s[i..j]$ 构成一个回文串，且长度 $j - i + 1 >= k$ 的话，我们就可以考虑 $s[0..i-1]$ 上最多可分成几个回文子串，然后再加上 $s[i..j]$ 这一个，就构成了一种可能性。

基于上述思路，我们隐约发现某种最优子结构，定义 $dp[j]$ 表示 $s[0..j-1]$ 上最多可以分成的回文子串个数。这里用 $j-1$ 是为了后面的初始化和状态转移方程比较简洁。

这样定义的话，答案就是 $dp[n]$，初始值 $dp[0] = 0$ 表示空串的情况。下面考虑状态转移方程。

考虑以 $j-1$ 结尾的子串 $s[i..j-1]$，其中 $0 \leq i \leq j - k$，如果这个范围内的 $i$ 没有能使得 $s[i..j-1]$ 是回文串的，那么 $s[0..j-1]$ 无论怎么分割，都不存在一个最优方案是以 $s[j-1]$ 为最后一个回文子串的结尾的，这样 $d[j]$ 就只能等于 $dp[j - 1]$。

另一方面，即使存在使得 $s[i..j-1]$ 成为回文串的 $i$，$s[0..j-1]$ 的最优方案可能也不以 $s[j-1]$ 作为最右边的回文子串的末尾，这样 $dp[j - 1]$ 依然是一个可能的决策。

对于回文子串 $s[i..j-1]$，如果方案中用这个回文子串，则 $s[0..j-1]$ 可分割的最多回文子串为 $dp[i] + 1$。对于每个 $0 \leq i \leq j - k$ 且 $s[i..j-1]$ 构成回文子串的情况，$dp[i] + 1$ 都是一种可能的决策。

以上的多种决策中，取其最大值作为 $dp[j]$ 的答案。

可以看到，在上面的状态转移过程中，要频繁询问 $s[i..j-1]$ 是否构成回文串，我们可以将这个信息预处理出来。记 $p[i][j]$ 表示 $s[i..j]$ 是否为回文串。这样状态转移方程如下：

预处理 $p$ 的过程是另一个动态规划，其阶段为区间长度 $l$，区间起点 $i$ 作为附加信息，这样 $j = i + l - 1$，这样的阶段划分是一个区间动态规划。初始化就是长度为 1 的时候为 true，即 $p[i][i] = true$，以及长度为 2 时 p[i][i+1] = s[i] == s[i+1]。状态转移方程如下：

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        # 预处理
        p = [[False for _ in range(n)] for _ in range(n)]
        for i in range(n):
            p[i][i] = True
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                p[i][i + 1] = True
        for l in range(3, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                if s[i] == s[j]:
                    p[i][j] = p[i + 1][j - 1]

        # 动态规划
        dp = [0 for _ in range(n + 1)]
        for j in range(1, n + 1):
            dp[j] = dp[j - 1]
            for i in range(j - k + 1):
                if p[i][j - 1]:
                    dp[j] = max(dp[j], 1 + dp[i])
        return dp[n]
Share