leetcode最长回文子串_最长回文子串算法

leetcode最长回文子串_最长回文子串算法C++实现——最长回文子串

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

Jetbrains全系列IDE稳定放心使用

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:

给定一个仅包含小写字母的字符串,求它的最长回文子串的长度。

所谓回文串,指左右对称的字符串。

所谓子串,指一个字符串删掉其部分前缀和后缀(也可以不删)的字符串

(注意:记得加上while处理多个测试用例)

输入描述:

输入一个仅包含小写字母的字符串

输出描述:

返回最长回文子串的长度

示例:

输入:

cdabbacc

输出:

4

说明:

abba为最长的回文子串

解题思路:

这题用双循环解决。从头开始一层遍历,从后开始一层遍历;每个节点,令m=i,n=j,当某个位置str[m]与str[n]相等时进入while循环,m++、n–,同时用t记录回文一半长度的尺寸,若为回文则到中间位置,m会大于等于n;如果m和n相等,说明回文字符数为奇数,则回文长度为2*t+1,若m>n,说明回文字符数为偶数,则回文长度为2*t,同时更新max,max为最长回文长度。

测试代码:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    string str;
    while(getline(cin,str))
    {
        int max=0;
        int size=str.size();
        for(int i=0;i<size;++i)
        {
            for(int j=str.size()-1;j>i;--j)
            {
                int m=i,n=j,t=0;
                while(str[m]==str[n])
                {
                    t++;
                    m++;
                    n--;
                    if(m>=n)
                    {
                        if(m==n)
                            t=2*t+1;
                        else
                            t=2*t;
                        if(t>max)
                            max=t;
                        break;
                    }
                }
            }
        }
        cout<<max<<endl;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 如何架设FTP服务器[通俗易懂]

    如何架设FTP服务器[通俗易懂]FTP服务器的架设在我们的实际网络生活中,特别是宽带网接入之后,FTP服务器作为文件的传输和共享工具得到广泛应用。FTP服务器在文件的传输上性能稳定,占用系统资源小,而且传输速度快,现在网上已经有很多的FTP服务器可供使用,而自己架设一个FTP服务器也很容易,下面介绍两种主流的FTP架构方式。1.利用微软公司的IIS微软的IIS功能非常强大,它除了提供WWW服务之外,还提供FTP的服务,利用…

  • charles导致mac无法上网_使用不同的MAC地址上网

    charles导致mac无法上网_使用不同的MAC地址上网前言charles关闭后,发现网页突然打开了,那大概率是设置了代理,但明明已经关闭了charles,这是由于mac网络偏好设置中,使用的是手动代理,将其改为自动即可解决方法1打开网络偏好设置,

  • 第二代微服务

    第二代微服务

  • 组合模式解决什么问题_组合模式实例

    组合模式解决什么问题_组合模式实例组合模式 Composite动机模式定义实例结构要点总结笔记动机在软件某些情况下,客户代码过多地依赖于对象容器复杂的内部实现结构,对象内部实现结构(而非抽象接口)地变化将引起客户代码地频繁变化.带来代码地维护性,扩展性等弊端如何将”客户代码与复杂地对象容器结构”解耦?让对象容器自己来实现自身地复杂结构,从而使得客户代码就像处理简单对象一样来处理复杂地对象容器模式定义将对象组合成树形结构以表示”整体-部分”地层次结构.Composite使得用户对单个对象和组合对象地使用具有一致性(稳定)实例树形

  • 或非门_与非门转化为或非门

    或非门_与非门转化为或非门 

  • pl sql develop_sql中declare是什么意思

    pl sql develop_sql中declare是什么意思因为SQL只能访问、操作数据库,却不能进行程序设计,而OraclePL/SQL是一种高级数据库程序设计语言,该语言专门用于对ORACLE数据库进行访问,并且可以进行过程处理。*注:在PL/SQL中只能用SQL语句中的DML部分,不能用DDL部分,如果要在PL/SQL中使用DDL(如CREATEtable等)的话,只能以动态的方式来使用。**1.DML(datamanipulationlanguage)数据操纵语言:比如SELECT、UPDATE、INSERT、DELETE

    2022年10月12日

发表回复

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

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