leetcode 第 285 场算法比赛

零、背景

这次比赛又翻车了。

想了下，有两方面原因。

第一是昨天周六连续参加了多场比赛，睡得比较晚，起得比较早，没休息好。

第二是自己脑子不止怎么想的，非常裸的单点更新线段树模板题，我自己非要自己实现一套区间操作的的数据结构。

自己实现的数据结构调试了一个小时，最终才通过。
赛后使用线段树模板，几分钟就通过了。

其实，整个比赛期间，脑子都不对劲，所有题都选择了困难的算法。

一、统计数组中峰和谷的数量

题意：给一个数组，求峰顶与谷底的个数。

注意事项：连续的值相等的峰顶和谷地算一个。

思路：

方法一：先循环一遍，预处理数据，删除相邻重复的数字。
之后再循环一遍，判断是不是峰顶与谷底即可。

方法二：我觉得预处理需要开辟空间，于是尝试使用标记位来做，这样就可以做到 O(1) 的空间了。

由于有重复值比较麻烦，调试了好久，最终修改成维护一个非单调栈来做。

非单调栈就是栈中任意连续三个值不单调，即栈中的值肯定是一个峰顶挨着一个谷底。
最终答案肯定就是栈中的元素减 2 了。

赛后回顾的时候，我也想不明白自己为啥不选择方法一，无脑循环两边好了。

二、统计道路上的碰撞次数

题意：给 n 练车的运行状态：左运行、右运行、静止。

车辆会按下面规则相撞，并得到对应的积分。

-）左运行 与 右运行的车面对面相撞后，状态会转化为静止，积分加 2。
-）左运行 或者 右运行 的车撞到静止的车时，状态也会转化为静止，积分加 1。

求最终的积分。

思路：

方法一：循环两边法。

除了最左边朝左运行的车和最右边朝右运行的车，中间的车肯定会相撞。
所以预处理左右边界，之后扫描两边中间的区间。

第一遍遇到非停止的车就加 1 分。
第二遍遇到左右面对面的车就加 1 分，算是补上漏算的分。

方法二：状态机。

记录上一个车的状态，判断当前车的状态。
需要写八九个判断条件。

比赛的时候，我就是使用状态机的方法，敲了十几分钟。

三、射箭比赛中的最大得分

题意：A 和 B 射箭比赛， 都射了 N 箭。

有 12 个箭靶，区域编号分别是 0~11。
对于某个区域，谁射的箭多，谁就可以赢得区域编号对应的积分。

现在告诉你 B 在 12 个区域的命中数量，问 A 如何射箭，才能得到最高积分。
输出 A 获得最高积分时，在各个区域的命中数量。

思路：

方法一：动态规划。

我第一时间想到的丁动态规划。

状态：f(n, m) n 个箭射前 m 个区域的最高得分。

状态转移方程：

当前状态分两种：

-）放弃，则不射箭，得分为 0。
-）赢比赛，比对手多射一箭，得分为 m。

f(n, m) = max(f(n, m-1), m + f(n - v[m] - 1, m - 1) )

所有状态计算出来后，再逆向遍历状态计算出路径即可。

方法二：二进制枚举。

既然只有 12 个区域，二进制枚举 A 哪些区域赢了，判断能不能赢，更新积分即可。

点评：比赛的时候没想到二进制枚举，这个无脑循环即可。

思考题1：如果问题修改为让 A 与 B 的积分差 A - B 尽量大又该如何做呢？

思考题2：如果问题修改为让 A 与 B 的积分差绝对值 |A-B| 尽量小，又该如何做呢？

四、由单个字符重复的最长子字符串

题意：给一个字符串，以及若干个修改。
每次会修改字符串中一个位置的值。
问每次修改后，字符串中最长连续等值子串的长度。

思路：

看了一眼题目，我就想到两个方法：线段树模板题 或者 构造数据结构。

最近我在整理最新的算法模板。
由于还没整理道线段树题，所以我决定自己构造数据结构来做这道题。

没想到自此走入不归路，直到比赛也没调试出来（写错一个地方）。
比赛后找到之前整理的线段树模板，贴进去修改了几下，就过了。
套用模板，很快，我有点崩溃。

方法一：单点更新线段树。

是的，这道题甚至不需要延迟标记。
而且查询是整个区间，只需要写一个PushUp 函数就可以了。

节点需要保存的状态：

-）左边界的字符与最长等值前缀长度。
-）右边界的字符与最长等值后缀的长度。
-）当前区间的最长等值连续子串。

如果是叶子节点，字母肯定就是叶子的值，三个长度都是 1。
非叶子节点，分五种情况合并左右儿子。

-）左右儿子无法合并
-）可以合并，且左右儿子字符全部相等
-）可以合并，左儿子的字符全部相等，与右儿子的左边界合并
-）可以合并，右儿子的字符全部相等，与左儿子的右边界合并 -）可以合并，其他情况，中间的边界合并，但不影响左右边界

实现了 PushUp 函数，其他的都是模板，套用即可。

方法二：构造数据结构。

构造的数据结构需要满足下面结构条件。

-）能够求出当前最长线段
-）修改一个线段的之后，能够更新线段。

对于最长的线段，可以使用优先队列或者 map 实现。
比赛的时候，我使用的优先队列，赛后发现 map 更简单一些。

这里最难的在于更新线段，分几种情况。

-）更新一个点时，需要找到对应的线段，然后进行线段拆分，并修改。
-）之后的线段，如果可以合并（修改的是线段的边界），需要进行线段合并。

使用 map 维护线段区间。
之前我在文章《leetcode上的几个区间题》分享过。

而对于线段的维护，就是删除旧线段，加入新线段。
区间的维护挺繁琐的，需要判断一堆边界。

五、最后

这次比赛每道题都有多种方法，每道题我都选择了困难模式。

前两题两边循环即可解决问题，我硬是使用状态机，写了一堆条件判断。
第三题二进制枚举即可，我使用带路径的动态规划，复杂点，但还好。
第四题线段树模板题，我自己维护区间，又写了一堆条件判断。

由此看来，以后做题的时候，如果一堆条件判断可以做时，先思考下是否可以通过其他方法通过。
毕竟，写一堆条件判断很浪费时间，还很容易漏掉，从而导致 WA 吧。

加油，算法人。

《完》

-EOF-

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