Leetcode 第139场比赛回顾

零、背景

Leetcode 第139 场比赛的题目难度属于中等难度。

只可惜我的思维还是太慢，敲代码速度太慢，浪费不少时间。

最后一道题就差几分钟就敲完代码了，但是比赛结束了，然后以提交，就过了。

接下来就看看看这四道题吧。

一、字符串的最大公因子

题意：问是否存在一个子串，是输入两个串的重复子串（无交集）。

思路： 这道题直接暴力从大到小枚举判断即可。

但是我犯了算法洁癖症，想着最优解，浪费不少时间。

比如我的方法是：

第一步：对两个串的长度求 GCD，答案肯定小于等于GCD。

第二步：枚举所有小于GCD的数字，判断是否分别是两个串的重复子串。

而且在判断是不是重复子串时，可以使用 MOD 来快速判断（是的话需要能够 %MOD = 0 ）。

中间代码敲了一半时，我甚至想也许还可以用二分。

最后一看时间已经过了 15 分钟了，赶紧清空代码写了一个暴力算法把题过了。

二、按列翻转得到最大值等行数

题意：给一个 0/1 矩阵，可以翻转一些列，使得一些行的值全部相等。求最大的相等行数。

思路：可以发现，最终相等的行的值要么全是 0 ，要么全是 1 。

对于全是 0 的行，例如 line[i] 和 line[j] ，翻转某些列后，这些行依旧是相等的，即 line[i] = line[j] 。

对于全是 1 的行，同理，不管怎么翻转，这些行组成的数组都是相同数组。

对于 0 与 1 的行，最终每个位置应该都是相反的，那翻转列之前，每个位置也应该是相反的。

因此我们可以假设第 i 行是最终答案，然后统计和第 i 行完全相等以及完全相反的行数，然后求最大值。

这里我又犯了洁癖症，标准的方法是暴力做，复杂度是 O(n^2*m) 。

我的做法是预处理，对每一行数据序列化为字符串，然后使用 map 计数与查找，复杂度优化到了 O(n*m) ，只是我的时间都浪费了。

三、负二进制数相加

题意：给两个以 -2 为基数的数字，求两个数字之和。

思路：对于大整数加法，是有套路的。

第一步是翻转字符串，使得低位在前面，高位在后面。

第二步是高位补零。

第三步是相加。由于 -2 基数的特殊性，这里我们暂时不管进位问题。

第四步是处理进位逻辑。

第五步去前导零。

第六步翻转结果，即得到答案。

这里最关键的一步是如何处理进位。

如果当前位的值是 0 和 1 ，那就不需要处理。

如果当前位大于等于 2 ，且下一位大于 0 ，那么可以抵消，即 2*(-2)^k + (-2)^(k+1) = 0 。

如果当前位是 2 且下一位为0，则可以转化为后面两位的运算结果，即 2 * (-2)^k = (-2)^(k+1) + (-2)^(k+2) 。

证明：

当 k 是偶数时，最终结果是 2^(k+1) ，那公式展开 -2^(k+1) + 2^(k+2) = 2^(k+1) 。

当 k 是奇数时，最终结果是 -2^(k+1) ，那公式展开 2^(k+1) - 2^(k+2) = -2^(k+1) 。

由此，则可以完美的处理所有的进位了。

四、元素和为目标值的子矩阵数量

题意：给一个矩阵，问满足要求的子矩阵个数。

这里的要求是矩阵和等于给定的值。

思路：对于子矩阵问题，有一个万能的方法。

首先是枚举子矩阵的上面那条边，然后枚举矩阵的下面那条边，这个过程中，可以累积计算出每一列的值，目前复杂度 O(n^2) 。

这样，问题就转化为了有一个一维数组（列的累计值），求这个数组里面满足要求的子数组个数。

对于一维数组求子数组最优值，则需要具体情况具体分析了，但是复杂度不要超过 O(n^2) ，最优的是 O(n) ，次之是 O(n log(n)) 。

比如对于最大子矩阵和，就可以转化为最大子序列和，就是 O(n) 的复杂度算出最大序列和，综合就是 O(n^3) 。

这道题是求子序列和等于指定值的个数，那就只能统计前缀和 O(n) ，然后判断快速判断当前后缀是否存在答案了 O(log(n)) 。

具体来说，如果当前位置 now 为后缀的子序列 pre+1,...,now 是一个答案，则说明当前前缀 1,2,3,..., now 和减去前面的某个前缀和 1,2,...,pre 等于指定值。

反过来就是，当前前缀 1,2,3,..., now 减去指定值，存在某个 1,2,...,pre 等于这个差值。

、 这里使用 map 或者 hash_map 储存前缀和以及个数，然后查找差值是否存在，存在则找到一个答案。

五、最后

回头看看，这次比赛题挺好的，难度适中，大家花一些时间思考一下，做出三道题应该是没问题的。

四道题解在 leetcode 上我也分享了，刷题的朋友可以帮我点个赞，虽然我不知道 leetcode 上点赞有啥用。

地址：https://leetcode.com/tiankonguse/

-EOF-