leetcode 2022 秋季编程大赛(个人赛)

零、背景

今年的 leetcode 秋季赛编程大赛比晚年晚一些。

想到这里我又要吐槽了， 这次的团队赛 leetcode 安排在国庆假期的最后一天，感觉大部分人都无法参加了。

回到个人赛，这次比赛 5 道题，我做出前 4 道，排名进入前百名，但是没能进去前 50 名。

最后一题想的是直接使用动态规划做，结果状态转移方程推导不出来，最后看题解发现需要二分。
这次没做出来是自己的问题。
求最值的最值是个经典的问题，确实需要二分的，自己忘记了。
既然不知道这个，看到求最值，也可以往二分方向去思考的，以后要注意了。

一、气温变化趋势

题意：给两个正数数组，数组内相邻位置的值有三种关系：大于、等于、小于。
问两个数组相同位置关系相等的最长区间是多少。

思路：数组预处理为关系，相等的关系标记为 1，否则标记为 0。
问题就转化为了最长连续 1 的个数，典型的动态规划。

二、交通枢纽

题意：给一个有向图的边列表（没告诉顶点个数），问是否有一个超级顶点，这个顶点没有出边，所有其他顶点都可以到达这个顶点。
如果存在，输出这个超级顶点。

思路：预处理边，统计每个顶点的入度与出度与顶点的个数。
如果出度为0 的顶点只有一个，再判断其他顶点到这个顶点是否都有边即可。

三、弹珠游戏

题意：给一个矩阵，矩阵的值分为四种：终止点、左转点、右转点、空白点。
现在可以从矩阵的四条边垂直射入一个珠子，问在指定步数内是否可以到达终止点。
射入有两个限制：入口的值必须是空白点，并且入口不再四个角上。
求出所有的满足条件的入口坐标。

思路：枚举所有的合法入口，记忆化搜索即可。

矩阵每个位置可能有四个方向通过，所以状态个数为矩阵大小的四倍。

注意事项：题目是问是否可以在指定步数内到达终点，可以先求出入口到达终点的步数，然后再比大小即可。

四、二叉树灯饰

题意：给一个有根二叉树，数的值为 0 和 1。
现在可以对一个子树做下面三种操作：根节点值反转、根和儿子的值反转、根和所有后代的值反转（子树）。
问最少需要多少步骤，可以把整个二叉树的值变为 0.

思路：典型的树上 DP。

有三个操作，枚举组合就是 8 种情况。

具体到每个子树时，父子的操作不存在，所以变为 4 种状态。

状态 1）不受父节点影响
状态 2）影响，根节点反转
状态 3）影响，除了根，子树都反转 状态 4) 影响，子树反转

对于每个子树的每个状态，我们枚举所有操作组合，求小答案即可。

比赛的时候，我人肉梳理出了 4*8=32 中情况，即写了这么多 if/else。

赛后，推导了下状态转移方程，发现不难。
如果我比赛推导公式的话，应该排名更靠前一些。

// 001 根反转
// 010 子树反转
// 100 父子反转
int Dfs(TreeNode* root, const int flag) {
  if (root == nullptr) return 0;
  if (h[flag].count(root))  return h[flag][root];
  int& ret = h[flag][root]  = INT_MAX;
  int preOne = __builtin_popcount(flag);
  for (int mask = 0; mask < 8; mask++) {
    const int one = __builtin_popcount(mask);
    if ((one + preOne + root->val) % 2 == 1) continue;  // 奇偶性判断
    const int child = ((mask ^ flag) & 2) | (mask >> 2);
    ret = min(ret, one + Dfs(root->left, child) + Dfs(root->right, child));
  }
  return ret;
}

五、舒适的湿度

题意：给一个数组，数字代表温度，可能是升高也可能是降低。
如果数字升高或降低的含义确定时，所有子区间的和的绝对值的最大值称为波动温度。
问数字的升高与降低组合序列中，可以得到的最小的波动温度是多少。

思路：题意理解起来比较麻烦，其实就是求最大值中的最小值。
即有两个条件，条件1确定时，所有的条件2可以得到一个最大值。
现在求所有条件1里面，条件2得到的最大值的最小值。

对于这种题型，典型的做法是二分答案，判断这个答案是否成立。

在想怎么二分之前，我们先看下暴力做这道题需要怎么做。
从前到后，对于每个数字，与前缀得到的集合相加与相减，不考虑数据值的范围，得到的不同值可能就是 2^n 个。

题目中可以看到，数字最多 1000个，值的范围是 [1,1000]。
可以证明，答案不会超过 2000, 即不会超过两个最大值。

这样，数据范围就降低到 2000 以内了。
这样复杂度也降低到 n^2 了。

六、最后

这次比赛题目挺好的。

第一题动态规划。
第二题都不算图论。
第三题矩阵记忆化搜索。
第四题树上DP。 第五题二分+动态规划。

最后一题我已经证明最优值不会大于 1n了，如果能想到二分的话，我应该应该就可以做出来了。
不过这道题确实有难度，没做出来也没有遗憾。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code