[百度]2014百度校园招聘之最长回文串

简介:

【题目】

给你一个字符串,找出该字符串中对称的子字符串的最大长度。即求最大回文串。

【思路1】暴力法

即不使用技巧,穷举所有可能。时间复杂度为O(n^3)(时间上最长,不推荐使用),空间复杂度为O(1)。

本思路是从最大长度的字串开始,而不是从最小开始。假如说给定的字符串为len,先遍历长度为len的字串是否为回文串,如果是停止,

如果不是遍历长度为len-1的字串是否是回文串,一次类推。

#include <iostream>
using namespace std;
//是否是回文串
bool IsPalindromeSubNumber(string num){
    int len = num.length();
    for(int i = 0,j=len-1;i < j;i++,j--){
        if(num[i] != num[j]){
            return false;
        }
    }
    return true;
}
void MaxSubPalindromeNumber(string num){
    bool result;
    bool flag = false;
    int len = num.length();
	//遍历字串的长度
    for(int i = len;i > 0;i--){
		//遍历字串的起始位置
        for(int j = 0;j+i <= len;j++){
            result = IsPalindromeSubNumber(num.substr(j,i));
            if(result){
                flag = true;
                cout<<num.substr(j,i)<<endl;
            }
        }
        if(flag){
            break;
        }
    }
}

int main(){
    string num = "djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
    MaxSubPalindromeNumber(num);
    return 0;
}

【思路2】

假设现在已经遍历到第 i 个字符,要找出以该字符为“中心”的最长对称字符串,我们需要用另两个指针分别向前和向后移动,直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况,所以需要写出两种情况下的代码:

(1) 第 i 个字符是该对称字符串的真正的中心,也就是说该对称字符串以第 i 个字符对称, 比如: “aba”

(2)第 i 个字符串是对称字符串的其中一个中心。比如“abba”。

所以遍历到每个字符都要考虑两种情况,它可能是在奇数个回文串中或者是在偶数个回文串中

#include<string>
#include<iostream>
using namespace std;


string MaxPalindromeNumber(string str){
    int maxLen = 1,start = 0;
    int len = str.length();
    string s = str;
    int left,right;
    for(int i = 0;i < len;i++){
        //奇数字串
        int oddLen = 1;
        left = i-1;
        right = i+1;
        while(left >= 0 && right < len && str[left] == str[right]){
            left--;
            right++;
            oddLen += 2;
        }
        //更新最大长度
        if(oddLen > maxLen){
            maxLen = oddLen;
            //记录当前最大回文串的起始位置
            start = left+1;
        }
        //偶数字串
        left = i;
        right = i+1;
        int evenLen = 0;
        while(left >= 0 && right < len && str[left] == str[right]){
            left--;
            right++;
            evenLen += 2;
        }
        //更新最大长度
        if(evenLen > maxLen){
            maxLen = evenLen;
            //记录当前最大回文串的起始位置
            start = left+1;
        }
    }
    return str.substr(start,maxLen);
}

int main(){
	string str="djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
	string s=MaxPalindromeNumber(str);
	cout<<s<<endl;
	return 0;
}





【思路三】Manacher算法

算法的基本思路是这样的:把原串每个字符中间用一个串中没出现过的字符分隔#开来(统一奇偶),同时为了防止越界,在字符串的首部也加入一个特殊符$,但是与分隔符不同。同时字符串的末尾也加入'\0'。算法的核心:用辅助数组p记录以每个字符为核心的最长回文字符串半径。也就是p[i]记录了以str[i]为中心的最长回文字符串半径。p[i]最小为1,此时回文字符串就是字符串本身。 
示例:原字符串 'abba’,处理后的新串 ' $#a#b#b#a#\0’,得到对应的辅助数组p=[0,1,1,2,1,2,5,2,2,1]。 

详细请看:[算法]Manacher算法之最大回文子串

#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
//数据预处理
char* Init(char* s){
    int len = strlen(s);
    char* str = new char(2*len+4);
    str[0] = '$';
    int index = 1;
    for(int i = 0;i < len;i++){
        str[index++] = '#';
        str[index++] = s[i];
    }
    str[index++] = '#';
    str[index] = '\0';
    return str;
}

