leetcode 第 205 场算法比赛

零、背景

今天继续参加比赛，发现被虐了，最后一题没时间写了。

比赛过程中，可能没有心思吧，各种小错误。
更神奇的是第三题我 递归总是超时，最终最好递推才过的。

总的来说，这次比赛题型还是比较丰富的，有字符串题、简单计算题、动态规划题、图论题。

下面来看看这四道题吧。

一、替换所有的问号

题意：给一个小写字母和问号组成的字符串。求将问号转换为字符串，使得字符串相邻字母不相同。输出任意一组答案。

思路：由于每个字母只与左右两个字母相邻，可供选择的字母有 26 个，所以肯定存在答案。

具体方法可以贪心，即从左到右循环寻找最小的满足条件字母。

二、数的平方等于两数乘积的方法数

题意：给两个数组，问在一个数组中挑一个数字 a，在另外一个数组中挑两个数字 b 和 c，问满足 a*a==b*c 的组合数。

思路：与 leetcode 第一题两数之和的解题思路类似。
先使用一个 map 记录一个数组的数组，然后枚举 a*a/b，判断 c 是否存在即可。

注意事项：数字可能大于 int ，请使用 long long。

三、避免重复字母的最小删除成本

题意：给一个字符串以及删除每个位置字符的成本。
问使得字符串相邻字符不同的最小删除成本。

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

只需要看前 k 个字符串，对于第 k 个字符可以选择删与不删。
不删，则第 k-1 个字符与这个字符有关系。
删的话，与第 k 个字符有关系的字符会传递给第 k-1 个。

由于最后一个字符没有后续依赖字符，所以可以使用另外一个转移方程来表示。
当然，也可以枚举最后一个位置的 26 个字符，取最小值。

空间优化：由于第 k 个字符只与第 k-1 个字符有关系，可以使用滚动数组来储存状态。

四、保证图可完全遍历

题意：给一个无向图，有三种类型的边。

类型 1：只能由 Alice 遍历。
类型 2：只能由 Bob 遍历。
类型 3：Alice 和 Bob 都可以遍历。

问最多可以删除多少条边，使得 Alice 和 Bob 可以遍历所有节点。

思路：遍历所有节点，意味着这种类型的边至少可以构成一个树，使得图是连通图。

我们假设只有一个人，那这道题就是典型的图求最小生产树的问题了。
而对于图求最小生成树的问题，最经典的方法就是并查集了。
所以这道题也可以通过并查集来缩边实现。

由于类型3是万能边，这里需要先对类型3进行并查集缩边。

之后类型2和类型3的边完全没关系，单独进行并查集即可。

五、最后

这次比赛第三题我原先使用 dfs 写的，一会就写完了。
结果一提交，超时了，最后改成递推才过，这个时间卡的有点没意思了。

而最后一题，起初没想到使用并查集，想的是实实在在的缩边。
一想操作那么复杂，就不想写了，便去录腾讯微博相关的视频了。

现在已经录完视频并上传到 B 站了，微博也转发了，可以关注我的微博看视频吧。
我的微博是 tiankonguse 。
最近没时间写公众号了，我尝试在微博写短内容来打卡，欢迎围观。

其实回头看看视频也没啥意思，就是想使用视频见证一下历史，以后回忆的时候，知道自己至少曾经知道这么一回事。

就像电影《人工智能》里面机器人最后说的那句话：“I am … I was”。
我存在，我曾经存在。

思考题：第三题能使用贪心做吗？

《完》

-EOF-

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