leetcode 第 230 场算法比赛

零、背景

这次比赛的题目有点难度。

同一道题，可以做的方法很多，而我每道题都想到的是最复杂的那个方法。
最后题目没有做完。

源代码：

https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/2/230

一、5689. 统计匹配检索规则的物品数量

题目：给一个数组，每个元素有三个属性：类型、颜色、名字。
现在给一个属性类型和属性值，问匹配这个属性类型的元素有多少个。

思路：循环判断即可。

小技巧：工程上，面对比较多的 if/else 又类似的时候，可以使用表格驱动来优化。

int ans = 0;
map<string, int> m = { {"type", 0}, {"color", 1}, {"name", 2} };
for(auto& v: items){
    if(v[m[ruleKey]] == ruleValue){
        ans++;
    }
}
return ans;

二、5690. 最接近目标价格的甜点成本

题意：制作冰淇淋需要一种原材料和若干辅助材料，要求每类辅助材料至多选两份。
现在有 n 类原材料 和 m 类辅助材料每份的成本。
问怎么组合，才能配制出离目标成本 t 最近的冰淇淋。

如果存在多种方案，选择成年最低的那种。

思路：

第一个方法是暴力枚举。
由于原材料和辅助材料最多不超过 10 个，直接枚举也不会超时

细节：三层循环，第一层循环枚举原材料，第二次循环枚举辅助材料的子集，第三次循环依旧枚举辅助辅助材料的子集。
枚举复杂度：O(n * 2^m * 2^m)

优化： 其实对于选与不选，是经典的背包问题。

这里的不同点时，组合出来的成本允许超过目标成本 t。
这是，我们把目标 t 翻倍出来，这样组合出来的背包成本就永远小于目标成本了。

通过背包算法运行之后，对于任意成本，可以求出不超过这个成本且离这个成本最近的成本。
然后O(N)算法从所有的组合成本里寻找最优成本即可。

其实这个背包算法的结果与上面的枚举方法一样，都是得到所有可能的组合大小。
不过这里通过动态算法的思想，避免重复运算了。

复杂度：O(n * V)

三、5691. 通过最少操作次数使数组的和相等

题意：给两个数组，每个数组里的值都是1~6。
问是否可以通过修改数组的值，使得两个数组值之和相等，如果可以，输出最小修改次数。

思路：

首先，需要判断是否存在答案。
如果较短的数组全部设置为6，较长的数组全部设置为1，短数组之和依旧小于长数组，则不存在答案。

逻辑也很简单，不做修改次数限制，看两个数组可以得到的最大值与最小值。
如果有交集，就可以让两个数组相等，没交集就不能相等。
而短数组的区间偏左一些，长数组的区间偏右一些，所以直接判断左区间的最大值与右区间的最小值即可。

如果存在答案，接下来要判断的是怎么确定要修改谁。

方法一：二分。

显然，大于最优答案的次数都是满足情况的。
所以我首先想到的方法是二分，即枚举操作次数。
这样问题就转化为了判断一个操作次数是否是答案。

接着，我枚举第一个数字操作次数 p1，剩下的就是第二个数组操作次数 p2。
并计算出两个数组各自的操作次数下，对应的数组和区间。

可以证明，每个数组在固定操作次数下，可以得到的数组和区间是连续的。

所以，如果两个区间有交集，则说明有答案，否则没有到答案。

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

方法二、双指针。

第一个方法已经说了，可以证明指定的操作次数可以得到连续的区间。
那能不能直接根据这个连续区间的性质来直接计算呢？

具体来说就是，假设第一个数组小于第二个数组。

当两个数组和差距很大时，第一个数组最优的操作是数字 1 改变成数字 6，第二个数组反之，是数字 6 变成数字 1。
总结下就是，数组差值很大时，选择操作差值最大的数组，这样就可以通过一次操作使得数组和的差距尽量小。

数组和差距很小时呢？
会不会一不小心第一个数组大于第二个数组呢？
没关系，这时候最后一次操作不做最大差值变更，按数组和的差距变更即可。

由此，我们就可以通过这个区间连续性的方法，每次从左右选择变更值更大的那个，来找到答案。

复杂度：O(n)

