百度360必应搜狗淘宝本站头条
python判断字典是否为空crontab每周一执行aes和des区别安装指定版本npmadb pull
当前位置：网站首页 > IT知识 > 正文

C/C++面试宝典:求字符串的最大长度回文

liuian 2025-07-07 20:09 4 浏览

引言

字符串回文是C/C++面试中常见的问题之一，该内容主要考察面试者对于代码设计的鲁棒性、时间复杂度和空间复杂度的考虑，同时需要对代码的异常做和是判断，想要实现相关的代码不难，但是想要设计出鲁棒性较好的代码，需要花费一定的形式

示例需求描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

代码设计思路：通过回文字符串的特性，正反读取都相同，可以将字符串逆转后，求取最长公共子串，但可能会出现其他部分重置与另一部分相同，所以需要对比找到最长公共子串的索引与原索引相加是否为字符串长度-1,即 当A.at(right + 1) == A.at(left - 1)时，maxLen = right - left + 1;


测试用例：

示例1

输入：

"ababc"

返回值：

3

说明：

最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：

"abbba"

返回值：

5

示例3

输入：

"b"	返回值：1

示例代码：

int getLongestPalindrome(string A, int n) 
  {
       //边界条件判断
    if (n < 2)
        return A.length();
    //maxLen表示最长回文串的长度
    int maxLen = 0;
    for (int i = 0; i < n; ) {
        //如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
        // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
        if (n - i <= maxLen / 2)
            break;
        int left = i;
        int right = i;
        while (right < n - 1 && A.at(right + 1) == A.at(right))
            ++right; //过滤掉重复的
  
        //下次在判断的时候从重复的下一个字符开始判断
        i = right + 1;
        //然后往两边判断，找出回文子串的长度
        while (right < n - 1 && left > 0 && A.at(right + 1) == A.at(left - 1)) {
            ++right;
            --left;
        }
        //保留最长的
        if (right - left + 1 > maxLen) {
            maxLen = right - left + 1;
        }
    }
    //截取回文子串
    return maxLen;
    }
};

结语

对于一个一个字符串的最大回文的计算，我们也可以使用的是中心位置法，遍历去头去尾的字符串，若字符串左边右边相等，则两个指针定位左边右边，同时向外扩展直到不相等，则回文长度是right_point - left_point - 1；若字符串左边或者右边的某一位与该字符串相等，则指针定位这两个相等的字符，并同时向外扩展直到不相等，方法相同。

相关推荐

C/C++恶意代码盘点(一):进程遍历丨木马病毒丨密码记录

恶意代码的分类包括计算机病毒、蠕虫、木马、后门、Rootkit、流氓软件、间谍软件、广告软件、僵尸(bot)、Exploit等等，有些技术经常用到，有的也是必然用到。恶意代码常见功能技术如下：进程遍...

跨越十年的C++演进:C++11新特性全解析

原作者：Linux教程，原文「链接」：https://mp.weixin.qq.com/s/oFbiFlqiwgVcJIMMvTelEA很多刚刚进入C++领域的朋友，最初是从C语言转过来的。因...

如何在C#中调用C++方法（c#调用c++的类）

主要方式C#主要通过两种方式提供对非托管代码的调用，第一种是使用平台调用(PlatformInvoke，P/Invoke)，第二种是使用不安全代码(unsafe)，日常开发中我们使用最多的就是第一种...

C语言字符数组和字符串（c语言字符数组和字符串数组）

用来存放字符的数组称为字符数组，例如：charc[10];字符数组也可以是二维或多维数组。例如：charc[5][10];字符数组也允许在定义时进行初始化，例如：charc[10]={'c',...

C语言指针，如何操作字符串?linux C第45讲

1指针操作字符串在学习数组的时候，我们了解了字符串的定义，我们可以定义一个字符数组，用来存放一个字符串，例如：chararray[]={"abcde"};charbuf[]=...

信奥赛C++常用的算法总结（信息学奥赛c语言和c++有什么区别）

1、桶排序核心：①创建盛下所有数的数组②将每个数作为编号放入桶里优点：稳定、简单、容易考缺点：空间复杂度较大，时间复杂度较大。#include<bits/stdc++.h>usingn...

Arduino 使用 C 字符串（arduino 字符串 数组）

问题您想了解如何使用原始字符字符串：创建字符串、查找其长度以及比较、复制或附加字符串。核心C语言不支持Arduino样式的String功能，因此您想了解针对基本字符数组编写的其他平台的代码...

C++20 四大特性之一:Module 特性详解

C++20最大的特性是什么？最大的特性是迄今为止没有哪一款编译器完全实现了所有特性。文章来源：网易云信有人认为C++20是C++11以来最大的一次改动，甚至比C++11还要大。本文仅介绍...

C/C++的const常量总结（c++语言const）

“所谓常量，就是在代码运行过程中值恒定不变的标识符，该标识符的值可以是一个常数，也可以是字符串。”在C/C++中，通常使用define宏定义或者const来定义常量，比如：#definePI3....

学习分享 | 通过C++python的对比，帮你快速入门python

一、前言对于只接触过静态语言，而从未使用过动态语言的人来说，第一次看到python的语法可能会大为惊叹。不用申明变量类型？不用等老半天编译完成就能直接运行？不用小心的维护指针？还不用写CMakelis...

字符串常量，C语言字符串常量详解

字符常量是由一对单撇号括起来的单个字符，如'a'、'D'、'？'、'#39;。在C语言中，除了字符常量外还有字符串常量，顾名思义就是多个“...

C/C++中的内存四区（c++的内存区域分为）

1代码区存放CPU执行的机器指令。通常代码区是可共享的（即另外的执行程序可以调用它），使其可共享的目的是对于频繁被执行的程序，只需要在内存中有一份代码即可。代码区通常是只读的，使其只读的原因是防...

通过pybind11来实现python调用C++接口(一)

有小伙伴很好奇，怎么样实现python调用C++接口？哈哈，手把手教程来了。第一步：我们需要安装pybind11这个纯头文件的库，目前该库支持c++11及以上版本，在你的环境中通过命令行输入：apt-...

深入了解C++如何注释以及在哪儿注释-开课吧广场

注释虽然写起来很痛苦，但对保证代码可读性至关重要，同时这也是每一个C++开发工程师所需要做好的事情。那么C++开发过程中该如何注释？应该在哪写注释呢？关于注释风格，很多C++的Coders更喜欢行注释...

C++核心知识点速查手册(实用重点版)

一、基础必备核心1.指针与引用（遥控器原理）指针：存储地址的变量（像电视遥控器）inttv=100;//电视机int*remote=&tv;//遥控器指向电视*...

一周热门
最近发表
标签列表