LeetCode 刷题笔记——day 7

9. 回文数

难度：简单

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

1
2
输入：x = 121
输出：true

示例 2：

1
2
3
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

1
2
3
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：

1
2
输入：x = -101
输出：false

提示：

  • -231 <= x <= 231 - 1

**进阶：**你能不将整数转为字符串来解决这个问题吗？

我的答案

思路

首先，根据题目来看，负数肯定不会是回文数，所以可以在第一步直接排除，后面直接判断非负数即可。这里将题给数放进了整形数组中（题目的进阶要求为不将整数转为字符串来解决，所以这里转为了整型数组， վ’ᴗ’ ի ），然后依次遍历前半部分同时与后半部分相比较，存在不同则直接输出 false ，剩下的就是回文数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        vector<int> a;
        int i = 0;
        for(; x > 0; i++) {
            a.push_back(x % 10);
            x /= 10;
        }
        for(int j = 0; j < i / 2; j++) {
            if(a[j] != a[i - j - 1]) return false;
        }
        return true;
    }
};

  • 执行用时: 16 ms

  • 内存消耗: 9.4 MB

难得写了一个零 bug 的程序而且一遍过，可喜可贺可喜可贺，虽然只是一道简单题……

不过程序还存在一个问题，整形数组占用的空间反而比字符串要多得多，这里只是实在想不到不用字符串怎么解才使用整型数组……

接下来还是看看官方给的答案：

官方答案

反转一半数字

思路

映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。

第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。
但是，如果反转后的数字大于int.MAX\text{int.MAX}，我们将遇到整数溢出问题。

按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转int\text{int} 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

算法

首先，我们应该处理一些临界情况。所有负数都不可能是回文，例如：-123 不是回文，因为 - 不等于 3。所以我们可以对所有负数返回 false。除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字返回 false。

现在，让我们来考虑如何反转后半部分的数字。

对于数字 1221，如果执行 1221 % 10，我们将得到最后一位数字 1，要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以 10 的余数，122 % 10 = 2，就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。

现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？

由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。

作者：LeetCode-Solution

用 C++ 复现了一遍：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || (x % 10 == 0 && x != 0)) return false;
        int num = 0;
        while(x > num) {
            num = num * 10 + x % 10;
            x /= 10;
        }

        return x == num || x == num / 10;
    }
};

  • 执行用时: 4 ms

  • 内存消耗: 5.9 MB

学到了学到了~

继续练习一下 Java ：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0 || (x % 10 == 0 && x != 0)) return false;
        int num = 0;
        while(x > num) {
            num = num * 10 + x % 10;
            x /= 10;
        }

        return x == num || x == num / 10;
    }
}

  • 执行用时: 4 ms

  • 内存消耗: 37.8 MB

对了，代码比较简单，只用到了最基本的语法，所以 Java 和 C++ 的代码是一样的。

10. 正则表达式匹配

难度：困难

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

1
2
3
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

1
2
3
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

1
2
3
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

1
2
输入：s = "mississippi" p = "mis*is*p*."
输出：false

提示：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 30
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

很好，所以 正则表达式 是什么？

​ 正则表达式，又称规则表达式。（英语：Regular Expression，在代码中常简写为 regex 、regexp 或 RE），计算机科学的一个概念。正则表达式通常被用来检索、替换那些符合某个模式(规则)的文本。

​ 正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。

—— 百度百科

似懂非懂，附上 正则表达式手册 ，先把题目做了吧。

我的答案

思路

利用二维数组 a[x][y]，其中 x 和 y 分别表示字符在 字符规律p 以及 字符串s 中的位置序号。数组类型为 bool，若值为 true 则说明 字符串s 前 y 位与 字符规律p 的前 x 位相匹配。

首先，a[0][0] 为 true ，而 x 或 y 为 0 的其他项为 false，因为 x 与 y 不同时为 0 时不匹配。但是，有一种特殊情况，若 y=0 而 字符规律p 的前两位为 X* （X 表示除 * 以外符合条件的任意字符）时，此时相匹配，则 a[2][0] 为 true。而这种情况也会影响到后面 y=0 组的值。因此在循环体中需要添加以下代码：

