算法练习三

发表于 | 分类于

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba”也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

思路：常规暴力法：求所有子串，逐个验证是否是回文子串，n的平方*n，时间复杂度O(n3);
动态规划：动态规划是一个不错的思路，首先，一个首尾索引分别为i和j的字符串是不是回文，只需要比对i和j是否相等，并且i+1到j-1的字符串是否为回文子串。这样我们记忆dp[i][j]是否为回文字符串的所有结果。如果是一个字符肯定是回文子串，如果是两个字符，相等就是回文子串。由于保存了dp[i][j]的结果，时间复杂度O(n2),空间复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    string longestPalindrome(string s) {
        //字符串长度
        int size=s.size();
        bool dp[size][size];
        // fill_n(&dp[size][size],size*size,false);
        int max_len=1; //保存最长回文子串长度
        int start=0;   //保存最长回文子串起点
        
        //i是右标，开始遍历i
        for(int i=0;i<size;++i)
        {
            //j是左标
            for(int j=0;j<=i;++j)
            {
                if(i-j<2){
                    //两个字符的时候，直接比对值 一个字符就是true
                    dp[j][i]=(s[i]==s[j]);
                }
                else{
                    //动态规划思路，j+1的和i-1一定是已经填充过得值，因为i是从左往右遍历的
                    dp[j][i]=(s[i]==s[j] && dp[j+1][i-1]);
                }
                if(dp[j][i] && max_len<(i-j+1))
                {
                    max_len=i-j+1;
                    start=j;
                }
            }
        }
        return s.substr(start,max_len);
    }
};

小思考：空间复杂度还是可以优化的，因为只需要输出最大回文子串，可以只保存上一轮的结果值。不保存全部。

6. Z字形变换

将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数：

P A H N
A P L S I I G
Y I R
之后从左往右，逐行读取字符：”PAHNAPLSIIGYIR”

实现一个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);
示例 1:

输入: s = “PAYPALISHIRING”, numRows = 3
输出: “PAHNAPLSIIGYIR”
示例 2:

输入: s = “PAYPALISHIRING”, numRows = 4
输出: “PINALSIGYAHRPI”
解释:

P I N
A L S I G
Y A H R
P I

这是一道常规找规律的题目，我们按行遍历即可，时间复杂度O(n),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        string ret;
        int n = s.size();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret += s[j + i];
                //不是第一行也不是最后一行，中间的字符
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret += s[j + cycleLen - i];
            }
        }
        return ret;
    }
};