leetcode 第 334 场算法比赛

零、背景

以后写代码的时候，一定要先想好。

之前总是看一眼题目就敲代码，敲了一半发现不可行，这样就浪费很多时间。

一、左右元素和的差值

题意：给一个数组，问所有位置的前缀和和后缀和的差的绝对值。

思路：预处理出前缀和，总和减前缀和就是后缀和，求差的绝对值即可。

PS：前缀和后缀求差，此时前缀和后缀是否包含当前元素无所谓了，很有意思的性质。

二、找出字符串的可整除数组

题意：给一个纯数字组成的字符串，问前缀字符串对应的数字是否能整除 m.

思路：取模运算有一个性质，数字加减若干个 mod 的倍数，不影响取模结果。

所以，边取模边判断是否能整除即可。

pre = (pre * 10 + v) % m  

三、求出最多标记下标

题意：给一个数组，问是否可以选择若干组不相关的下标，使得每组下标对于的值满足2 * nums[i] <= nums[j]。
问最多可以选出多少组。

思路：分析一下，如果答案为 k 组，则肯定是选择最小的 k 个数字和最大的 k 个数字进行匹对。

由此可以想到二分答案，判断是否满足匹配。

四、在网格图中访问一个格子的最少时间

题意：给一个网格，值代表访问网格的最小时间。
起点在左上角，每一秒必须上下左右选择一个方向进行移动，到达方格时时间大于网格的最小时间。
问是否可以到达右下角，可以的话求最小时间。

思路：如果起点可以出发移动一步，则来回移动，即可把时间变得无限大，从而到达右下角。
所以没有答案的条件是初始点无法起步。

方格有答案求最小值，典型的广度优先搜索。

不过在搜索之前需要先解决来回移动环的问题。

存在的环的原因是通过来回移动增大当前方格的时间，从而使得到达下个方格的时间满足最小时间这个条件。
对于网格，可以发现环的长度都是偶数，最小为 2。
所以来回移动到达下个方格的时间是可以计算出来的，即不断的加 2，直到满足条件。

于是，通过直接计算未来到达下个方格的最小时间，就可以消除广度优先搜索的环了。

五、最后

这次比赛题目其实也不难。

我也发现自己做题慢的一个原因：敲代码的时候没想好算法。

以后比赛，我做题前会先去想好算法，确认没问题了，再去敲代码。

这样应该可以节省很多时间吧。

《完》

-EOF-

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