leetcode 第 278 场算法比赛

零、背景

这次比赛题目其实还好，但是我想复杂了，最终翻车了。

赛后总结出几个经验，分享给大家。

一、将找到的值乘以 2

题意：给一个数组和目标数字。
有一个操作：如果目标数字在数组中，目标数字的值就翻倍。
这样不断的操作后，问目标数字的值是多少。

思路：数组中的值储存到 hash map 中，不断查找，存在则翻倍。

二、分组得分最高的所有下标

题意：给一个 01 数组，给一个下标，可以将数组拆分为左右两部分。
这个下标的得分是左部 0 的个数与右部 1 的个数之和。
求最大得分。

思路：预先统计 1 的总个数，然后循环累计 0 的个数，计算出临时答案，取最大值即可。

小技巧：由于是 01 数组，可以通过求和代替计数，代码会简单一些。

三、查找给定哈希值的子串

题意：给一个字符串，求第一个长度为 k 的连续子串，其 hash 值是 hashValue。
哈希算法：sum(v[i] * p^i)%m

思路：我一开始从前到后推论，发现需要使用除法逆元。

但是我很多年没使用除法逆元了，就试了下暴力计算，果然超时了，我就跳过这道题了。

赛后，发现大部分人是从后到前计算的，这样就不需要除法逆元了。

当然，也有几个人从前到后计算，不过没有计算逆元，而是给目标 hash 值乘以对应的 p。
这个思路挺不错的。

四、字符串分组

题意：给一个字符串数组，每个字符串总的字符只出现一次。
如果一个字符串可以转换到另外一个字符串，则两个字符串需要划分到一个分组内。

转换规则有三个：删除任意一个字母、增加任意一个字母，替换任意一个字母。

问最终的分组数，以及最大分组中字符串的个数。

思路：

字符串中字母只出现一次，意味着可以使用 bit 位压缩为整数来表示一个字符串。
两个字符串可以放进一个分组意味着两个字符串之间有一条边。
最终的分组数就是图的连通分支个数。

所以，这道题可以分三步来做：bit 位压缩、建图、DFS 求解。

当然，建图的时候我没做有优化，有重复边，导致超时一次。
后面建图时增加标记位屏蔽掉重复边后，就通过了。

赛后，看有人把建图与DFS求解合并了，这样就不存在重复边了。
这个思路不错。

五、最后

这次比赛翻车了，赛后想了想，总结出下面几个经验。

经验一：
对于第三题，我想到除法逆元后准备放弃前，应该看下榜单。
如果过的人多，说明这道题有简单的方法。
这样就可以再换个思路想一想，可能就可以快速通过了。

经验二：
还是第三题，把除法转化为乘法，就是目标也乘以一个数字。
这个算是逆向思维，很有意思的想法。

经验三：建图与搜索求解合并。
建图会存在大量的重复边。
求解需要防止重复计算。
防止重复计算的过程中，就可以把重复边过滤掉。
这个方法也学习到了。

当然，我第三题使用逆元还没有通过这道题。
你觉得使用逆元可以做这道题吗？
如果有问题，是哪里的问题呢？

《完》

-EOF-

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