leetcode 第 207 场算法比赛

零、背景

昨天周六，下午参加了 leetcode 的年度团队赛。
今天周日，上午参加了 Leetcode 的第 207 场周赛，下午参加了 ICPC 的网络赛。
晚上的第三次计蒜客算法比赛就不参加了，做不动了。

回头看看上午这场周赛，其实题目都比较基础。
下面来看看这四道题吧。

一、重新排列单词间的空格

题意：给一个内有空格的字符串，空格将字符串分割为若干个子字符串。
请调整空格的位置，使得这些子字符串之间的空格相等且尽量多，剩余的空格放在字符串最后。

题意：按空格分隔字符串，并统计空格的个数，计算出字符串之间的空格数量，剩余的追加到最后面。

二、拆分子字符串数目最多

题意：将一个字符串拆分为若干不同的子字符串，求最多可以拆分多少个。

思路：第一眼看到这道题会不会做，因为暴力搜索的话复杂度太高。
再看看数据范围，字符串长度最长为 16， 暴搜即可。

三、矩阵的最大非负积

题意：给一个矩阵，从左上角到右下角找一条路线，使得乘积最大。如果最大乘积为负数，输出 -1。

思路：典型的动态规划题。
由于存在负数，每个位置需要计算一个最大正值和最小负值。这样最小负值可以负负得正得到最大正直。

四、连通两组点的最小成本

题意：给两个集合 A 和 B，以及两个集合间任意两点连线的代价。
问 A 集合的任意一点都与 B 集合有至少一条连线，B 集合的任意一点都与 A 集合有至少一条连线的最小代价。

思路：与第二题类似，一看只能暴力搜索，带会超时。
再看下数据范围，集合的点只有 12 个。
因此可以使用状态压缩，一个数字就可以代表当前集合选了哪些点。

状态定义 f(n, flag) 为A集合里前 n 个点与 B 集合 flag 点连线的最低代价。
flag 定义：位压缩形式，第 i 位值为 1 代表连线，0 代表没连线。

状态转移：枚举前 n-1 个点的 flag1，剩下的 flag2 就是第 n 个点要连的。
如果 flag2 为 0，那么第 n 个点只需要在 flag 里面找一个代价最小的点连线即可。

五、最后

这次比赛都是基础题，第二题就是枚举搜索，后两题都是动态规划。

没其他的补充了。

思考题：这些题你都是怎么做的呢？

《完》

-EOF-

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