Leetcode 第 162 场比赛回顾

零、背景

上周说 leetcode 大放水，没想到这次放的水更大了。

上次的题还有一定的门槛，这次的题就啥门槛了，全部无脑暴力求解即可。

面对这种题，我敲代码速度这么慢，没啥优势。
等我练习打字出师了，这种比赛半个小时就可以搞定吧。

下面来看看这几道题吧。

PS：在最前面先说一个事，上次发起了一个樊登读书VIP的抽奖活动，中奖人员是“无双”，看到了可以微信联系我（微信在文末）。

一、奇数值单元格的数目

题意：给一个全0矩阵以及一个索引数组。

索引数组的值是一个二元组(r, c)，代表将矩阵的第r行都加一，第c行也都加一。
注意，此时(r, c)这个坐标的值加了两次。

求索引全部执行之后，矩阵的坐标中，值是奇数的个数。

思路：

第一个方法就是按照题意暴力计算矩阵，最后遍历矩阵统计个数。
复杂度分析：最耗时的是索引处理，时间为索引 * 行数 * 列数。
所以复杂度为 O(n^3)。

第二个方法就是预处理统计出每行与每列分别需要加几。

行加奇数次，列加偶数次时，对应的坐标结果是奇数。
行是偶数次，列是奇数次时，对应的坐标结果也是奇数，
其他情况坐标的值都是偶数。

所以答案就是偶数的个数乘以奇数的个数。
复杂度分析：索引、行、列都是遍历一遍。
复杂度：O(n)

二、构造二进制矩阵

题意：有一个2*n的二进制0/1矩阵，告诉我们每一行1的总个数和每一列1的总个数。
问能够构造出这个二进制矩阵。

思路：

首先，所有行1的个数应该和所有列1的个数相等。
所以第一步是检查行与列1的总个数是否匹配。

第二步，可以先一列一列的看。

如果这一列1的个数是2个，那每一行的值都需要是1。
如果这一列1的个数是1个，则可能第一行是1，也可能第二行是1。
如果这一列1的个数是0个，那每一行的值都必须是0。

此时对于个数是2时，可以确定每一行都是1。
如果某些行1的个数小于2的个数，那显然是不符合要求的。

比如我们宣称有三列的和都是2，然后说第一行只有一个1。
三列的和都是2可以判断每一行1的个数至少是3，小于3则说明不能构造出矩阵来。

所以可以先把2的情况处理了，每处理一个2，所有行都应该减1。

第三步，此时每一列最多只有一个1。
由于所有行的总和与所有列的总和是匹配的，所以怎么分配都是存在答案的。
贪心的做法就是优先分配第一行，第一行分配完了再分配第二行。

三、封闭岛屿的数目

题意：给一个二维矩阵，0代表陆地，1代表海洋。
四条边与大陆相连，矩阵中相邻的陆地属于一个小岛，问小岛的数量有多少个

思路：典型的搜索题。

由于四边的小岛不算，所以可以优先处理掉。
之后不断的DFS寻找下一个小岛即可。

复杂度：O(n^2)

四、得分最高的单词集合

题意：给一些单词和一些字母（有重复），每个字母有一个得分。
每个字母只能使用一次，问最终可以组成哪些单词，使得得分最高。

比如我们有三个单词ak, bk, ck， 五个字母a,b,c,k,k。
a有1分
b有2分
c有3分
k有4分
最终我们肯定选择bk和ck使得得分是2+4 + 3+4。

思路：这道题是典型的动态规划题。
可是状态我们没法储存，位压缩也不行。

我们之前提到过，大部分动态规划就是搜索加状态记忆化。
既然状态不能储存，我能就暴力的搜索吧。

那怎么搜索呢？
对于每个单词，我们可以选择组成这个单词，也可以不组成这个单词。
组成时，字母集合就需要删除使用过的字母，搜索完后删除的字母再加回来。

由此，就完成了搜索，标准的深度优先搜索。
你只要做过类似的题，应该都可以敲出来。

那复杂度呢？
数据量只有14个，暴力也就2^14，不会超时。

当然，我做这道题的时候，做了很多优化。
比如预先计算出每个单词的分数，以及每个单词的字母组成。
除此之外，我还做了位优化，用来快速判断一个单词需要的字母是不是都有（个数够不够另外判断）。

最后，我把这些优化都删除了，这道题竟然也过了。
过早优化是万恶之源。

当然，对于选与不选，另一种容易理解的方法是使用二进制。
不过我更喜欢递归实现。

五、最后

这次比赛题出的太简单，都属于各种算法的最简单题型。

也许是双十一了，leetcode 想给大家一个礼物，出了四道简单题。

不过，我不喜欢这样的题型。

-EOF-

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