[c/c++]——最长回文子串「建议收藏」

[c/c++]——最长回文子串「建议收藏」最长回文子串已经很久没有更新关于leetcode的题解了,一个是觉得太费时间,二一个目前网上也有很全面的解答,但是在写leetcode的最长回文子串时,发现很多同学的代码都很长(实际上几行就可以解决的事情),并且c++解答的代码不够完整。最关键的是在一种“马拉车”的算法卡了很久很久,今天把几种求解的方法全部都整理出来,方便大家也便于自己以后复习。ps:讲解很少,都是整理出可看性很高的源码方法…

大家好,又见面了,我是你们的朋友全栈君。

最长回文子串

已经很久没有更新关于leetcode的题解了,一个是觉得太费时间,二一个目前网上也有很全面的解答,但是在写leetcode的最长回文子串时,发现很多同学的代码都很长(实际上几行就可以解决的事情),并且c++解答的代码不够完整。最关键的是在一种“马拉车”的算法卡了很久很久,今天把几种求解的方法全部都整理出来,方便大家也便于自己以后复习。

ps:讲解很少,都是整理出可看性很高的源码

方法一:暴力求解

其实在做多了leetcode的题之后你会发现,你拿到题如果第一想法是暴力解法那么恭喜你,95%过不了,所以这里的第一种暴力法如果在面试时被问到你可以讲出来为后面更优秀的算法做铺垫,实际上没有什么使用价值,这道题领扣只过了60%用例左右吧

  • 时间复杂度:O(N^3)
  • 空间复杂度:O(1)
  • 思路:思路很简单,双循环判断每一个从i开始到j结束的子串是不是回文的,因为判断子串又需要遍历一遍所以时间复杂度为O(N^3)
class Solution { 
   //暴力算法
public:
    string longestPalindrome(string s) { 
   
        if(s.size() == 0 || s.size() < 2) return s;
        int max = 0;
        string ret = "";
        for(int i = 0;i < s.size();i++)
        { 
   
            for(int j = 1;j < s.size();j++)
            { 
   
                string tmp = s.substr(i,j-i+1);
                string tmpr(tmp);//这里将这个子串反转一下与原串对比是否相同
                reverse(tmp.begin(),tmp.end());
                if(tmp == tmpr && tmp.size() > max)
                { 
   
                    max = tmp.size();
                    ret = s.substr(i,j-i+1);
                }
            }
        }
        return ret;
    }
};

方法二:中心扩散算法

这个算法相对暴力算法来说可以说效率高了不只一点点,甚至比动态规划还要好。

  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)
  • 思路:以abbba为例子,我们以最中间的b为例子,向两边扩散为bbb -> abbba,结束。当然如果是abba的字符串我们就可能需要从bb开始扩散bb -> abba结束,思路并不难理解照着源代码就能豁然开朗。(其实很好理解,不要觉得很难因为硬菜在后面,嘿嘿嘿)
class Solution { 
   //中心扩散法
public:
    int max = 0;
    string ret = "";
    void spread(string& s,int left,int right) { 
   
        int L = left,R = right;
        while(L >= 0 && R < s.size() && s[L] == s[R]) { 
   //向左向右扩散
            if(R-L+1 > max) { 
   
                max = R-L+1;
                ret = s.substr(L,R-L+1);
            }
            L--; R++;
        }
    }
    string longestPalindrome(string s) { 
   
        if(s.size() <= 1) return s;
        for(int i = 0;i < s.size();i++) { 
   
            spread(s,i,i);//从单个字符开始扩散
            spread(s,i,i+1);//从相邻的两个字符开始扩散
        }
        return ret;
    }
};

方法三:动态规划

如果你没有学过动态规划的思想可以先了解下什么是动态规划,动态规划在这道题中效率出奇的低这让人也是很纳闷

  • 时间复杂度:O(N^2)
  • 空间复杂度:O(N^2)
  • 思路:一个子串是否为回文串可以判断这个子串的第一个与最后一个是否相等+中间的子串是否为回文,中间的子串又可以分解为第一个与最后一个是否相等+中间的子串是否为回文,所以我们就找到了最优子结构,我们直接贴代码来分析
class Solution { 
   //动态规划
public:
    string longestPalindrome(string s) { 
   
        if(s.size() == 0) return s;
        int dp[s.size()][s.size()] = { 
   0};//创建一个存放状态的数组
        string ret = "";
        int max = 0;
        for(int i = 0;i < s.size();i++) { 
   //这个双循环是在判断i到j位置的子串是否为回文串
            for(int j = 0;j <= i;j++) { 
   
                dp[i][j] = s[i] == s[j] && (i-j <=2 || dp[i-1][j+1]);
                //i-j <=2这句是因为如果子串为bb时就是极限状态,他也构成回文
                //dp[i-1][j+1]这句就是判断中间的子串是否为回文,很好理解
                if(dp[i][j]) { 
   
                    if(i-j+1 > max) { 
   
                        max = i-j+1;
                        ret = s.substr(j,i-j+1);
                    }
                }
            }
        }
        return ret;
    }
};

