leetcode 第 343 场算法比赛

零、背景

五一假期去成都旅游了，，所以就没参加周赛。

找时间做了一下题，分享下题解。

一、保龄球游戏的获胜者

题意：告诉你保龄球的计分规则，问两个选手谁赢。
计分规则：如果强两个球至少有一个满分，则当前得分翻倍。

思路：按照题意判断计算即可。

小技巧：记录最近一次的满分为止，可以更方便判断。

二、找出叠涂元素

题意：矩阵的每个方格中有不同的数字灯，现在给一个序列，代表打开数字灯的顺序。
问第几个灯亮时，第一次出现某行或者某列灯全亮。

思路：

1）预处理出每个数组对应的矩阵坐标。
2）维护两个数组，代表各行和各列亮灯的个数。
3）以此打开灯，更新行数组和列数组，并判断是否都亮了。

三、前往目标的最小代价

题意：现在有一个坐标，坐标之间移动时间等于曼哈顿距离。
现在给你虫洞，从一个坐标传送到另外一个坐标有一定的时间成本，问从起点到达终点的最短时间是多少。

思路：单源最短路。

每个虫洞坐标、起点、终点的坐标离散化为图中的顶点，构造出一个有向完全图，边都等于曼哈顿距离。
对于虫洞，如果距离更短，则更新对应的有向边。

然后跑最短路即可。

四、字典序最小的美丽字符串

题意：给一个美丽字符串 S，求一个字典序大于S的美丽字符串，如果存在多个，输出字典序最小的那个。
美丽字符串：字母由前 k 个字母组成，子串不能存在长度大于 1 的回文串。

思路：枚举+贪心。

1）由于是求字典序最小，所以需要让前缀尽量的不变。
枚举前缀的长度，有大到小，判断是否存在答案，存在即找到最优答案。

2）前缀固定后，由于需要满足字典序大于 S，所以前缀之后的第一位的字符需要大于 S。
可以从小到大枚举所有字符，且需要满足不存在回文串。

3）前缀+第一个字符确定后，，贪心构造之后的字符即可。

贪心依据：由于前缀不存在回文子串，所以接下来的字符只需要判断是否与前两个字符相等即可。

如下图，假设前缀的最后三个字符是 abc，则接下来的字符不能是 c，也不能是 b，可以是其他任意字符。

abc
abcc
abcb
cbca

所以我们通过前两个字符，就可以确定接下里最小字符是什么。
上面的贪心过程也可以证明，字符个数大于 3 个时，贪心肯定存在答案。

复杂度分析：虽然是枚举，但一旦存在答案，就可以马上计算出答案，如果不存在答案，也可以马上确定不存在答案。
复杂度：O(n)

五、最后

这次比赛题目比较简单。

明天又是周日了，我可以正常参加比赛了。
明天下午还是春季团队赛，我也可以参加比赛。
之前春季个人赛，我一直没时间写解题报告，下周看有没有时间写吧。

《完》

-EOF-

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