LeetCode 刷题笔记——day 7
9. 回文数
难度：简单
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
代码语言：javascript复制输入：x = 121
输出：true示例 2：
代码语言：javascript复制输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3：
代码语言：javascript复制输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。示例 4：
代码语言：javascript复制输入：x = -101
输出：false提示：
-231 <= x <= 231 - 1
**进阶：**你能不将整数转为字符串来解决这个问题吗？
我的答案
代码语言：javascript复制思路 首先，根据题目来看，负数肯定不会是回文数，所以可以在第一步直接排除，后面直接判断非负数即可。这里将题给数放进了整形数组中（题目的进阶要求为不将整数转为字符串来解决，所以这里转为了整型数组， վ’ᴗ’ ի ），然后依次遍历前半部分同时与后半部分相比较，存在不同则直接输出
false，剩下的就是回文数了。
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.MAXtext{int.MAX}int.MAX，我们将遇到整数溢出问题。 按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转inttext{int}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 复现了一遍：
代码语言：javascript复制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 ：
代码语言：javascript复制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：
代码语言：javascript复制输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。示例 2:
代码语言：javascript复制输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：
代码语言：javascript复制输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。示例 4：
代码语言：javascript复制输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5：
代码语言：javascript复制输入：s = "mississippi" p = "mis*is*p*."
输出：false提示：
1 <= s.length <= 201 <= p.length <= 30s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
很好，所以 正则表达式 是什么？
正则表达式，又称规则表达式。（英语：Regular Expression，在代码中常简写为 regex 、regexp 或 RE），计算机科学的一个概念。正则表达式通常被用来检索、替换那些符合某个模式(规则)的文本。 正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。 —— 百度百科
似懂非懂，附上 正则表达式手册 ，先把题目做了吧。
我的答案
代码语言：javascript复制思路 利用二维数组
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组的值。因此在循环体中需要添加以下代码：
if(ch == '*') {
a[i][0] = a[i - 2][0];
}代码语言：javascript复制完成以上则确定的二维数组的初始状况，接下来开始分步具体考虑。 如果
字符规律p被读取的字符为'.'，则只需要保证在此之前的两段字符串相匹配即可，即以下代码：
a[i][j] = a[i - 1][j - 1];代码语言：javascript复制而如果读取的字符为
'小写字母'，则只需要保证当前位字母相同且之前位都相匹配，即以下代码：
a[i][j] = ch == s[j - 1] && a[i - 1][j - 1];代码语言：javascript复制最后若读取到的字符为
'*'时，就需要分两种情况考虑。因为'*'可以表示零或多个前一位字符，这里分别考虑表示零和多位时的情况。 表示零位，则保证在 字符'*'的前方第二位处之前两段字符串匹配即可，即以下代码：
a[i][j] = a[i - 2][j]代码语言：javascript复制表示多位，则保证 字符
'*'之前的一位之前两段字符串相匹配即可，特别的，若前位为'.'，则不需判断相同以匹配，因为'.*'可与任意端字符串相匹配，即以下代码：
a[i][j] = a[i][j - 1] && (p[i - 2] == '.' || p[i - 2] == s[j - 1]);
代码语言：javascript复制通过以上步骤，二维数组的最大位
a[p.size()][s.size()]即为整体匹配的结果。
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
第一次自己写这么长的一段题解，主要的原因还是对分析过程还是不算特别熟悉。我并没有用过类似的方法，这道题本来用的一维数组，最终无路可走，能用二维数组分析至此，还是参考了网友的方法。就现阶段来说，这道题目于我实在还是太难了。说来惭愧，计算机专业学生今天第一次接触正则表达式。
官方答案
动态规划
思路与算法
如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了s 中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：字母 星号的组合在匹配的过程中，本质上只会有两种情况： 匹配s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配； 不匹配字符，将该组合扔掉，不再进行匹配。 如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：
作者：LeetCode-Solution
用 c 实现了以下官方解法：
代码语言：javascript复制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
这里需要特别注意：
代码语言：javascript复制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 <= 201 <= p.length <= 30s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
貌似相互矛盾了，实测 s 和 p 确实不能为空，但是，我自己的代码考虑了，也就是说，力扣对我的代码测试也许并不全面，我的代码也许存在 bug ~ 先放着吧，问题不大。
继续练习以下用 Java 来实现：
代码语言：javascript复制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
总结 第十题可有点太复杂了~