方法四:马拉车算法

在这里插入图片描述
真是个让人头皮发麻的算法,说真的,我也讲不清楚,有时候我脑子里明白的东西我说出来大家可能还是一脸懵逼,就把自己找到非常优秀的讲解给大家贴上,嘤嘤嘤,这样大家就可以少走点弯路找资料了。

链接:https://www.felix021.com/blog/read.php?2040
(多的不贴了,这个讲的真的是最好的,其余的都是把人家的抄过来,很多博客笔者可能自己都没明白)

我这里就说一些细节(给大家用大白话讲出来)的东西,帮助大家更好的理解,前提确保你先真正看懂了如何求解p数组

class Solution { 
   //马拉车算法
public:
    string longestPalindrome(string s) { 
   
        if(s.size() <= 1) return s;
        string str = "@#";//一定注意这个@,非常关键,因为在从下标为1的#字符开始求解p数组时没有这个符号就越界了
        for(int i = 0;i < s.size();i++) { 
   
            str += s[i];
            str += '#';
        }
        
        vector<int> p(str.size(),0);
        int mx = 0, id = 0,start = 0,maxlen = 0;
        for (int i = 1; str[i] != '\0'; i++) { 
   
        //这里如果i在右边界mx之外就只能自己老实匹配了,如果在mx之内需要看p[j]是否大于对称的mx左边界,大于的话说明i位置
        //的p[i]至少也能延展到以id为中心的回文边界,否则只能是p[j]的值
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (str[i + p[i]] == str[i - p[i]]) p[i]++;
            if (i + p[i] > mx) { 
   
                mx = i + p[i];
                id = i;
            }
            if(p[i]-1 > maxlen)
            { 
   
                start = (i-p[i])/2;//i+p[i]是右边界,所以i-p[i]就是左边界,除以2是因为str加了#变成了两倍长度,所以
                //在原串的开始位置就是除以2
                maxlen = p[i]-1;
            }
        }
        return s.substr(start,maxlen);
    }
};

文章主要以总结c++代码为主,理解还需大家自己体会,有什么问题尽管指出我会虚心改正。

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

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/134395.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • CausalDiscoveryToolbox:因果建模、因果图代码实现

    CausalDiscoveryToolbox:因果建模、因果图代码实现Cdt工具包实现了端到端的因果建模方法,支持从观测数据中恢复直接依赖关系(因果图的骨架)和变量之间的因果关系。基于python实现了许多用于图结构恢复的算法,接口简单,易于上手。

    2022年8月14日
    3
  • 【Java】输入—Scanner用法(全)[通俗易懂]

    【Java】输入—Scanner用法(全)[通俗易懂]Scanner用法目录1、输入整数、字符串数组2、输入二维数组3、输入字符串4、输入字符串分割为数组5、连续输入数字和字符串6、换行输入数字和字符串7、换行输入数字和字符串(需要包含空格)1、输入整数、字符串数组第一行输入n,m第二行输入n个整数第三行输入m个字符串//导入包importjava.util.Scanner;import…

    2022年7月16日
    9
  • matlab非线性整数优化,fmincon整数优化

    matlab非线性整数优化,fmincon整数优化MATLAB非线性优化fmincon_数学_自然科学_专业资料。精心整理act…注意:[1]fmincon函数提供了大型优化算法和中型优化算法。默认时,若…[x,fval,exitflag]=fmincon(@ff8,x0,[],[],[],[],[],[],nonlcon)四、整数线性规划算法说明:下面给出用分枝定界法求解整数线性规划的M函数文件……fminc…

    2022年5月6日
    45
  • matlab仿真的五个步骤,matlab仿真步骤

    matlab仿真的五个步骤,matlab仿真步骤基于matlab的MPSK的仿真流程图_计算机软件及应用_IT/计算机_专业资料…DataImport/Export:SIMULINK和MATLAB工作间数据的输入和输出设定,以及数据存储时的格式、长度等参数设置;(3)?Diagnostics:允许用户选择在仿真过程中警告信息……simulinkmatlab仿真环境教程Simulink是面向框图的仿真软件。演示一…

    2022年6月4日
    53
  • 黎曼猜想和素数分布的关系_黎曼公式和素数的关系

    黎曼猜想和素数分布的关系_黎曼公式和素数的关系自然数简化到素数:黎曼猜想RiemannHypothesis及其解释(公号回复“黎曼猜想”下载PDF经典收藏版彩标资料)原创:秦陇纪数据简化DataSimp今天数据简化DataSimp导读:科学大院《黎曼猜想RiemannHypothesis简介》来自黄逸文(中国科学院数学与系统科学研究院),介绍了黎曼猜想RiemannHypothesis大概。知乎译文《黎曼猜想Riemann…

    2022年8月11日
    37
  • laravel-admin 自定义导出excel功能,并导出图片

    laravel-admin 自定义导出excel功能,并导出图片

    2021年10月30日
    34

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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