leetcode 第 402 场算法比赛

零、背景

这次比赛都不难，最后一题线段树，不过合手速慢了，排名比较靠后

A: 暴力枚举。
B: 分组统计。
C: 动态规划。
D: 线段树。

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

一、构成整天的下标对数目 I

题意：给一个数组，问两两组合，有多少对数字和是 24 的倍数。

思路1：数据范围不大时，暴力枚举所有组合。

思路2：数据范围较大时，所有元素对 24 取模分组。
取模值为 0 和 12 的，只能在分组内任意选两个，组成答案 C(k, 2)。
其他情况，取模值为 a 的，只能与取模值为 24-a 的组成答案，两个分组两两组合就是分组大小相乘。

二、构成整天的下标对数目 II

题意：与第一题一样，数据范围变大。

思路：参考第一题的分组算法。

三、施咒的最大总伤害

题意：给一个数组，如果选择了值为 v 的元素，则不能选择 v-2,v-1,v+1,v+2 元素。
问如何选择，才能使得选择的元素和最大。

思路：动态规划。

可以发现几个特征。

特征1：选择只关心值，不关心顺序。
所以可以对值进行排序。

特征2：相同元素，如果选择一个，其他的肯定全部选择。
所以需要对元素进行合并去重，统计个数。

特征3：如果从小到大选择，我们值关心前面两个元素。
所以题目可以修改为选择 v，不能再选择 v-1,v-2。

状态：f(v) 值小于等于 v 时的最优值。

方程：f(v) = max(f(v-1), v + f(v-3))
解释：分为选择与不选择。

空间优化：
值的数据范围是 10^9，储存不下。
不过我们只需要储存每个值的答案，通过比较值，找到第一个小于等于 v-3的位置。

新的方程：f(n) = max(f(n-1), nums[n] + f(pos_v_3))

另外可以发现，方程只关心最近四个连续值，使用滚动数组保留最近4个位置元素的答案。

四、数组中的峰值

题目：给一个数组，有两个操作：

操作1：查询区间峰值的个数。
操作2：修改一个元素的值。

峰值定义：一个位置大于左右相邻元素时，当前元素称为峰值。

思路：单点更新，区间查询，典型的单点更新线段树。

不过这道题合并子区间时，边界可能产生新的峰值，所以需要特殊处理。

特殊处理1：数组整体右移，使得左右边界都是最大值，从而不需要特殊处理最大值和最小值边界。

特殊处理2：合并子区间时，中间可能会有峰值，需要记录中间的位置，比较是否有新的峰值。

合并后产生峰值的条件：

条件1：左右区间都不为空。
条件2：左区间的右边界是峰值，或者右区间的左边界是峰值。

针对这两个条件，特殊判断即可。

五、最后

这次比赛后，发现我的模板都缺少使用样例。
所以先对线段树模板更新了下，补充了使用样例。
后面遇到一个算法，就更新一个算法模板的使用样例吧。

线段树模板与使用样例如下：

https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/seg/segUpdateOne.cpp

《完》

-EOF-

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