char* MaxPalindromeNumber(char* s){
    char *str = Init(s);
    int maxId = 0,center = 1;
    int len = strlen(str);
    int *p = new int[len+1];

    // MaxId为i字符之前最大回文串向右延伸的最大位置
    // id为MaxId对应的最大回文串的中心位置
    for(int i = 1;i < len;i++){
        //初步定i位置字符为中心的半径
        if(maxId > i){
            p[i] = min(maxId - i,p[2*center - i]);
        }
        else{
            p[i] = 1;
        }
        //继续确定i位置字符为中心的半径 这地方用到'$'
        while(str[i-p[i]] == str[i+p[i]]){
            p[i]++;
        }
        //更新MaxId,id
        if(p[i]+i > maxId){
            maxId = p[i] + i;
            center = i;
        }
    }
    // 最大长度
    int maxLen = 0;
    center = 1;
    for(int i = 1;i < len;i++){
        if(str[i] != '#' && p[i] - 1 > maxLen){
            maxLen = p[i] - 1;
            center = i;
        }
    }
    //提取最大回文串
    char* maxStr = new char[maxLen+1];
    int index = 0;
    for(int i = center - maxLen;i <= center + maxLen;i++){
        if(str[i] != '#'){
            maxStr[index++] = str[i];
        }
    }
    maxStr[index] = '\0';
    return maxStr;
}

int main(){
	char* str="skjflkdsjfkldsababasdlkfjsdwieowowwpw";
	cout<<MaxPalindromeNumber(str);
	return 0;
}










相关链接:

[小米]2015小米校招之回文数判断

[网易]字符串回文分割




目录
相关文章
|
6月前
逛街【 腾讯2020校园招聘-后台&综合-第一次笔试】(单调栈的应用)
逛街【 腾讯2020校园招聘-后台&综合-第一次笔试】(单调栈的应用)
31 0
|
8月前
|
消息中间件 Dubbo Java
阿里、腾讯、美团春招真题“惨遭”泄露,Github上标星66.3K
黄金跳槽的高峰期已经到来,今年市场变得格外不同,比之前仅仅想涨薪、想换领导的基础因素上又加了两种情况;如受前两年疫情影响想跳槽未跳的,去年“双减”政策裁员的.....所以导致今年的市场更加火热;
阿里、腾讯、美团春招真题“惨遭”泄露,Github上标星66.3K
一道网红面试题(腾讯、百度面试中都出现过)
在腾讯和百度的面试中,出现了这样一道面试题,,被大家亲切的称呼为网红面试题,这道面试题就是。['1', '2', '3'].map(parseInt)的输出结果是什么?['1', '2', '3'].fliter(parseInt)的输出结果是什么? 这个面试题,面试官可能不仅仅需要你说出他的结果,还需要你知道为什么会出现这样的结果。
146 0
|
算法
百度之星之J:百度的新大厦
描述 继百度搜索框大厦之后,百度又于2012年初在深圳奠基了新的百度国际大厦,作为未来百度国际化的桥头堡。不同于百度在北京的搜索框大厦,新的百度国际大厦是一栋高楼,有非常多的楼层,让每个楼中的电梯都能到达所有楼层将是一个极为不明智的设计。
146 0
|
人工智能 vr&ar
【0209创精选】论执行力,这次百度真的赢了
在前天的创精选中,我们提到李彦宏在百度新春开年演讲上放了狠话,将对没有市场竞争力的产品该撤就撤,该关就关,该并就并,结果昨天就有消息爆出,百度内部整体裁撤了医疗事业部。
《壹百度—百度十年千倍的29条法则》,互联网营销
  《壹百度—百度十年千倍的29条法则》中的29条法则   1、人一定要做自己喜欢并擅长的事   内心的喜好是推动事业进步的最大动力,它能帮你克服困难,坚持到底;而如果你喜欢的事情有很多,要挑选自己最擅长做的事,这样就能在感受快乐的同时也取得超乎常人的成就。
1181 0
|
算法 UED
百度霸屏?谁也霸不过百度
最近百度文库、知道、经验、拇指的百度排名很疯狂,尤其是文库。今天百度貌似有个大更新,这些百度自家产品被清理了绝大部分。
2018 0
|
算法 C++
搜狗2016校园招聘之算法编程解析
1、第一个题:最近邻居 题目: 解题思路: 1)这个题如果用java,相对会好解一些,因为可以直接用JDK中的Point2D类,来定义坐标系空间中的一个点。 2)简单思路:暴力破解,计算任意两个点之间的距离,时间负责度为O(n^2); 3)优化思路:《编程之美》上给出了一个思路,利用分治法,将所有点所在的平面切成点数大致相同的两半,分为Left,Right,则距离最近的两个点,要么在Left区域中,要么在Right区域中,要么在跨两者中间的区域中,时间复杂度可以优化到O(nlgn)。
870 0