LeetCode解题报告（第二篇）

LeetCode是一个在线题库，收录了面试中常见的技术类题目，题目的方向涵盖算法、数据库、Shell等。我前几天用闲暇时间在LeetCode上刷了些题，于是写一系列博客来讨论其中比较有趣的题目。

不定期更新中：第一篇，第二篇

Maximal Square

题目的输入是这样的数组，表示一个黑白点阵图：

1 [
2     ['1', '0', '1', '0', '0'],
3     ['1', '0', '1', '1', '1'],
4     ['1', '1', '1', '1', '1'],
5     ['1', '0', '0', '1', '0']
6 ]

要求找到其中最大的由1填满的正方形，返回它的面积。上例中，我们可以找到边长为2的正方形，所以应该返回4。

由于这道题要求找正方形，“面积”其实是个障眼法——我们只需要求出最大边长，然后平方即可。

我们可以依次处理图像的两个维度。

首先处理横向维度。我们计算出“从当前位置向左看，连续有多少个1”：

1 [
2     [1, 0, 1, 0, 0],
3     [1, 0, 1, 2, 3],
4     [1, 2, 3, 4, 5],
5     [1, 0, 0, 1, 0]
6 ]

然后我们从右至左、从上至下处理纵向维度。

依次观察最后一竖列：

• 0：直接忽略；
• 3：如果正方形以这个点为右上角，那么它的边长不大于3，我们令这样的正方形为a；
• 5：正方形a最大边长依然是3；如果这个点是右上角，边长不大于5，令这样的正方形为b；a和b实际的最大边长此时都还未确定；
• 0：正方形a实际边长为2；正方形b实际边长为1。

倒数第二竖列：

• 0：忽略；
• 2：我们已经找到了一个边长为2的正方形，忽略；
• 4：如果这个点是右上角，边长不大于4，令这样的正方形为c；
• 1：正方形c实际边长为1。

另外，考虑到整个点阵图的边长限制，后两行已经不需要考虑，可以直接忽略。

倒数第三竖列，情况类似：

• 1：忽略；
• 1：忽略；
• 3：如果这个点是右上角，边长不大于3，令这样的正方形为d；
• 0：正方形d实际边长为1。

之后的点可以全部忽略，不赘述了。

我们得到了结果：最大的正方形边长为2，面积为4。

这道题中出了 这道题中 出现了由0和1组成的矩阵。如果读者曾经见过n皇后问题的位运算解法，应该会联想到它。

是的，我们可以如法炮制。

首先，当然是建立数组：

1 [
2     10100b,
3     10111b,
4     11111b,
5     10010b
6 ]

我们进行一种“折叠”操作。首先对相邻两行做与运算，形成新的数组：

1 [
2     10100b = 10100b & 10111b,
3     10111b = 10111b & 11111b,
4     10010b = 11111b & 10010b
5 ]

这样，我们就找出了所有的“上下两个点均为1”的情形。

然后将每个数与自己右移一位后的结果做与运算：

1 [
2     0000b = 10100b & 1010b,
3     0011b = 10111b & 1011b,
4     0000b = 10010b & 1001b
5 ]

这时，每个为1的位就代表一个边长为2的正方形。

同样，我们继续进行折叠操作，此时每个为1的位代表一个边长为3的正方形。一直重复折叠下去，直到整个数组的所有数都为0，我们就找到了最大的正方形。

Regular Expression Matching

这道题要求我们实现最基本的正则表达式功能：星号（重复）和点（通配符）。

1 /abc/ match 'abc'
2 /a*/ match 'aaa'
3 /.*/ match 'aabc'
4 /c*a*b/ match 'cccaab'
5 ...

学过编译原理的同学可能会想到标准的正则表达式实现方法，埋头去写自动机。但这题有更简单的思路——我们可以使用动态规划来实现。

以/c*a*b/匹配'cccaab'为例：

• 我们把正则表达式解析成一个数组[/c*/, /a*/, /b/]。
• 首先，持有一个集合state = {0}，表示下一个字符可以匹配的正则表达式内的位置。
• 读入第一个字符'c'。从state中取出0，正则表达式的0位置是/c*/，我们发现它可以匹配也可以不匹配，于是我们把0（匹配）和1（跳过）都加入state。现在state = {0, 1}。
• 跳过/c*/后我们来到了正则表达式中的/a*/，但它并不能匹配'c'，我们只能继续跳过它。而之后的’/b/’既不能匹配也不能跳过。因此，现在state = {0, 1, 2}。
• 读入第二个字符'c'。分别考察state中的0、1和2，更新state后依然是{0, 1, 2}。第三个字符同理。
• 读入第四个字符'a'，我们发现/c*/不能匹配了，于是更新state到{1, 2}。第五个字符同理。
• 读入第六个字符'b'，/a*/也能匹配了，而/b/可以匹配，因此state更新为{2, 3}。
• 此时，字符已经读完了，而state中也包含了指向正则表达式末尾的3，因此匹配成功。

这两道题相对来说并不困难，而解法较多。如果急于编码，可能会陷入不理想的解法中，反而浪费时间。“充分思考，然后动手”，正是LeetCode所鼓励的编程方式。