Leetcode第432场周赛总结

发表于 更新于

周赛链接：https://leetcode.cn/contest/weekly-contest-432/

涉及知识点：模拟、动态规划、二分检测

Question A：跳过交替单元格的之字形遍历

模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> zigzagTraversal(vector<vector<int>>& grid) {
        vector<int> result;
        int n = grid.size(); int m = grid[0].size();
        bool skip = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!skip) {
                    result.push_back(grid[i][(i % 2 == 0 ? (j) : (m - j - 1))]);
                    skip = true;
                }
                else {
                    skip = false;
                }
            }
        }
        return result;
    }
};

Question B：机器人可以获得的最大金币数

这道题的难点在于机器人可以感化两个劫匪，并规避在该地块的金币损失。

定义 dfs(i, j, k) 表示从 (i, j) 走到 (m - 1, n - 1)，还剩k次感化的最大金币得数。
那么有选择不感化递推公式：

$
dfs(i, j, k) = max(dfs(i + 1, j, k), dfs(i, j + 1, k)) + coins[i][j]
$

或选择感化递推公式

$
dfs(i, j, k) = max(dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1))
$

两者选最大即可。

在目的地有

$
dfs(m - 1, n - 1, k) = coins[m - 1][n - 1];
$

究其本质逻辑，其实这是一个三维的DP，第三维度为感化数量；我一直在用网格DP的逻辑分析问题，找不到第三维度的处理方式，所以出错。

1
// 代码之后补上

Question C：图的最大边权的最小值

这道题中，从0开始跑DFS检测其是否与其它节点还存在联系的复杂度为O(n)，即验证答案正确性的复杂度较低。

所以可以尝试通过二分查找答案，复杂度仅为O(n * log(X))。

另外值得一提的是，threshold参数是无用的，对于解不为-1的情况，总存在一个每个节点只访问过一次的DFS策略访问全图，又因为threshold >= 1，所以该条件总能满足。

1
// 代码之后补上