leetcode 第 357 场算法比赛

零、背景

这场比赛去长沙旅游，没有参加，现在补上题解。

一、故障键盘

题意：给一个小写字母字符串，遇到字母 i 会导致前面的字符串反转。
问最终字符串是什么。

思路1：模拟，遇到字母 i 反转字符串即可。
复杂度: O(n^2)

思路2: 离线逆向处理 正向处理，我们无法确定一个字符在答案中的位置。
逆向处理，遇到的字符在答案中的位置就是固定的。

没有遇到 i，则遇到字母的顺序不变，放在最后即可。
遇到了 i，前面的字母需要反转，所以遇到的字母需要反转，放在最前面。

所以维护一个前缀和后缀 buf，逆序计算出答案即可。

复杂度：O(n)

二、判断是否能拆分数组

题意：给一个数组，每次操作可以选择一个数组，拆分为两个子数组。
拆分条件是要么子数组大小为1，要么子数组的元素和大于等于m。
问是否可以把数组全部拆分为大小为1的子数组。

思路1：动态规划
状态定义：f(l,r) 代表数组[l,r]是否可以全部拆分为大小为1的子数组。

状态转移方程：f(l,r) = sum(l,r)>=m && f(l,i) && f(i+1, r) 方程的含义为是否存在一个 i，使得左边子数组和右边子数组都有答案。
复杂度：O(n^3)

边界：输入时，数组大小为1和2时，肯定存在答案，特殊处理。

思路2：贪心

数组大小为1和2时，肯定存在答案，特殊处理。

对于数组大小大于2的情况。
假设存在答案，最后一个拆分的数组是[i,i+1]。
则肯定有 sum(i,i+1)>=m。

从而可以推导出所有前缀数组的元素和一级以及所有后缀数组的元素和都满足要求。

sum(i-1,i+1)>=m
sum(i-2,i+1)>=m
sum(1,i+1)>=m

sum(i,i+2)>=m
sum(i,i+3)>=m
...
sum(i,n)>=m

根据上面的前缀和后缀，我们就可以拆分出答案。

因此，循环数组判断相邻元素和是否大于等于 m 即可。
复杂度：O(n)

三、找出最安全路径

题意：给一个矩阵，某些坐标有一个小偷，值为1。其他坐标为空，值为0。
现在需要寻找一个左上角到右下角的路径，使得路径的安全系数最大。
路径的安全系数定义：路径上所有点到最近小偷的曼哈顿距离的最小值。

思路：搜索题。

第一步：BFS 搜索计算出所有坐标的安全系数。
第二步：优先队列搜索计算出所有坐标为终点时，路径的最大安全系数。

总结：两边搜索即可。

四、子序列最大优雅度

题意：给一个数组，元素有一个值和品类。
现在需要选择 k 个元素，使得优雅度最大。
优雅度定义：元素值之和 加上 不同品类的平方。

思路：

第一想法是贪心选择最大的 k 个元素，此时可以得到一个临时答案。
对于这个临时答案，某些品类可能选择了多次，而有些品类可能没有选择。

此时可以发现，如果对于选择多次的品类，少选择一次，用来选择没有选择过的品类，可能得到更优的答案。

少选一次，选择哪个呢?
显然是选择所有多次品类中元素值最小的那个。

选择没有选择过的品类，应该选择哪个呢？
显然是没有选择过的品类的元素中，元素值最大的那个。

所以可以维护两个数据结构来选择即可。

五、最后

这次比赛题有难度。
前两题都可以优化出O(N)算法。
后两题都不太好想。

你都是怎么做的呢？

《完》

-EOF-

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