leetcode 第 409 场算法比赛

零、背景

这次比赛前三题难度还好，第四题难度就大多了。
当然，不是说大家想不到算法，而是边界很多，很容易遗漏边界。

A: 值映射位置。
B: 最短路。
C: 贪心+区间合并。
D: 线段树+模拟。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/409

一、设计相邻元素求和服务

题意：给一个值互不相同的矩阵，输入一个值，问所在位置上下左右相邻位置的元素之和 与 上下左右四个斜角位置的元素之和。

思路：hash 维护值到坐标的关系，之后按题意找到值的位置，遍历四个方向求和即可。

小技巧：储存下四个方向的相对坐标，循环数组即可。

int adjacents[4][2] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
int diagonals[4][2] = { {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };

二、新增道路查询后的最短距离 I

题意：若干城市之间有一些道路，每个城市只与左右相邻的城市有一条道路。
给两种操作，操作1把两个城市相连，操作2问从第一个城市到最后一个城市的最短路。

思路：数据范围不大，构图，每次询问跑最短路即可。

三、新增道路查询后的最短距离 II

题意：若干城市之间有一些道路，每个城市只与左右相邻的城市有一条道路。
给两种操作，操作1把两个城市相连，操作2问从第一个城市到最后一个城市的最短路。
特殊限制：任何两个道路之间如果有交集，则只存在包含关系，不存在交叉。

思路：突破口就在特殊限制上。

假设已存在一个道路 [i,j], 这意味着从 i 可以直接跳到 j, 走[i,j]之内的城市和道路不会得到最优答案。
如果新加的道路[a,b]在 [i,j]之间，则为无效道路，因为不是最优答案。
如果新加的道路[a,b]覆盖 [i,j]， 则道路关系为 [a,i,j,b]，此时从 a 直接到 b 是最优的。

由此可以找到一个贪心方法：对于包含关系的道路，只储存最外层的道路，答案为最外层道路的个数。

实现：有序映射表储存最外层的道路。
新增一条道路后，判断道路是新的最外层还是被包含。
如果被包含，则什么都不操作。
如果是新的最外层，则删除所有包含的路径，然后插入新的路径。

复杂度：O(n log(n))

四、交替组 III

题意：给一个首位相连的数组，值为0和1。
给两个操作，如下：
操作1：询问交替子数组长度大于等于 K 的个数。
操作2：修改数组一个位置的值。
交替子数组：除了左右边界，中间任何相邻元素值都不同的子数组的长度。

思路：先不考虑修改操作，很容易想到方法。

假设从一个位置开始，存在长度为 L 的最长交替子数组。
则从第二个位置开始，必然存在长度为 L-1 的交替子数组。
依次递推，从前到后，交替子数组的长度依次递减。
题目是求大于等于 K 的子数组，所以长度 [L,K] 都满足， [K-1,0] 都不满足，这段区间内的答案就是 L-K+1 。

有了上面的规律，只需要找到一段最长交替子数组，则这段区间内为起始位置的答案为 sum(Li - K + 1) 。

假设最长交替子数组为 li 的有 ni 个，则答案如下：

 (vi - K + 1) * ni 
= vi * ni - (K - 1)* ni

多个长度累计之和公式如下：

 sum((vi - K + 1) * ni)
= sum(vi * ni) - (K - 1) * sum(ni)

很容易想到，sum(vi * ni) 和 sum(ni) 两个区间和可以使用线段树或树状数组来快速计算。

因此，我们可以预处理输入数组，求出所有最长交替子数组，储存在两个线段树里，即可在 log(n)的时间复杂度里查询答案了。

接下来思考修改操作。

首先需要维护所有最长交替子数组，然后修改时动态维护这个最长交替子数组。

修改一个位置的值，根据位置与所在最长交替子数组的关系分几种情况：

1）在交替数组中间，例如 010 修改为 000，则需要分裂为多个交替子数组。
2）在边界，例如 000 修改为 010，则左右两个交替子数组会发生变化。

3个位置的二进制，则有 8 种情况。
如果你想要分情况讨论，会发现又会与左右第二个值有关系，这样就是5个位置，这样就有 32 种情况。
而且还要考虑整个环都是交替子数组的情况。

所以，如果你比赛时分情况讨论，会发现会有无数的样例让你的枚举不通过。

针对这种情况，我想到一种暴力方法：提前将三个位置拆分为独立的最长交替子数组，然后枚举三个位置，判断是否可以合并为更大的交替子数组。

// 向后合并
if (IsConnect(nextIndex)) {
  Connect(nextIndex);
}

// 向前合并
if (IsConnect(preIndex)) {
  Connect(preIndex);
}

if (IsConnect(index)) {
  Connect(index);
}

通过这个方法，判断的情况就由 32 种减少为 3 种。

五、最后

这次比赛第二题最短路，第三题找规律，第四题线段树+大模拟。

你是怎么做最后一题的？
如果你的想法是枚举所有情况，应该会提交不通过无数次，通过未通过的样例，发现漏了很多种情况。
而如果不去枚举具体的值，直接枚举左右是否新增或合并交替数组，则只有三种情况，会简单很多。

《完》

-EOF-

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