小技巧：不要排序，直接统计出1~6的数据即可得到有序数组。

四、5692. 车队 II

题意：给 n 辆车的位置和速度。
如果后面的一辆车遇到前面的那辆车，后面的那辆车的速度就会和前面那辆车相等。
求每辆车追上前面那辆车的时间，如果追不上，输出 -1。

思路：

简单分析，发现车辆追上后存在合并的情况。
这个专业名称叫做并查集，不过这里是特殊的并查集，即两个相邻区间的合并。

方法一：暴力查找

一种朴素的思路是，不断的找到可以追尾的那辆车，找到一个答案，然后合并。

复杂度：O(n^2)

方法二：线段树

暴力查找之所以慢，是为了循环找到下一个追尾的车。
如果我们预先计算好每辆车追尾的时间，这样就可以通过某种数据结构快速找到那辆车了。

找到一辆车后，不仅要合并到后面的车，还需要更新前面那辆车的追尾时间。
这个使用朴素的优先队列不可行，所以我选择线段树来做这道题了。

大概思路：

-）计算每辆车与下辆车的追尾时间
-）通过查询，找到最小时间以及车的编号 posb，得到一个答案。
-）追尾的车 posb 与后面的车 posc 合并（此时，posb 的追尾时间与 posc 保持一致，区间修改posb ）。 -）追尾的车 posb 之前的车 posa 需要重新计算追尾时间（与 posc 追尾， 区间修改posa 的追尾时间）。

可以看到，posa、posb、posc代表的是一个区间。
区间的左边界和右边界都通过并查集来维护。
这样就可以找到真实的上一辆车和下一辆车了。

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

方法三：优先队列

上面提到，在查找最值的时候可以使用优先队列。
但是这道题除了取出最值外，还涉及修改队列里的元素。

那怎么修改队列里的元素呢？
答案是修改后的元素再加入优先队列，而对于已存在的值，打个标记，忽略即可。

打标记的方法很多，比如每辆车进入队列时，分配一个编号。
要删除队列里的这辆车了，就把这个编号标记一下，然后给这辆车分配新的编号即可。

当然，对于每辆车其实有一个天然的标号：追尾的车。

还是以posa、posb、posc距离。
posb和posc追尾了，posb这辆车就要删除。
posa原先要追尾的车是posb，现在变成posc了。

所以我们只需要标记posb已经删除了，这样优先队列里的posa-posb二元组就可以识别出来了。

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

方法四：单调栈

如果再分析下这道题的特征，会发现前面的车是否追尾永远不影响后面的车。
也就是，任意取一个后缀，答案都是固定不变的。

所以我们可以尝试从后到前来推导这道题。

还是以posa、posb、posc为例。

情况一： 最后一辆车posc

-）对于posc ，作为最后一辆车，肯定不会追尾。

情况二：倒数第二辆车posb

-）如果posb的速度小于等于posc，则永远不会与 posc追尾。删除最后一个元素，回到情况一。
-）如果 posb 的速度大于posc，则肯定可以追尾，追尾时间可以计算出来，而且也是固定的。

情况三：倒数第三辆车 posa

此时可以保证前面有两辆车，且posb > posc，即会追尾。

-）如果posa 的速度小于等于 posb，则肯定是 posb 与 posc先追尾。
此时 posb 没有意义，删除 posb，回到请二。

-）如果posa的速度大于 posb，则可能posa先追尾，也可能posb先追尾。
如果 posb 先追尾，则删除posa回到状况二。
否则，posa先追尾，但是还不能删除，因为可能后面的车会先撞 posa。

就这样，我们维护了一个从后到前的单调栈。
不管进行这样的三种情况的模拟，就可以从后到前计算出所有车追尾的时间了。

复杂度：O(n)

五、最后

这次比赛有点难度。

第二题就是 0/1 背包动态规划，当然，暴力也可以做。
第三题则是双指针，或者二分搜索。
第四题的方法就多了，暴力、线段树、优先队列、单调栈。

对于后三题，建议大家都做下。

最后一题我写了几百行的线段树+并查集，没想到一个单调栈就搞定了。
果然是自己太弱了。

加油，算法人。

《完》

-EOF-

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