[DLdigest-6] 每日一道算法

2017 年 10 月 29 日 深度学习每日摘要 DLdigest

题图：A sculpture in New Zealand designed to look like a cartoon

在上一期的每日一道算法中，题目是给定一个字符串s，找出其中最长的子回文字符串，假定s的最大长度为1000。

首先说明一下什么是回文字符串，其定义就是如果一个字符串从左向右读与从右向左读是一模一样的，那么它就是回文字符串，如"aa"、"aba"、"a"都属于回文字符串。假设s为”babad”，那么其最大子回文字符串就是”bab”，或者也可以说是”aba”，它们长度一样；假设s为”cbbd”，那么其最大子回文字符串就是”bb”。

如果字符串s的长度为1，那么它本身就是回文字符串，因此返回本身即可。除此之外，还要注意的是回文字符串的长度可以为奇数也可以为偶数，如果长度为奇数，那么字符串就是以中心字符为对称点，而如果长度为偶数，那么就是以字符串中某两个字符为中心的对称。

具体的求解突破口就是要找子回文字符串的开始位置及其长度，然后调用substr来得到该回文字符串。

#include<iostream>
using namespace std;

class Solution {
public:    
    string findMaxPlalindrome(string s) {
        //返回字符串本身
        if(s.size()<=1)
            return s;
        int start=0, len=0;
        int left, right;
        for(int i=0; i<s.size()-1; i++) {
            //长度为奇数
            left=i;
            right=i;
            while(left>=0 && right<s.size() && s[left]==s[right]) {
                left--;
                right++;
            }
            if((right-left-1)>len) {
                start=left+1;
                len=right-left-1;
            }
            
            //长度为偶数
            left=i;
            right=i+1;
            while(left>=0 && right<s.size() && s[left]==s[right]) {
                left--;
                right++;
            }
            if((right-left-1)>len) {
                start=left+1;
                len=right-left-1;
            }
        }        
        return s.substr(start, len);
    }
};
        
int main() {
    string s1("abbc");
    string s2("abcbd");
    string s3("abcd");
    string s4("a");
    Solution s;
    cout<<s1<<"-->"<<s.findMaxPlalindrome(s1)<<endl;
    cout<<s2<<"-->"<<s.findMaxPlalindrome(s2)<<endl;
    cout<<s3<<"-->"<<s.findMaxPlalindrome(s3)<<endl;
    cout<<s4<<"-->"<<s.findMaxPlalindrome(s4)<<endl;
    return 0;
}

运行结果：
abbc-->bb
abcbd-->bcb
abcd-->a
a-->a

每日一道算法——ZigZag Conversion
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)