• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

开发技术 开发技术 1周前 (06-22) 17次浏览

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

本周我们继续来看5道磨人的小妖精,图解leetcode6-10~

多说一句,leetcode10 杀死了233酱不少脑细胞…

另:

沉迷算法,无法自拔。快来加入我们吧!
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

别忘了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字形排列如下:

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

需要输出的结果是:“0 6 12 15 7 11 13 2 4 8 10 14 3 9 15”

假设我们将Z字形排列后的字符串每一行i 用一个数组arr[i]存起来,最后按行数i的顺序输出arr[i]中的值,那么就可以得到最终的输出结果。
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

如何知道字符串s中的各个字符在哪个arr数组的哪个索引位置呢?这就是我们用数字字符的字符串来举例子的好处了,因为数字的值就对应着字符在字符串s中的下标。当我们遍历字符串s时,是我们可以用pointer表示当前遍历的字符所对应的行数i,代表这个字符是要放到arr[i]中的。
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

我们可以发现每当遍历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:需要分别取出十进制数字的个位,十位,百位..一直到最高位的数字。

阿姨来教你小学数学的除法运算:
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)
所以当我们 取余再取模 就可以得到高位的数字。

Step2:将取出来的个位,十位,百位..一直到最高位的数字 依次放到 最高位,…,百位,十位,个位。

阿姨来教你小学数学的乘法运算:
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

至于示例中列举的几个边界条件,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 表示当前遍历到的字符:
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

另外,我们还需要注意 示例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了,有没有觉得阿姨的乘除法运算还是有帮助的:)

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

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…

相信小伙伴们都知道,它的递推规律是:
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

假设求f(10),则递推公式展开为:
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)
可以看到其中有大量的重复子问题: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]来考虑。
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

可分为p[j] == * or p[j] != * 两种情况。因为 ‘*’ 代表着0-多个字符,会影响p的枚举数。’.’ 我们只需要把它当成一个万能字符就好,’.’ 不会影响p的枚举数量。

  • p[j] != '*' 时,则 s 与 p 是否匹配 取决于 s[i] 是否等于 p[j] && dp[i][j] 是否为true
    图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

  • p[j] == '*' 时,我们需要枚举* 代表的从0-多个字符的字符序列集合中,s 是否与他们其中之一匹配。

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)
如图所示,考虑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,..]的值。不然会影响到我们递推公式的求值。

好了,到这里我们先总结下 这个问题动态规划解法的状态和状态转移方程:
图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

Step3.计算最优解的值。
这个步骤就是具体计算递推公式dp[i+1,j+1]的过程了,我们可以采用 循环+ 自底向下的方式来求解,也就是对于二维数组先填第0行的值,再填第0列的值,以此类推。
假设s="aa", p="a*" 。则它的二维填状态表的顺序和结果为:

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

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酱会在群里答疑哦~

图解leetcode5-10 | 和233酱一起刷leetcode系列(2)

参考资料:
[1].《算法导论》
[2].https://time.geekbang.org/column/article/75702


喜欢 (0)