leetcode 第 408 场算法比赛

零、背景

这次比赛第三题和第四题都有点意思，需要思考一下才能想出算法。

A: 循环。
B: 素数判断。
C: 枚举+二分。
D: 联通性检查。

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

一、判断是否可以赢得数字游戏

题意：给一个数组，问所有一位数数字之和与所有二位数数字之和谁大。

思路：根据位数分别求和，判断即可。

二、统计不是特殊数字的数字数量

题意：给一个数字区间，问区间内不是 特殊数字 的特殊。
特殊数字：恰好存在三个因子的数字。

思路：

特殊数字有三个因子，排查自身和1，只剩下一个因子，说明这个因子是不可拆分的，即是素数。
所以特殊数字肯定是一个平方数，且这个平方因子是素数。

数据范围很大，直接枚举区间，必然超时。
不过根据特殊数字是平方数的特点，枚举所有平方数即可。
另外，需要判断平方因子是不是素数，就需要提前打好素数表。
复杂度：sqrt(N)

三、统计 1 显著的字符串的数量

题意：给一个二进制字符串，求显著的子串个数。
显著子串：子串中 1 的个数大于等于 0 的个数的平方。

思路：直接枚举所有子串，显然会超时。
显然，显著子串的定义是突破口，枚举 sqrt(N) 个 0 即可。

算法：先枚举子串的起始位置，再枚举前缀有 sqrt(N) 个0时，有多少个前缀是显著子串。

不妨设起始位置为 i，枚举的是第 k 个 0。

第一步：需要找到满足 k 个 0 的最小长度与最大长度，即满足要求的前缀区间 [L,R]。
这个可以预处理统计所有 0的位置，然后二分查找计算得到。

第二步：根据0的个数，计算最少需要多少个1，得到存在答案时的最短前缀 P，判断是否在第一步计算的前缀区间里。
如果存在，则存在答案，最短前缀之后的子串都满足答案 ans+=R-P+1。

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

优化：枚举 0 时，下一次枚举可以复用上一次枚举的位置，从而少一次二分查找。
复杂度：O(n sqrt(n))

常数优化：第二步求最短前缀时，如果不存在答案，大多数时候可以跳过很多 0。
逻辑：每多一个0，由于平方的缘故，最短前缀的长度会增加很多，对于0很多的case，可以快速跳过这些 0。

四、判断矩形的两个角落是否可达

题意：给一个矩阵和若干圆，问是否存在从矩阵左下角到矩阵右上角的路径。
路径要求：路径在矩阵内，且不经过圆的边缘。

思路：联通性检查。

分析圆与矩阵的关系，可以得到三个结论。

结论1：如果两个圆相交或者相切，则两个圆就是联通的，两个圆心之间形成的线段是无法通过的。

结论2：如果一个圆与矩阵相交或者相切，则圆心和矩阵垂直线的交点是联通的，交点与圆心形成的线段是无法通过的。

结论3：如果从矩阵左边或者上边开始，存在一个到矩阵下边或右边的路径，路径上的圆都是联通的，则显然这个路径将矩阵分割，不存在从左下角到达右上角路径了。

矩阵的左边或者上边定义为超源起点，矩阵的边或右边定义为超源终点。

则根据上面的三个结论，可以得知，如果超源起点到超源终点存在路径，则不存在答案，即判断超源的联通性。

算法：先预处理，构图，然后DFS或者并查集判断连通性即可。
复杂度：O(n^2)

五、最后

这次比赛第二提和第三题需要枚举平方数，第四题把几何题转化为图论题，质量还算不错。

《完》

-EOF-

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