leetcode 第 385 场算法比赛

零、背景

今天大年初九，我休假还没回深圳上班。

一大早起床带我爸去了一趟医院，回来看还有时间，就参加了比赛，排名 45。

最后一题又是字符串题，我又使用字符串 hash 算法通过了。

A: 暴力循环判断。
B: 字典树。
C: 枚举。
D: 字符串hash。

一、统计前后缀下标对 I

题意：给一个字符串数组，问存在多少字符串对，满足前面的字符串同时是后面字符串的前缀和后缀。

思路：数据量不大，暴力枚举所有字符串对，判断是否满足前缀和后缀关系。
复杂度：O(n^2*L)

二、最长公共前缀的长度

题意：两个数组分别选两个数字，会有一个公共前缀，求最长公共前缀的长度。

思路1：字典树。
对一个数组构造字典上，然后另一个数组枚举查询最长公共前缀。

思路2：前缀集合。
一个数组的所有前缀集合储存起来，然后另一个是这样枚举前缀集合进行判断。
数字的前缀不超过 10 个，空间大小翻 10 倍可以接受。

思路3：字符串数组排序+二分查找。
在《第133场比赛》题解中，我提到可以使用字符串排序加二分查找来代替字典表。

本质区别是数组没压缩公共前缀，而字典树压缩了公共前缀。

三、出现频率最高的素数

题意：给一个数字矩阵，求矩阵的直线路径组成的数字中，出现频率最高的、大于 10的素数。

思路：枚举所有路径，统计素数的频率，然后寻找最大频率即可。

四、统计前后缀下标对 II

题意：与第一题一样，数据范围变大。

数据范围：字符串个数 10^5 个，字符串字符总个数 10^5个。

思路：由于字符串个数比较多，不能枚举所有字符串对，只能判断确定一个字符串后，另一个字符串有多少个满足要求。

确定的字符串有两种方法，一种是确定左边的字符串，另一种事确定右边的字符串。

确定左边的字符串，需要对右边的所有字符串预处理，并统计出每个字符串前后缀相等时，对应前缀对应的字符串个数。
前缀的个数与字符个数相等，故字符串个数为10^5，直接储存字符串空间会爆炸，所以需要储存字符串的 hash 值。

确定右边的字符串，则需要对左边的所有字符串预处理，统计每个字符串出现的频率。
之后枚举右边字符串的所有前缀与后缀，相等时，查找前面出现的频率。
每个字符串储存一次，空间复杂度与输入一致。

难点：如何在 O(1)的复杂度里判断前缀与后缀是否相等。
显然，使用 hash 预处理的话，就可以直接O(1)判断了。

五、最后

这次比赛第二题其实蛮有难度的，有三种解法。
最后一题则需要使用大家都很熟悉的 hash 算法来判断两个字符串是否相等。

《完》

-EOF-

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