Leetcode 第 158 场比赛回顾

作者: | 更新日期:

动态规划题型其实很简单,就是递归记忆化搜索。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

零、背景

十一国庆飞回家了,所以没参加比赛,这周继续。

可能周末只有一天的缘故,一大早起来都没睡醒,比赛就开始了。
还好,这次比赛比较简单,在比赛前全部都做出来了。

不过由于头脑不清晰,有很多地方敲错了,导致 WA 了几次。
尤其是最后一道题,有很多细节。建议大家做做这道题。

一、分割平衡字符串

题意:给一个平衡字符串,问同时可以拆分为多少个子字串,子字串都是平衡字符串。
平衡字符串定义:只有两个字母,且出现次数相等。

思路:从前到后分别统计两个字母出现的次数即可,次数相等时,就可以拆分一个。
证明:原字符串是一个平衡字符串,找到一个平衡字符串前缀时,对应的后缀肯定也是平衡字符串。 所以可以从前到后贪心统计划分。

时间复杂度:O(n)
空间复杂度:O(1)

二、皇后攻击国王

题意:给一个8*8的棋盘,有一个国王和若干王后,问可以一步攻击到国王的王后个数。
规则:王后横、直、斜都可以走,但是不能跳过其他棋子。

思路:考虑上下左右以及四个斜线,共有 8 个方向。
由于王后不能跳过棋子,所以答案肯定在[0,8]之间。

第一个方法是枚举国王的这八个方向,看是否可以遇到王后。
第二个方法是枚举所有王后,根据两个棋子的位置看是否在攻击方向上,在了再判断当前方向是否有其他棋子挡路。

由于第二个方法需要作出大量判断,建议使用第一个方法。

三、有限制的掷骰子

题意:每次骰子可以随机的得到1~6这些数字。
现在需要掷n次骰子,但是每个数字连续出现的次数有个最大限制。
问此时,可能出现的数字序列有多少个。

思路:典型的动态规划题。

假设当前是起始状态,此时前面是没有依赖,我们可以随机n次。
掷一次骰子后,可能出现6个数字其中一个,而下个状态就和前面出现的数字和次数有依赖了,即前面的数字出现的次数需要保存下来。

这里的状态定义为f(k, index, n),代表数字index在前面出现k次时,再掷n次骰子会出现多少序列。
那么总答案就是:

ans += f(1, 1, n-1) 
ans += f(1, 2, n-1)
ans += f(1, 3, n-1)
ans += f(1, 4, n-1)
ans += f(1, 5, n-1)
ans += f(1, 6, n-1)

那对于有依赖的状态,大概分四种情况。

情况一:n等于0了,此时不能掷骰子了,确定一个序列,找到一个答案。
情况二:随机出的数字newIndexindex无关,那么得到新的状态f(1, newIndex, n-1)
情况三:随机出当前index,但是还没到达限制,那么得到新状态f(k+1, index, n-1)
情况四:随机出当前index,但是到达限制,忽略这个状态。

汇总一下就是下面的状态转移方程:

f(k, index, n) = 五个 f(1, newindex, n) + 一个合法的f(k+1, index, n-1)

PS:大家不要纠结这是动态规划还是记忆化搜索了,两个都是,没有冲突的。
动态规划是一种拆分子问题的思想,记忆化搜索是这种思想的递归实现。

四、最大相等频率

题意:给一个数组,问是否存在某个前缀,删除一个元素后,剩余的元素按值分组个数相等。
如果存在,返回最大的前缀长度。

思路:起初看到整道题,惊呼这么简单的题怎么是最后一题呢。
做了之后才发现,这道题有毒,需要考虑很多边界,也需要优化时间复杂度。

这道题的处理流程很简单,枚举所有前缀,判断是否是满足要求。
那什么时候是答案呢?

大概分几种情况:

情况一:只出现一个数字,显然是答案。

7 7 7 7 7

情况二:出现很多数字,但是都次数都是1。

7
8
9

情况三:只有一个数字出现一次,其他都出现多次,且次数相等。

6
7 7 7
8 8 8
9 9 9

情况四:所有数字都出现多次,但是大多数次数都相等,只有一个特殊多了一次。

7 7 7 7
8 8 8
9 9 9

能想到这里,一般这道题就可以考虑到所有边界,从而不会 WA 了。
但是还会超时。

因为我们是枚举每个前缀的O(n),每个前缀又需要进行分组,复杂度O(n),合起来就是O(n^2)的复杂度了。

那该怎么优化呢?
前缀是一个好的模式,因为前缀n和前缀n+1是有关系的。
我们计算前缀n+1时,完全可以想办法利用上前缀n的计算结果,从而避免重复计算。
所以优化方式就是,维护一个前缀分组。

时间复杂度:O(n log(n)) PS:每次用到map的时候,就会有人提到可以使用hash map,时间复杂度是O(1)的。 这里大家不要纠结这个了。

五、最后

这次比赛的题相对来说还算简单,都是我擅长的数据结构题。
你学会了吗?

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越