1
2
3
if(ch == '*') {
	a[i][0] = a[i - 2][0];
}

完成以上则确定的二维数组的初始状况，接下来开始分步具体考虑。

如果 字符规律p 被读取的字符为 '.'，则只需要保证在此之前的两段字符串相匹配即可，即以下代码：

1
a[i][j] = a[i - 1][j - 1];

而如果读取的字符为 '小写字母' ，则只需要保证当前位字母相同且之前位都相匹配，即以下代码：

1
a[i][j] = ch == s[j - 1] && a[i - 1][j - 1];

最后若读取到的字符为 '*' 时，就需要分两种情况考虑。因为 '*' 可以表示零或多个前一位字符，这里分别考虑表示零和多位时的情况。

  • 表示零位，则保证在 字符'*' 的前方第二位处之前两段字符串匹配即可，即以下代码：

    1
    a[i][j] = a[i - 2][j]

  • 表示多位，则保证 字符'*' 之前的一位之前两段字符串相匹配即可，特别的，若前位为 '.' ，则不需判断相同以匹配，因为 '.*' 可与任意端字符串相匹配，即以下代码：

    1
    a[i][j] = a[i][j - 1] && (p[i - 2] == '.' || p[i - 2] == s[j - 1]);

通过以上步骤，二维数组的最大位 a[p.size()][s.size()] 即为整体匹配的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        bool a[n + 1][m + 1];

        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                a[i][j] = false;
            }
        }
        a[0][0] = true;
        for(int i = 1; i <= n; i++) {
            char ch = p[i - 1];
            if(ch == '*') {
                a[i][0] = a[i - 2][0];
            }
            for(int j = 1; j <= m; j++) {
                if(ch == '.') {
                    a[i][j] = a[i - 1][j - 1];
                } else if(ch == '*') {
                    a[i][j] = a[i - 2][j] || a[i][j - 1] && (p[i - 2] == '.' || p[i - 2] == s[j - 1]);
                } else {
                    a[i][j] = ch == s[j - 1] && a[i - 1][j - 1];
                }
            }
        }

        return a[n][m];
    }
};

  • 执行用时: 4 ms

  • 内存消耗: 6.2 MB

第一次自己写这么长的一段题解，主要的原因还是对分析过程还是不算特别熟悉。我并没有用过类似的方法，这道题本来用的一维数组，最终无路可走，能用二维数组分析至此，还是参考了网友的方法。就现阶段来说，这道题目于我实在还是太难了。说来惭愧，计算机专业学生今天第一次接触正则表达式。

官方答案

动态规划

思路与算法

题目中的匹配是一个「逐步匹配」的过程：我们每次从字符串pp 中取出一个字符或者「字符 + 星号」的组合，并在ss 中进行匹配。对于pp 中一个字符而言，它只能在ss 中匹配一个字符，匹配的方法具有唯一性；而对于pp 中字符 + 星号的组合而言，它可以在ss 中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。

我们用f[i][j]f[i][j] 表示ss 的前ii 个字符与pp 中的前jj 个字符是否能够匹配。在进行状态转移时，我们考虑pp 的第jj 个字符的匹配情况：

如果pp 的第jj 个字符是一个小写字母，那么我们必须在ss 中匹配一个相同的小写字母，即

