LeetCode琅琊榜第二层-最长回文子串问题(动态规划)「建议收藏」

LeetCode琅琊榜第二层-最长回文子串问题(动态规划)「建议收藏」LeetCode_5.最长回文字串难度:中等看了它,妈妈再也不用担心我不会力扣啦

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

LeetCode_5.最长回文字串

难度:中等

关注博主,持续输出优质算法内容

题目链接

LeetCode琅琊榜第二层-最长回文子串问题(动态规划)「建议收藏」


目录

 1.暴力求解法?

 1.代码思路?

 2.不足之处及提升方法?

不足之处?

提升方法?

3.回文字符串的特征分析? 

4.动态规划算法的思想?

5.动态规划解题的代码实现与分析?

代码分析:?

优越性与结论?


1.暴力求解法?

class Solution {
    public String longestPalindrome(String s) {
        var maxLength = 0;
        String tempStr = null;
        var begin = 0;
        var end = 0;
        for (int i = 0; i < s.length();i++) {
            for (int j = s.length() - 1; j >= i;j--){
                if (j - i < maxLength) {
                    break;
                }
                var flag = false;
                while (j >= i && s.charAt(i) != s.charAt(j)) {
                    j--;
                }
                if (j >= i) {
                    flag = isPalindrome((tempStr = s.substring(i,j+1)));
                }
                if (flag && tempStr.length() > maxLength) {
                    begin = i;
                    end = i + tempStr.length();
                    maxLength = tempStr.length();
                    break;
                }
            }
        }
        return s.substring(begin,end);
    }
    public boolean isPalindrome(String str) {
        int p0 = 0;
        int p1 = str.length() - 1;
        while (p0 < p1 && str.charAt(p0) == str.charAt(p1)) {
            p0++;
            p1--;
        }
        return p0 >= p1;
    }
}
  •  1.代码思路?

  • 根据回文子串的特点,收尾的元素一定相等,所以我们从字符串的最后一个位置开始找,找一个第一个元素相同的元素
  • 找到该元素后,我们对这两个元素里面的区间进行判断,即isPalidorme方法,从两边向中间,判断两两元素是否相等
  • 如果这个区间内是回文子串,我们就把他记录下来,并把第一个元素后移一位
  • 如果这个区间内不是回文子串,那么有可能最后一个元素向前移一位会形成回文子串,因此形成嵌套循环从而得出答案

 2.不足之处及提升方法?

  • 不足之处?

  • 我们可以发现,上述算法的时间复杂度是O(N*2)平方阶,空间复杂度是O(1),虽然是平方阶,但是,因为找子串的过程是一个嵌套for循环,里面含有大量的情况,而且还调用了下面判断是否为回文串的方法,会造成大量的比较,使程序的效率大大降低

  • 提升方法?

  • 因此,我们引入了新的方法,即动态规划算法

3.回文字符串的特征分析? 

  • 假设有一个回文字符串,即[B,A,B,A,B],我们发现,回文字符串的两边的元素是一样的,即 B = B,倘若,我们将两边的元素删去之后,即[A,B,A],两边的元素仍然是一样的,该字符串还是一个回文字符串,因此,我们得出了一个结论:回文字符串如果将两个端点删去之后,新的字符串还是一个回文字符串且两个端点是一样的
  • 此外,如果只有一个元素[A],那么他自己就是一个回文字符串,所以,回文字符串最小长度是1

4.动态规划算法的思想?

  • 前言:动态规划算法的核心步骤是填表,所以,动态规划算法主要是以如何去填表以及找出表里面元素之间的关系展开
  • 注意:动态规划算法的思想与回文串的特征密不可分,所以,要想用动态规划解决这个问题先要熟悉回文串的特征
  • 我们假定一个闭区间[i,j]是回文子串,i表示该回文子串的第一个元素的下标,j表示该回文子串的最后一个元素的下标
  • 我们需要先判断i和j是否相等,如果相等则说明该区间有可能是回文子串
  • 接着我们需要进一步求验这个区间是否是回文子串,所以要判断i+1和j-1
  • 此刻,如果经过不断的求验,只剩下最后一个元素,那么我们说明这个区间一定是一个回文子串
  • 上述这句话我们可以用 (j – 1) – (i + 1) + 1 <  2来解释,即如果(j – 1) = 3 (i + 1) = 2,根据表达式得出结果是2,因为2与3是两个元素,与2相等,所以该表达式是稳妥的
  • 通过化简得出 j – i < 3,当满足这个条件的时候,说明构成回文字符串
  • 有了上面的基础,开始制表
  • 表中的行和列分别表示对应的元素的下标,对应的值表达的是这两个下标之间能否形成回文子串,如果可以则赋值为true,否则为false

如图所示

LeetCode琅琊榜第二层-最长回文子串问题(动态规划)「建议收藏」


5.动态规划解题的代码实现与分析?

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        var len = s.length();
        var begin = 0;
        var maxLen = 1;
        var sChars = s.toCharArray();
        var board = new boolean[len][len];
        for (int i = 0,j = 0; i < len && j < len; i++,j++) {
            board[i][j] = true;
        }
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (sChars[i] != sChars[j]) {
                    board[i][j] = false;
                }else {
                    if (j - i < 3) {
                        board[i][j] = true;
                    }else {
                        board[i][j] = board[i+1][j-1];
                    }
                }
                if (board[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLen);
    }
}

