leetcode 第 332 场算法比赛

零、背景

周六在研究一个算法，即尝试使用程序来破解一个桌游，并做成了网站，当然还没做完，做到很晚才睡。

今天比赛头有点懵，恰好比赛题目质量比较高，我就卡了很几次，做完的时候，比赛快结束了。

一、找出数组的串联值

题目：给一个数组，每次对收尾弹出的数字求串联值，最终所有串联值求和。

思路：按题意双指针首尾移动，计算串联值，求和即可。

二、统计公平数对的数目

题意：给一个数组，问存在多少个二元组的和在 [L,R] 区间内。

思路：数组排序，枚举一个数字，二分查找大于等于 L 和 大于 R 的个数，差值就是满足要求的，不过可能包含自身，特殊判断。

细节：假设第一个数字 l 确定了，则需要求所有的 r，使得满足 L<=l+r<=R。
转化一下就是 L-l<=r<=R-l，对 L-l 和 R-l 二分查找即可。

三、子字符串异或查询

题意：给一个二进制字符串，q 个询问 [v1, v2]，问是否存在二进制某个子串的十进制 v 满足 v ^ v1 == v2。
如果存在，求最靠左的子串位置。
数据范围：二进制字符串长度 n，一个数字的二进制长度为 m。

思路：先分析异或公式。

v^v1==v2 可以转化为 v=v1^v2。

故题意转化为了是否存在子串十进制是 v。

方案1：暴力子串查询
查询一次复杂度是 O(nm)，查询 q 个复杂度就是 O(nmq)。

方案2：KMP
查询一次复杂度：O(n+m)，查询 q 个复杂度 O(q*(m+n))
由于 q 和 n 都是 10^5，会超时。

方案3：字典树。
离线对所有查询的二进制建字典树，复杂度 O(q*m)。
然后枚举所有后缀，判断哪些字典树存在值，复杂度O(n * m)。
综合复杂度O(m * (q + n)), m 为二进制长度，不大于 32，故不会超时。

四、最少得分子序列

题意：给两个字符串 s 和 t，问 t 如何删除才满足是 s 的子序列。
删除得分是删除的最大下标与删除的最小下标的区间大小。
求最小删除得分。

思路：显然，删除的最大下标和最小下标之间的字符串都可以删除，不影响答案。
得分越小，删除区间的长度越小，故前缀和后缀之和长度越大。
故题意转化求最长的不相交的前缀和后缀，使得前缀和后缀组成的字符串是 s 的子序列。

贪心预处理前后缀与字符串的子序列匹配关系。

枚举所有前缀，二分查找后缀不相交的最大长度，更新答案即可。

五、最后

这次比赛难度比较大，第二题二分，第三题字典树，第四题二分，差点翻车。

这次比赛你做出几道题，都是怎么做的？

《完》

-EOF-

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