图解leetcode5-10 | 和233酱一起刷leetcode系列(2)
本周我们继续来看5道磨人的小妖精，图解leetcode6-10～
多说一句，leetcode10 杀死了233酱不少脑细胞…
另：
沉迷算法，无法自拔。快来加入我们吧！
别忘了233酱的一条龙服务：
公众号文章题解 -> 私信答疑 -> 刷题群答疑 -> 视频讲解
我们的目的是成为套路王～
嘿嘿，广告完毕 , Let’s go!
leetcode6: Z 字形变换
题目描述：
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
题目示例:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
解题思路:
相信小伙伴看到这道题目，也和233一样觉得Z字形排列的字符串冥冥中有些规律。为了方便解释 ，我们假设输入：
字符串s=”0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15″
numRows=4
注意： s中的输入字符依次为：为0-15，中间的空格是我为了展示清楚额外加的。
那么s的Z字形排列如下：
需要输出的结果是：“0 6 12 15 7 11 13 2 4 8 10 14 3 9 15”
假设我们将Z字形排列后的字符串每一行i 用一个数组arr[i]存起来，最后按行数i的顺序输出arr[i]中的值，那么就可以得到最终的输出结果。
如何知道字符串s中的各个字符在哪个arr数组的哪个索引位置呢？这就是我们用数字字符的字符串来举例子的好处了，因为数字的值就对应着字符在字符串s中的下标。当我们遍历字符串s时，是我们可以用pointer表示当前遍历的字符所对应的行数i，代表这个字符是要放到arr[i]中的。
我们可以发现每当遍历numRows=4 个字符，pointer就从 0->3 转化为 3->0。所以我们可以用一个flag记录pointer的变化量。
思路有了，我们来看一下时间空间复杂度：
- 时间复杂度：遍历一遍字符串s: O(n)。
- 空间复杂度：数组arr的存储：O(n)。
可以写出代码吗：）
Java版本
class Solution {
public String convert(String s, int numRows) {
if(numRows <= 1){
return s;
}
List<StringBuilder> arr = new ArrayList<>();
for(int i = 0 ;i< numRows;i++){
arr.add(new StringBuilder());
}
int flag = -1;
int pointer = 0;
for(int i =0;i<s.length();i++){
char ch = s.charAt(i);
arr.get(pointer).append(ch);
if(pointer == 0 || pointer == numRows -1) flag = - flag;
pointer += flag;
}
StringBuilder res = new StringBuilder();
for(StringBuilder row : arr) res.append(row);
return res.toString();
}
}
leetcode7: 整数反转
题目描述：
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
题目示例:
输入: 123
输出: 321
输入: -123
输出: -321
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
解题思路:
这道题考的还是 数学运算。
Step1:需要分别取出十进制数字的个位，十位，百位..一直到最高位的数字。
阿姨来教你小学数学的除法运算：
所以当我们 取余再取模 就可以得到高位的数字。
Step2:将取出来的个位，十位，百位..一直到最高位的数字 依次放到 最高位,…,百位，十位，个位。
阿姨来教你小学数学的乘法运算：
至于示例中列举的几个边界条件，Java中的整数是带有符号的。刚好符合我们的乘除运算。
另外，需要判断乘法计算时正负数字的越界问题。当然如果res用long表示，也就不需要考虑这个问题了。代码如下：
Java版本
class Solution {
public int reverse(int x) {
int res = 0;
while(x!=0){
if(x>0 && res > ((Integer.MAX_VALUE-x%10)/10)) return 0;
if(x<0 && res < ((Integer.MIN_VALUE-x%10)/10)) return 0;
res = res*10 + x%10;
x/=10;
}
return res;
}
}
leetcode8: 字符串转换整数(atoi)
题目描述：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ‘ ‘ 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
题目示例:
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
解题思路:
放这么多 题目示例 阿姨并不是为了凑字数，而是这类问题就是属于考边界情况的问题，边界情况拎清了，就不会被磨到了～
假设输入一个字符串 ” -4193 with words” ， 我们可以从左到右遍历这个字符串，用k 表示当前遍历到的字符：
另外，我们还需要注意 示例5的情况，当乘法计算时的值超过INT_MAX or INT_MIN时，结束并返回 INT_MAX or INT_MIN.
Java版本
class Solution {
public int myAtoi(String str) {
int res = 0;
int k = 0;
while(k< str.length() && ' ' == str.charAt(k))k++;
int minus = 1;
if(str.length() == k) return res;
if('-' == str.charAt(k)) {
minus = -1;
k++;
}else if('+' == str.charAt(k)){
k++;
}
while(k<str.length() && str.charAt(k) >= '0' && str.charAt(k) <='9'){
int x = str.charAt(k) - '0';
if(minus >0 && res> (Integer.MAX_VALUE - x)/ 10){
return Integer.MAX_VALUE;
}
//-res * 10 - str.charAt(k) < Integer.MIN_VALUE
if(minus <0 && -res < (Integer.MIN_VALUE + x)/10)
return Integer.MIN_VALUE;
//最大的负数是存不下来的
if((-res * 10 - x) == Integer.MIN_VALUE ) {
return Integer.MIN_VALUE;
}
res = res* 10 + x;
k++;
}
res *= minus;
return res;
}
}
leetcode9: 回文数
题目描述：
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
题目示例:
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
解题思路:
上篇文章中我们讲过最长回文子串的查找。再来看这道题就很easy了。这道题的解法也很多：
比如我们可以把它变为字符串。然后reverse一下，判断前后两个字符串是否相等。
但是我们用一种更简单的方式，只需要反转整数，然后判断两个整数是否相等，就可以确定是不是回文整数。又回到leetcode7了，有没有觉得阿姨的乘除法运算还是有帮助的：）
Java版本
class Solution {
public boolean isPalindrome(int x) {
if(x<0) return false;
if(x<=9) return true;
int oringin = x;
int res = 0;
while(x>0){
//如果越界了说明不对称
res = res*10 + x%10;
x/=10;
}
return oringin == res;
}
}
leetcode10: 正则表达式匹配
题目描述：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
题目示例:
示例 1:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 2:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
神奇的.*来了，Hard模式，大家坐好～
判断 字符串s 是否与 一个 可能还有“.” or “*” 的字符规律 p 匹配，其实就是从 p 代表的所有的字符串中枚举出一个 匹配值。 简单暴力枚举的时间复杂度是指数级的。我们需要考虑对于求解一个最优解 或 匹配解的类似问题，有哪些可以降低时间复杂度的方案？
好了，不饶弯子了，动态规划 要来了。
温馨后记：写着写着就列举了一堆动态规划的理论，比较了解的朋友可以直接翻过这段看后面这一题的图解。
解题之前，我们先了解下：动态规划是什么？为什么动态规划能降低时间复杂度？什么类型的问题又能用动态规划去解决？如何构造解题步骤？
动态规划是什么
动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。
分治算法将问题划分为互不相交的子问题，递归地求解子问题，再将他们的解组合起来，求出原问题的解。如归并排序，划分的左右排序子问题是对不同的数字序列进行排序的，最后再把他们合并起来。
而动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。这种情况下分治算法需要对子子问题反复求解，而动态规划算法只对子子问题求解一次，将其结果保存到备忘录中 or 按照 自底向下 的顺序 求解每个子问题（也就是保证在求解子问题时，它所依赖的子子问题的解已经求出来了）这两种方式，避免不必要的计算工作，降低时间复杂度。
举一个简单的斐波那契数列的例子：
斐波那契数列指的是这样一个数列：
1、1、2、3、5、8…
相信小伙伴们都知道，它的递推规律是：
假设求f(10),则递推公式展开为：
可以看到其中有大量的重复子问题：f(6),f(5) 等。
动态规划的两种做法就是：
1.用 递归的代码求解时，将第一次计算的f(6)保存起来，如f(8)中的f(6). 这样再求解f(7)中的f(6)就可以直接获取到结果了
2.按照求f(3), ->(4)->…->f(10)的自底向下的顺序求解，这样再求 f(8)时，只需要保存下来 f(7) 和 f(6)的值，就可以求出了，f(10)同理。这种方式大多是循环的写法。
动态规划解决的问题类型
初步明白后，我们再来看下动态规划解决问题的类型：
极客时间的王争大佬 概括为： 一个模型，三个特征。
一个模型：多阶段决策最优解模型
我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
特征1:最优子结构
指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
特征2:无后效性
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
特征3. 重复子问题
这个就是我们前面提到的，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
动态规划的解题步骤
Step1.刻画一个最优解的结构特征
也就是能够把问题抽象转化为一种数学描述，通俗说 就是 状态的定义。如上述斐波那契数列 中 f(n）就是状态的定义。
Step2.递归地定义最优解的值。
就是问题与子问题之间的递推表达式是什么，通俗说 就是 状态转移方程的定义。如上述斐波那契数列 中的f(n) = f(n-1) + f(n-2)
Step3.计算最优解的值
就是采用的动态规划具体计算的做法，包括 递归+备忘录 or 循环+自底向下 求解两种方式。
Step4.利用计算出的信息构造一个最优解
因为我们步骤一定义的状态有时并不是我们直接要求的最优解，所以这一步就是利用状态和状态转移方式 表达出我们最终要求的最优解怎么得到。
我们会根据leetcode10来理解这些理论知识。
解题思路:
Step1.抽象出状态
这个问题实际求的是字符串s能否从字符规律p代表的所有字符串集合中找出一个匹配值。一般求两个字符串的匹配问题的状态用二维的数组来定义，为什么。。听大佬说：靠经验，靠悟。我们定义：dp[i,j] : 代表 所有 字符串s[0,i-1] (前i个字符) 和 字符规律p[0,j-1] （前j个字符）的匹配方案 集合。dp[i,j] 的值： 代表是否存在一种方案 使得 字符规律p 匹配 字符串s。这个值就是我们这个问题的解。true：存在。false：不存在。
Step2.递归地定义最优解的值。
这一步其实就是求状态递推式，找出问题dp[i,j] 和子问题之间的关系。
对于字符串s[i] 和 p[j] 是否匹配，因为p[j] 可能是* or . 。我们需要枚举出p所代表的所有字符串。我们我们可以从最后的字符 s[i] 和 p[j]来考虑。
可分为p[j] == * or p[j] != * 两种情况。因为 ‘*’ 代表着0-多个字符，会影响p的枚举数。’.’ 我们只需要把它当成一个万能字符就好，’.’ 不会影响p的枚举数量。
-
当
p[j] != '*'时，则 s 与 p 是否匹配 取决于s[i] 是否等于 p[j] && dp[i][j] 是否为true -
当
p[j] == '*'时，我们需要枚举* 代表的从0-多个字符的字符序列集合中，s 是否与他们其中之一匹配。
如图所示，考虑p[j] == '*' 所代表的字符数，我们需要列举出 组成dp[i+1,j+1] 的所有可能情况，同时我们其实靠yy也能推断出：
dp[i+1,j+1] 和 它的子问题：dp[i,j+1] 的关系，图中我也有列举出公式推导来源。
这里有一点需要注意： dp[i+1,j+1]才表示s[0,i] 和 p[0,j] 匹配。因为s[0]就代表了第一个字符。而我们也需要表示 s长度为0的dp[0,..]的值。不然会影响到我们递推公式的求值。
好了，到这里我们先总结下 这个问题动态规划解法的状态和状态转移方程：
Step3.计算最优解的值。
这个步骤就是具体计算递推公式dp[i+1,j+1]的过程了，我们可以采用 循环+ 自底向下的方式来求解，也就是对于二维数组先填第0行的值，再填第0列的值，以此类推。
假设s=”aa”, p=”a*” 。则它的二维填状态表的顺序和结果为：
Step4.利用计算出的信息构造一个最优解
在Step1的时候，我们其实就定义了。 s与p是否匹配 等价于 dp[i+1][j+1] 的值 是否为 true。 所以我们只需要返回 dp[i+1][j+1]的值 就是这道题的结果。
彻底完了，看懂了没，上代码吧。
Java版本
class Solution {
public boolean isMatch(String s, String p) {
int slen = s.length();
int plen = p.length();
//需要分别取出s和p为空的情况，所以dp数组大小+1
boolean[][] dp = new boolean[slen + 1][plen + 1];
//初始化dp[0][0]=true,dp[0][1]和dp[1][0]~dp[s.length][0]默认值为false所以不需要显式初始化
dp[0][0] = true;
//填写第一行dp[0][2]~dp[0][p.length]
for (int k = 2; k <= plen; k++) {
//p字符串的第2个字符是否等于'*',此时j元素需要0个，所以s不变p减除两个字符
dp[0][k] = p.charAt(k - 1) == '*' && dp[0][k - 2];
}
//填写dp数组剩余部分
for (int i = 0; i < slen; i++) {
for (int j = 0; j < plen; j++) {
//p第j个字符是否为*
if (p.charAt(j) == '*') {
//两种情况:1.s不变[i+1],p移除两个元素[j+1-2]。
// 2.比较s的i元素和p的j-1(因为此时j元素为*)元素,相等则移除首元素[i+1-1],p不变。
dp[i + 1][j + 1] = dp[i + 1][j - 1] ||
(dp[i][j + 1] && headMatched(s, p, i, j - 1));
} else {
//s的i元素和p的j元素是否相等,相等则移除s的i元素[i+1-1]和p的j元素[j+1-1]
dp[i + 1][j + 1] = dp[i][j] && headMatched(s, p, i, j);
}
}
}
return dp[slen][plen];
}
//判断s第i个字符和p第j个字符是否匹配
public boolean headMatched(String s, String p, int i, int j) {
return s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
}
}
能看到这里看来是真爱了，233酱都要对你竖起大拇指，要不要也在看，转发 对233酱竖起大拇指 …… ^ _ ^。不管对文章是否有疑问，都欢迎可爱的你加入我们的刷题群，有疑问233酱会在群里答疑哦～
参考资料：
[1].《算法导论》
[2].https://time.geekbang.org/column/article/75702