目录
第6题. ZigZag Conversion
1. 题目描述（中等难度）
2. 解法一
3. 解法二
4. 总结
第7题. Reverse Integer
1. 题目描述（简单难度）
2. 总结
第8题: String to Integer
题目描述（中等难度）
总结
第9题: Palindrome Number
题目描述（简单难度）
解法一
解法二
解法三
总结
第10题 :Regular Expression Matching
题目描述（困难难度）
解法一 递归
解法二 动态规划
总
喜欢 请点个 + 关注
第6题. ZigZag Conversion
1. 题目描述（中等难度）
就是给定一个字符串，然后按写竖着的 「z」的方式排列字符，就是下边的样子。
然后按行的方式输出每个字符，第 0 行，第 1 行，第 2 行 …
2. 解法一
按照写 Z 的过程，遍历每个字符，然后将字符存到对应的行中。用 goingDown 保存当前的遍历方向，如果遍历到两端，就改变方向。
public String convert(String s, int numRows) { if (numRows == 1) return s; List<StringBuilder> rows = new ArrayList<>(); for (int i = 0; i < Math.min(numRows, s.length()); i++) rows.add(new StringBuilder()); int curRow = 0; boolean goingDown = false; for (char c : s.toCharArray()) { rows.get(curRow).append(c); if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; //遍历到两端，改变方向 curRow += goingDown ? 1 : -1; } StringBuilder ret = new StringBuilder(); for (StringBuilder row : rows) ret.append(row); return ret.toString(); }
时间复杂度：O（n），n 是字符串的长度。
空间复杂度：O（n），保存每个字符需要的空间。
3. 解法二
找出按 Z 形排列后字符的规律，然后直接保存起来。
我们可以看到，图形其实是有周期的，0，1，2 … 7 总过 8 个，然后就又开始重复相同的路径。周期的计算就是 cycleLen = 2 × numRows - 2 = 2 × 5 - 2 = 8 个。
我们发现第 0 行和最后一行一个周期内有一个字符，所以第一个字符下标是 0 ，第二个字符下标是 0 + cycleLen = 8，第三个字符下标是 8 + cycleLen = 16 。
其他行都是两个字符。
第 1 个字符和第 0 行的规律是一样的。
第 2 个字符其实就是下一个周期的第 0 行的下标减去当前行。什么意思呢？
我们求一下第 1 行第 1 个周期内的第 2 个字符，下一个周期的第 0 行的下标是 8 ，减去当前行 1 ，就是 7 了。
我们求一下第 1 行第 2 个而周期内的第 2 个字符，下一个周期的第 0 行的下标是 16 ，减去当前行 1 ，就是 15 了。
我们求一下第 2 行第 1 个周期内的第 2 个字符，下一个周期的第 0 行的下标是 8 ，减去当前行 2 ，就是 6 了。
当然期间一定要保证下标小于 n ，防止越界。
可以写代码了。
public String convert(String s, int numRows) { if (numRows == 1) return s; StringBuilder ret = new StringBuilder(); int n = s.length(); int cycleLen = 2 * numRows - 2; for (int i = 0; i < numRows; i++) { for (int j = 0; j + i < n; j += cycleLen) { //每次加一个周期 ret.append(s.charAt(j + i)); if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) //除去第 0 行和最后一行 ret.append(s.charAt(j + cycleLen - i)); } } return ret.toString(); }
时间复杂度：O（n），虽然是两层循环，但第二次循环每次加的是 cycleLen ，无非是把每个字符遍历了 1 次，所以两层循环内执行的次数肯定是字符串的长度。
空间复杂度：O（n），保存字符串。
4. 总结
这次算是总结起来最轻松的了，这道题有些找规律的意思。解法一顺着排列的方式遍历，解法二直接从答案入口找出下标的规律。
第7题. Reverse Integer
1. 题目描述（简单难度）
很简单，就是输入整数，输出它的倒置。
第一反应就是， 取余得到个位数，然后除以 10 去掉个位数，然后用一个变量保存倒置的数。
public int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; rev = rev * 10 + pop; } return rev; }
然后似乎不是那么理想。
为什么呢？倒置过来不应该是 9646324351 吗。其实题目里讲了，int 的范围是 [−231,231−1][-2^{31} ,2^{31}-1][−231,231−1] 也就是 [−2147483648,2147483647][-2147483648,2147483647] [−2147483648,2147483647] 。明显 9646324351 超出了范围，造成了溢出。所以我们需要在输出前，判断是否溢出。
问题的关键就是下边的一句了。
rev = rev * 10 + pop;
为了区分两个 rev ，更好的说明，我们引入 temp 。
temp = rev * 10 + pop;
rev = temp;
我们对 temp = rev * 10 + pop; 进行讨论。intMAX = 2147483647 , intMin = - 2147483648 。
对于大于 intMax 的讨论，此时 x 一定是正数，pop 也是正数。
如果 rev > intMax / 10 ，那么没的说，此时肯定溢出了。
如果 rev == intMax / 10 = 2147483647 / 10 = 214748364 ，此时 rev * 10 就是 2147483640 如果 pop 大于 7 ，那么就一定溢出了。但是！如果假设 pop 等于 8，那么意味着原数 x 是 8463847412 了，输入的是 int ，而此时是溢出的状态，所以不可能输入，所以意味着 pop 不可能大于 7 ，也就意味着 rev == intMax / 10 时不会造成溢出。
如果 rev < intMax / 10 ，意味着 rev 最大是 214748363 ， rev * 10 就是 2147483630 , 此时再加上 pop ，一定不会溢出。
对于小于 intMin 的讨论同理。
public int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > Integer.MAX_VALUE/10 ) return 0; if (rev < Integer.MIN_VALUE/10 ) return 0; rev = rev * 10 + pop; } return rev; }
时间复杂度：循环多少次呢？数字有多少位，就循环多少次，也就是 log10(x)+1log_{10}(x) + 1log10(x)+1 次，所以时间复杂度是 O（log（x））。
空间复杂度：O（1）。
当然我们可以不用思考那么多，用一种偷懒的方式 AC ，我们直接把 rev 定义成 long ，然后输出前判断 rev 是不是在范围内，不在的话直接输出 0 。
public int reverse(int x) { long rev = 0; while (x != 0) { int pop = x % 10; x /= 10; rev = rev * 10 + pop; } if (rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE ) return 0; return (int)rev; }
2. 总结
比较简单的一道题，主要是在考判断是不是溢出，又是轻松的一天！
第8题: String to Integer
题目描述（中等难度）
将一个字符串转为整型。
这道题，难度其实不大，和上道题有很多重合的地方。整体的思路就是遍历字符串，然后依次取出一个字符就可以了。无非是考虑一些特殊情况，还有就是理解题目意思。
经过多次试错，题目的意思是这样的。
从左遍历字符串，可以遇到空格，直到遇到 ’ + ’ 或者数字或者 ’ - ’ 就表示要转换的数字开始，如果之后遇到除了数字的其他字符（包括空格）就结束遍历，输出结果，不管后边有没有数字了，例如 " - 32332ada2323" 就输出 “- 32332”。
如果遇到空格或者 ’ + ’ 或者数字或者 ’ - ’ 之前遇到了其他字符，就直接输出 0 ，例如 " we1332"。
如果转换的数字超出了 int ，就返回 intMax 或者 intMin。
public int myAtoi(String str) { int sign = 1; int ans = 0, pop = 0; boolean hasSign = false; //代表是否开始转换数字 for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '-' && !hasSign) { sign = -1; hasSign = true; continue; } if (str.charAt(i) == '+' && !hasSign) { sign = 1; hasSign = true; continue; } if (str.charAt(i) == ' ' && !hasSign) { continue; } if (str.charAt(i) >= '0' && str.charAt(i) <= '9') { hasSign = true; pop = str.charAt(i) - '0'; //和上道题判断出界一个意思只不过记得乘上 sign 。 if (ans * sign > Integer.MAX_VALUE / 10 || (ans * sign == Integer.MAX_VALUE / 10 && pop * sign > 7)) return 2147483647; if (ans * sign < Integer.MIN_VALUE / 10 || (ans * sign == Integer.MIN_VALUE / 10 && pop * sign < -8)) return -2147483648; ans = ans * 10 + pop; } else { return ans * sign; } } return ans * sign; }
时间复杂度：O（n），n 是字符串的长度。
空间复杂度：O（1）。
总结
这道题让自己有点感到莫名其妙，好像没有 get 到出题人的点？？？
第9题: Palindrome Number
题目描述（简单难度）
判断是不是回文数，负数不是回文数。
解法一
把 int 转成字符串，然后判断是否是回文串做就可以了，缺点是需要额外的空间存储字符串，当然题目也告诉了不能这样，所以 pass 。
解法二
在第 7 道题我们写了倒置 int 的算法，这里当然可以用到了，只需要判断倒置前后相不相等就可以了。
记不记得，当倒置后的数字超出 int 的范围时，我们返回的是 0 ，那么它一定不等于原数，此时一定返回 false 了，这正不正确呢？
我们只需证明，如果倒置后超出 int 的范围，那么它一定不是回文数字就好了。
反证法，我们假设存在这么一个数，倒置后是超出 int 范围的，并且它是回文数字。
int 最大为 2147483647 ,
让我们来讨论这个数可能是多少。
有没有可能是最高位大于 2 导致的溢出，比如最高位是 3 ，因为是回文串，所以最低位是 3 ，这就将导致转置前最高位也会是 3 ，所以不可能是这种情况。
有没有可能是第 2 高位大于 1 导致的溢出，此时保持最高位不变，假如第 2 高位是 2，因为是回文串，所以个位是 2，十位是 2 ，同样的会导致倒置前超出了 int 的最大值，所以也不可能是这种情况。
同理，第 3 高位，第 4，第 5，直线左边的都是上述的情况，所以不可能是前边的位数过大。
为了保证这个数是溢出的，前边 5 位必须固定不变了，因为它是回文串，所以直线后的灰色数字就一定是 4 ，而此时不管后边的数字取多少，都不可能是溢出的了。
综上，不存在这样一个数，所以可以安心的写代码了。
public int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > Integer.MAX_VALUE / 10) return 0; if (rev < Integer.MIN_VALUE / 10) return 0; rev = rev * 10 + pop; } return rev; } public boolean isPalindrome(int x) { if (x < 0) { return false; } int rev = reverse(x); return x == rev; }
时间复杂度：和求转置一样，x 有多少位，就循环多少次，所以是 O（log（x）） 。
空间复杂度：O（1）。
解法三
其实，我们只需要将右半部分倒置然后和左半部比较就可以了。比如 1221 ，把 21 转置和 12 比较就行了。
public boolean isPalindrome(int x) { if (x < 0) { return false; } int digit = (int) (Math.log(x) / Math.log(10) + 1); //总位数 int revert = 0; int pop = 0; //倒置右半部分 for (int i = 0; i < digit / 2; i++) { pop = x % 10; revert = revert * 10 + pop; x /= 10; } if (digit % 2 == 0 && x == revert) { return true; } //奇数情况 x 除以 10 去除 1 位 if (digit % 2 != 0 && x / 10 == revert) { return true; } return false; }
时间复杂度：循环 x 的总位数的一半次，所以时间复杂度依旧是 O（log（x））。
空间复杂度：O（1），常数个变量。
总结
这几天都比较简单，加油加油加油！。
第10题 :Regular Expression Matching
题目描述（困难难度）
一个简单规则的匹配，「点.」代表任意字符，「星号*」 代表前一个字符重复 0 次或任意次。
解法一 递归
假如没有通配符 * ，这道题的难度就会少了很多，我们只需要一个字符，一个字符匹配就行。如果对递归不是很了解，强烈建议看下这篇文章，可以理清一下递归的思路。
- 我们假设存在这么个函数 isMatch，它将告诉我们 text 和 pattern 是否匹配
boolean isMatch ( String text, String pattern ) ;
递归规模减小
text 和 pattern 匹配，等价于 text 和 patten 的第一个字符匹配并且剩下的字符也匹配，而判断剩下的字符是否匹配，我们就可以调用 isMatch 函数。也就是
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.')&&isMatch(text.substring(1), pattern.substring(1));
递归出口
随着规模的减小， 当 pattern 为空时，如果 text 也为空，就返回 True，不然的话就返回 False 。
if (pattern.isEmpty()) return text.isEmpty();
综上，我们的代码是
public boolean isMatch(String text, String pattern) { if (pattern.isEmpty()) return text.isEmpty(); //判断 text 是否为空，防止越界，如果 text 为空， 表达式直接判为 false, text.charAt(0)就不会执行了 boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.')); return first_match && isMatch(text.substring(1), pattern.substring(1)); }
当我们考虑了 * 呢，对于递归规模的减小，会增加对于 * 的判断，直接看代码吧。
public boolean isMatch(String text, String pattern) { if (pattern.isEmpty()) return text.isEmpty(); boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.')); //只有长度大于 2 的时候，才考虑 * if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ //两种情况 //pattern 直接跳过两个字符。表示 * 前边的字符出现 0 次 //pattern 不变，例如 text = aa ，pattern = a*，第一个 a 匹配，然后 text 的第二个 a 接着和 pattern 的第一个 a 进行匹配。表示 * 用前一个字符替代。 return (isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern))); } else { return first_match && isMatch(text.substring(1), pattern.substring(1)); } }
时间复杂度：有点儿小复杂，待更。
空间复杂度：有点儿小复杂，待更。
解法二 动态规划
上边的递归，为了方便理解，简化下思路。
为了判断 text [ 0，len ] 的情况，需要知道 text [ 1，len ]
为了判断 text [ 1，len ] 的情况，需要知道 text [ 2，len ]
为了判断 text [ 2，len ] 的情况，需要知道 text [ 3，len ]
…
为了判断 text [ len - 1，len ] 的情况，需要知道 text [ len，len ]
text [ len，len ] 肯定好求
求出 text [ len，len ] 的情况，就知道了 text [ len - 1，len ]
求出 text [ len - 1，len ] 的情况，就知道了 text [ len - 2，len ]
…
求出 text [ 2，len ] 的情况，就知道了 text [1，len ]
求出 text [ l1，len ] 的情况，就知道了 text [ 0，len ]
从而知道了 text [ 0，len ] 的情况，求得问题的解。
上边就是先压栈，然后出栈，其实我们可以直接倒过来求，可以省略压栈的过程。
我们先求 text [ len，len ] 的情况
利用 text [ len，len ] 的情况 ，再求 text [ len - 1，len ] 的情况
…
利用 text [ 2，len ] 的情况 ，再求 text [ 1，len ] 的情况
利用 text [1，len ] 的情况 ，再求 text [ 0，len ] 的情况
从而求出问题的解
我们用 dp[i][j]dp[i][j]dp[i][j]表示 text 从 i 开始到最后，pattern 从 j 开始到最后，此时 text 和 pattern 是否匹配。
dp[2][2]dp[2][2]dp[2][2]就是图中橙色的部分.
public boolean isMatch(String text, String pattern) { // 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况， // 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了 boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1]; // dp[len][len] 代表两个空串是否匹配了，"" 和 "" ，当然是 true 了。 dp[text.length()][pattern.length()] = true; // 从 len 开始减少 for (int i = text.length(); i >= 0; i--) { for (int j = pattern.length(); j >= 0; j--) { // dp[text.length()][pattern.length()] 已经进行了初始化 if(i==text.length()&&j==pattern.length()) continue; boolean first_match = (i < text.length() && j < pattern.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.')); if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') { dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j]; } else { dp[i][j] = first_match && dp[i + 1][j + 1]; } } } return dp[0][0]; }
时间复杂度：假设 text 的长度是 T，pattern 的长度是 P ，空间复杂度就是 O（TP）。
空间复杂度：申请了 dp 空间，所以是 O（TP），因为每次循环我们只需要知道 i 和 i + 1 时候的情况，所以我们可以向 第 5 题 一样进行优化。
public boolean isMatch(String text, String pattern) { // 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况， // 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了 boolean[][] dp = new boolean[2][pattern.length() + 1]; dp[text.length()%2][pattern.length()] = true; // 从 len 开始减少 for (int i = text.length(); i >= 0; i--) { for (int j = pattern.length(); j >= 0; j--) { if(i==text.length()&&j==pattern.length()) continue; boolean first_match = (i < text.length() && j < pattern.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.')); if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') { dp[i%2][j] = dp[i%2][j + 2] || first_match && dp[(i + 1)%2][j]; } else { dp[i%2][j] = first_match && dp[(i + 1)%2][j + 1]; } } } return dp[0][0]; }
时间复杂度：不变， O（TP）。
空间复杂度：主要用了两个数组进行轮换，O（P）。
总
这道题对于递归的解法，感觉难在怎么去求时间复杂度，现在还没有什么思路，以后再来补充吧。整体来说，只要理清思路，两种算法还是比较好理解的。
今天我们一起学习了LeetCode 6-10 题的算法分析,感谢大家阅读,觉得不错记得收藏哦!
