leetcode 第 222 场算法比赛

零、背景

继续参加 leetcode 的周赛，最后一题没能做出来，脑子不行了。

相关源代码： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/222

一、卡车上的最大单元数

题意：箱子有几种类型，每个类型的箱子有若干个单元数量。
现在给出每个类型箱子的个数以及最多可以选择的箱子数量，求最大单元数量。

思路：按单元数排序，优先取单元数大的小子即可。

二、大餐计数

题意：如果两个数字之和是 2 的幂，则称为一组完美匹配。
给若干个数字，求完美匹配的组数。

思路：类似于 leetcode 的第一题，预先统计计数，然后枚举判断所有幂，判断是否存在一个数字可以相加得到。

注意事项：如果一个数字恰好是幂的一半时，应该减一。

坑：计数我使用的 map，被卡超时了。改成unordered_map 即可。

三、将数组分成三个子数组的方案数

题意：给一个数组，分割成连续的三段：前缀、中缀、后缀。
如果前缀和小于等于中缀和，中缀和小于等于后缀和，则成为一个完美分割。
问存在多少组完美分割。

思路：首先是枚举后缀，然后二分找到最小的合法前缀和最大的合法前缀，中间都是合法的，相减就可以得到当前枚举值的答案个数。 复杂度：O(n log(n))

坑：答案很大，使用 long long，记得取模。

四、得到子序列的最少操作次数

题意：给一个数值互不相同的数组 target， 以及一个数组 arr。
现在可以在 arr 中任意的插入若干数字。
问最少插入多少个数字，才能让 target 是 arr 的子序列。

思路：直接看这道题的话，是最长公共子序列。
复杂度O(n^2)，会超时。

此时可以猜到，突破口就在与 target 的值是互不相同的。

而且，arr 中，不存在与 target 的数字也是不相关的，可以直接预处理删除掉。
这样插入操作满足子序列时， arr 的数字就和 target 完全一样了（不考虑重复数字）。

比赛期间，我想到这里就没思路了。

赛后，发现对 target 做等价置换重新编号，问题就转化为了求 arr 的最长递增子序列 LIS 问题。
而最长递增子序列有 O(n log(n))的算法，套模板即可。

对于 LIS 问题，使用线段树很容易理解 O(n log(n)) 算法。

定义 dp(i) 是以 i 为后缀的最长递增子序列。
则 dp(i) = max(dp(j) + 1), val[j]<val[i]。

使用线段树离散化维护所有 val，查询queryMax(1, val[i]-1) 即可。

传统的方法是 dp 加二分查找，理解起来有点难度。
dp(i) 定义为长度为i且最后一个值最小的子序列。

根据这个定义，可以推出一个很难理解的特征来。

假设处理了前 k 个数字，最长子序列是 j。

1、dp[1, j] 数组是连续有值的。
2、dp[1, j] 数组满足递增单调的。

有了这个推论，对于第 k+1 个数字，我们就可以更新 dp 数组了。

如果 val[k+1] > dp[j]，以为这当前数字大于最长子序列的最后一个值，可以得到更长的子序列。
从而得到 dp[j+1]=val[k+1]

否则，val[k+1] 肯定可以作为某个 dp 对应子序列最后一个元素。
也就是 val[k+1] 肯定是 dp[i] 的最优值。

这意味着 dp[i-1] < val[k+1] <= old_dp[i]。
这个结论很难理解，不过可以使用反证法来证明。

可以使用反证法来证明这个结论。

前提条件，dp[i-1] < val[k+1]。
假设val[k+1] 是 dp[i] 的子序列后缀，但不是最小的。
则说明 dp[k+1] > old_dp[i]。
此时，val[k+1]将不会是 dp[i]的子序列后缀，而是dp[i+1]的子序列后缀了。

假设不成立，所以val[k+1] 一定是 dp[i] 的最小后缀。

五、最后

这次比赛的题还不错，不过自己思路跟不上了。
这周开始，要早点休息，上个月睡眠严重不足，猝死的节奏。

加油，算法人。

《完》

-EOF-

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