代码分析:?

  1. 首先,我们要先判断一下所给字符串长度,如果小于2,不需要去执行算法了,直接返回(只有一个元素,一定构成回文)
  2. 变量的定义(变量的定义可以不唯一,如果搞懂了的话maxLen和sChars都可以不要)
    1. len ? 字符串 
    2. begin ? 最长回文子串的第一个元素的下标
    3. maxLen ? 最长回文子串的长度(为了好看)
    4. board ? 对应所要画的表
    5. sChars ? 字符串对应的字符数组(为了好遍历)
  3. 画表过程
    1. 首先,为了体现算法的严谨性,我们要将那一条对角线赋值为true,即自己和自己构成回文,所以对角线内都是true(PS:实际上用不到,只是体现算法严谨性!!!)
    2. 首先,我们先要理清一个该点,即如果下标为0和3的构成回文,说明下标为1和2的构成回文,根据图示中的表可知,我们需要通过这个表位置的左下角的位置的值才能确定当前位置的值
    3. 从上述的描述可知,要想保证左下角一定有值,我们要保证表的那一列全部被赋值完,所以我们对表的赋值的策略是:弄完一列再去弄下一列
    4. 所以得出了以上循环,对于变量的定义
      1. j ? 横坐标即列 
      2. i ? 纵坐标即行
      3. 因为(0,0)这个位置已经被赋值了,没必要继续赋值,所以直接到(0,1)即j = 1
      4. 由图示中的表可知,我们只需要赋值那条斜线上的内容,所以i < j(上下是对称的,没必要去弄下面的)
      5. 如果sChar[i] != sChar[j],说明了在这个[i,j]的区间内一定不是回文子串,所以直接赋值为false
      6. 如果sChar[i] = sChar[j],说明了在这个[i,j]的区间可能是回文子串,所以还要接着判断
        1. 如果j – i < 3,说明[i,j]之间小于两个元素,一个元素一定构成回文子串,故赋值为true
        2. 否则直接赋值为board[i][j] = board[i+1][j-1],因为如果[i+1,j-1]如果构成回文子串,那么[i,j]也一定构成,否则就不构成,直接赋值是可行的
        3. 注意:这里我们可以用套娃思想,进行逆推,i+1和j-1构成说明i+2和j-2构成说明i+3和j-3构成…..从而推出来的
      7. 最后,我们得出来该位置board[i][j]的值,通过判断,如果我么发现值为true,则说明构成了回文子串,如果j – i + 1(回文子串元素个数)大于maxLen,就进行赋值和记录下标
    5. 最后,当循环结束后,我们就知道最大回文子串,知道了其开始下标和长度,调用subString方法返回即可


优越性与结论?

         虽然动态规划还是摆脱不了O(N^2),但是动态规划消除了大量比较带来的时间损耗,大大提升了代码的性能,同时,动态规划算法也是我们常见的面试考点,所以我这摘取了动态规划算法,马拉车算法就不讲了(面试不考)

        我来总结一下必须要掌握的几点

        1.回文字符串的特征

        2.动态规划算法的思路

        3.代码的实现

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/181168.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • unity 方向向量_二面角距离公式

    unity 方向向量_二面角距离公式在学习Unity官方案例时,发现其中用了两种求物体XZ平面旋转夹角的方法:   方法1:floatangle=Vector3.Angle(fromVector,toVector);//求出两向量之间的夹角Vector3normal=Vector3.Cross(fromVector,toVector);//叉乘求出法线向量angle*=Mathf.Sig

  • python进阶(4)文件操作[通俗易懂]

    python进阶(4)文件操作[通俗易懂]文件操作文件操作主要包括对文件内容的读写操作,这些操作是通过文件对象实现的,通过文件对象可以读写文本文件和二进制文件open(file,mode='r',buffering=-

  • Git 工具 – 高级合并「建议收藏」

    高级合并在Git中合并是相当容易的。因为Git使多次合并另一个分支变得很容易,这意味着你可以有一个始终保持最新的长期分支,经常解决小的冲突,比在一系列提交后解决一个巨大的冲突要好。然而,有时也会有棘手的冲突。不像其他的版本控制系统,Git并不会尝试过于聪明的合并冲突解决方案。Git的哲学是聪明地决定无歧义的合并方案,但是如果有冲突,它不会尝试智能地自动解决它。因此,如果很久之后才合并两个分叉的分支,你可能会撞上一些问题。在本节中,我们将会仔细查看那些问题是什么以及Git

  • atitit 短信接口规范与短信解决方案.docx

    atitit 短信接口规范与短信解决方案.docx

  • toast弹窗代码_app加弹窗软件

    toast弹窗代码_app加弹窗软件效果图代码:<!DOCTYPEhtml><htmllang=”en”> <head> <title>弹窗</title> <metacharset=”UTF-8″> <metaname=”viewport”content=”width=device-width,initial-s…

  • python中int的取值范围_int32的取值范围是多少?

    python中int的取值范围_int32的取值范围是多少?int32的数值取值范围为“-2147483648”到“2147483647”;而int64的数值取值范围为“-9223372036854775808”到“9223372036854775808”。int32的取值范围计算机中32位int类型变量的范围,其中int类型是带符号整数。正数在计算机中表示为原码,最高位为符号位:1的原码为000000000000000000000000000…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号