leetcode55：跳跃游戏

题目链接

leetcode

题目描述

一个非负整数数组 nums，最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false 。

C++ 代码

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

/*
    双指针

    枚举回文串的中心 i，分两种情况向两边扩展，直到遇到不同字符为止。
        1.若回文串长度为奇数，
            则依次判断 s[i−k] == s[i+k], k = 1, 2, 3, ...
        2.若回文串长度为偶数，
            则依次判断 s[i−k] == s[i+k−1], k = 1, 2, 3, ...
    遇到不同字符时，找到了以 i 为中心的回文串边界。

    时间复杂度：O(n^2)
        其中 n 是字符串的长度。
        由于字符串长度小于 1000，所以可以枚举所有可能的情况。
    空间复杂度：O(1)
*/
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i++) {
            // 长度为奇数，以 s[i] 为中心的最长回文子串
            string s1 = check(s, i, i);
            // 长度为偶数，以 s[i] 和 s[i+1] 为中心的最长回文子串
            string s2 = check(s, i, i+1);
            res = res.size() > s1.size() ? res : s1;
            res = res.size() > s2.size() ? res : s2;
        }

        return res;
    }

    string check(const string& s, int l, int r) {
        // 防止下标越界，向两侧扩展
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--, r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文子串
        return s.substr(l+1, r-l-1);
    }
};

/*
    状态表示：
        f[i][j] 表示 s[i...j] 是否为回文串
    状态计算：
        f[i][j] = s[i-1] == s[j-1] && (j-i < 2 || f[i+1][j-1])

    时间复杂度：O(n^2)
    空间复杂度：O(n^2)
*/
class Solution_2 {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> f(n+1, vector<int>(n+1, 0)); // 初始化为 0
        int start = 0, length = 0;

        // 状态计算
        for (int len = 1; len <= n; len++) { // 枚举所有长度的子串
            for (int i = 0; i+len-1 < n; i++) {
                int l = i, r = i+len-1;
                if (len == 1) {
                    f[l][r] = 1;
                } else if (len == 2) {
                    f[l][r] = (s[l] == s[r]);
                } else {
                    f[l][r] = f[l+1][r-1] && (s[l] == s[r]);
                }

                if (f[l][r] != 0 && length < r-l+1) {
                    start = l;
                    length = r-l+1;
                }
            }
        }
        
        return s.substr(start, length);
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = { "babad", "cbbd" };

    for (auto s : s_cases) {
        cout << "Input: \"" << s << "\"" << endl;
        string result = solution.longestPalindrome(s);
        cout << "Output: \"" << result << "\"" << endl;
    }

    return 0;
}