f[i][j]={f[i−1][j−1],s[i]=p[j]false,s[i]≠p[j]f[i][j] = \begin{cases} f[i - 1][j - 1], & s[i] = p[j]\\ \text{false}, & s[i] \neq p[j] \end{cases}

也就是说，如果ss 的第ii 个字符与pp 的第jj 个字符不相同，那么无法进行匹配；否则我们可以匹配两个字符串的最后一个字符，完整的匹配结果取决于两个字符串前面的部分。

如果pp 的第jj 个字符是 *，那么就表示我们可以对pp 的第j−1j−1 个字符匹配任意自然数次。在匹配00 次的情况下，我们有

f[i][j]=f[i][j−2]f[i][j] = f[i][j - 2]

也就是我们「浪费」了一个字符 + 星号的组合，没有匹配任何ss 中的字符。

在匹配1,2,3,⋯1,2,3, \cdots 次的情况下，类似地我们有

如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了ss 中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：字母 + 星号的组合在匹配的过程中，本质上只会有两种情况：

匹配ss 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；

不匹配字符，将该组合扔掉，不再进行匹配。

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：

f[i][j]={f[i−1][j] or f[i][j−2],s[i]=p[j−1]f[i][j−2],s[i]≠p[j−1]f[i][j] = \begin{cases} f[i - 1][j] \text{~or~} f[i][j - 2], & s[i] = p[j - 1] \\ f[i][j - 2], & s[i] \neq p[j - 1] \end{cases}

在任意情况下，只要p[j]p[j] 是 .，那么p[j]p[j] 一定成功匹配ss 中的任意一个小写字母。

最终的状态转移方程如下：

其中matches(x,y)\textit{matches}(x, y) 判断两个字符是否匹配的辅助函数。只有当yy 是 . 或者xx 和yy 本身相同时，这两个字符才会匹配。

细节

动态规划的边界条件为f[0][0]=truef[0][0] = \text{true}，即两个空字符串是可以匹配的。最终的答案即为f[m][n]f[m][n]，其中mm 和nn 分别是字符串ss 和pp 的长度。由于大部分语言中，字符串的字符下标是从00 开始的，因此在实现上面的状态转移方程时，需要注意状态中每一维下标与实际字符下标的对应关系。

在上面的状态转移方程中，如果字符串pp 中包含一个「字符 + 星号」的组合（例如 a*），那么在进行状态转移时，会先将 a 进行匹配（当p[j]p[j] 为 a 时），再将 a* 作为整体进行匹配（当p[j]p[j] 为 * 时）。然而，在题目描述中，我们必须将 a* 看成一个整体，因此将 a 进行匹配是不符合题目要求的。看来我们进行了额外的状态转移，这样会对最终的答案产生影响吗？这个问题留给读者进行思考。

作者：LeetCode-Solution

用 c++ 实现了以下官方解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();

        auto fn = [&](int i, int j) {
            if(i == 0) {
                return false;
            }
            if(p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };
        vector<vector<int>> a(m + 1, vector<int>(n + 1));
        a[0][0] = 1;
        for(int i = 0; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(p[j - 1] == '*') {
                    a[i][j] = a[i][j - 2];
                    if(fn(i, j - 1)) {
                        a[i][j] |= a[i - 1][j];
                    }
                }
                else {
                    if(fn(i, j)) {
                        a[i][j] = a[i - 1][j - 1];
                    }
                }
            }
        }
        return a[m][n];
    }
};

  • 执行用时: 4 ms

  • 内存消耗: 7 MB

这里需要特别注意：

1
2
3
if(fn(i, j - 1)) {
	a[i][j] |= a[i - 1][j];
}

在此之前已经执行过 a[i][j] = a[i][j - 2]; ，所以 a[i][j] 的取值将与 a[i][j - 2] 有关，因此这里使用位运算进行赋值：a[i][j] |= a[i - 1][j]; 。

此外，在题干中有如下提示：

提示：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 30
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

貌似相互矛盾了，实测 s 和 p 确实不能为空，但是，我自己的代码考虑了，也就是说，力扣对我的代码测试也许并不全面，我的代码也许存在 bug ~ 先放着吧，问题不大。

继续练习以下用 Java 来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();

        boolean[][] a = new boolean[m + 1][n + 1];
        a[0][0] = true;
        for(int i = 0; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(p.charAt(j - 1) == '*') {
                    a[i][j] = a[i][j - 2];
                    if(fn(s, p, i, j - 1)) {
                        a[i][j] |= a[i - 1][j];
                    }
                } else {
                    if(fn(s, p, i, j)) {
                        a[i][j] = a[i - 1][j - 1];
                    }
                }
            }
        }
        return a[m][n];
    }
    public boolean fn(String s, String p, int i, int j) {
        if(i == 0) {
            return false;
        }
        if(p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

  • 执行用时: 1 ms

  • 内存消耗: 37 MB

总结

第十题可有点太复杂了~