LeetCode.5.413.91.139(动态规划)

5.最长回文子串

class Solution {
  public:
    /* int sumRemainder(string a) {
        int sum = 0;
        for (int i = 0; i < a.length(); i++)
            sum = (sum + a[i]) % 123;
        return sum;
    }
    bool judge(string a) {
        for (int len = a.length() / 2; len >= 1; len /= 2)
            for (int i = 0; i < a.length() / 2 / len; i++)
                if (sumRemainder(a.substr(0 + i * len, len)) != sumRemainder(a.substr(a.length() - (i + 1) * len, len)))
                    return 0;
        return 1;
    }
    string longestPalindrome(string s) {
        string ans;
        for (int start = 0; start < s.length(); start++)
            for (int len = 2; len <= s.length() - start; len++)
                if (judge(s.substr(start, len)) && len > ans.length())
                    ans = s.substr(start, len);
        return ans.empty() ? s.substr(0, 1) : ans;
    }
    //比一个一个找更慢 */
    /* string longestPalindrome(string s) {
        string s1 = s;
        reverse(s1.begin(), s1.end());
        int Max = 0;
        int pos = 0;
        for (int begin = 1 - (int)s.size(); begin < (int)s.size(); begin++) {
            int thisMax = 0;
            int thisPos = 0;
            for (int i = max(0, begin), j = max(0, -begin); i < s.size() && j < s.size(); i++, j++) {
                if (s[i] != s1[j]) {
                    thisMax = 0;
                } else {
                    thisMax++;
                    thisPos = i;
                    if (thisMax > Max) {
                        Max = thisMax;
                        pos = thisPos;
                    }
                }
            }
        }
        return s.substr(pos - Max + 1, Max);
    }
    //!例外:"aacabdkacaa" */
    string longestPalindrome(string s) {
        int size = s.size();
        vector<vector<bool>> dp(size, vector<bool>(size, 0));
        int pos = 0;
        int Max = 1;
        for (int i = size - 1; i >= 0; i--)
            for (int j = i; j < size; j++)
                if (j == i)
                    dp[i][j] = 1;
                else if (s[j] == s[i])
                    if (j == i + 1) {
                        dp[i][j] = 1;
                        if (j - i + 1 > Max) {
                            Max = j - i + 1;
                            pos = i;
                        }
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = 1;
                        if (j - i + 1 > Max) {
                            Max = j - i + 1;
                            pos = i;
                        }
                    } else
                        dp[i][j] = 0;
                else
                    dp[i][j] = 0;
        return s.substr(pos, Max);
        // 180/180 cases passed (372 ms)
        // Your runtime beats 37.88 % of cpp submissions
        // Your memory usage beats 53.29 % of cpp submissions (29.3 MB)
        //*原理如下
        // babad
        // 10100
        //  1010
        //   100
        //    10
        //     1
        //双指针法更好
    }
};

413.等差数列划分

class Solution {
  public:
    int numberOfArithmeticSlices(vector<int> &nums) {
        if (nums.size() < 3)
            return 0;
        int sum = 0;
        /* vector<vector<bool>> dp(nums.size(), vector<bool>(nums.size(), 0));
        for (int i = nums.size() - 3; i >= 0; i--) {
            for (int j = i + 2; j < nums.size(); j++) {
                if (j == i + 2 && nums[j] + nums[i] == 2 * nums[j - 1]) {
                    dp[i][j] = 1;
                    sum++;
                } else if (dp[i][j - 1] == 1 && dp[i + 1][j] == 1) {
                    dp[i][j] = 1;
                    sum++;
                }
            }
        }
        return sum;
        // 15/15 cases passed (76 ms)
        // Your runtime beats 46.53 % of cpp submissions
        // Your memory usage beats 5.07 % of cpp submissions (11.8 MB) */
        vector<int> dp(nums.size(), 0);
        for (int i = nums.size() - 3; i >= 0; i--) {
            if (nums[i] + nums[i + 2] == 2 * nums[i + 1]) {
                dp[i] = dp[i + 1] + 1;
                sum += dp[i];
            }
        }
        return sum;
        // 15/15 cases passed (4 ms)
        // Your runtime beats 46.53 % of cpp submissions
        // Your memory usage beats 91 % of cpp submissions (7 MB)
    }
};

91.解码方法

class Solution {
  public:
    int numDecodings(string s) {
        if (s[0] == '0')
            return 0;
        vector<int> dp(s.size(), 0);
        dp[s.size() - 1] = 1;
        for (int i = s.size() - 2; i >= 0; i--) {
            if (s[i] == '0') {
                if (s[i + 1] == '0')
                    return 0;
                else
                    dp[i] = dp[i + 1];
            } else if (s[i] == '1') {
                if (s[i + 1] == '0' || s[i + 2] == '0')
                    dp[i] = dp[i + 1];
                else
                    dp[i] = dp[i + 1] + (i + 2 > s.size() - 1 ? 1 : dp[i + 2]);
            } else if (s[i] == '2') {
                if (s[i + 1] == '0' || s[i + 1] > '6' || s[i + 2] == '0')
                    dp[i] = dp[i + 1];
                else
                    dp[i] = dp[i + 1] + (i + 2 > s.size() - 1 ? 1 : dp[i + 2]);
            } else {
                if (s[i + 1] == '0')
                    return 0;
                else
                    dp[i] = dp[i + 1];
            }
        }
        return dp[0];

        // 269/269 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 67.34 % of cpp submissions (6 MB)
        /*
        *1123
        ?1235(3=2+1)(5=3+2)
        */
    }
};

139.单词拆分

#include <unordered_set>
//TODO: 是不是应该抽点时间熟悉一下c++的容器
class Solution {
  public:
    bool wordBreak(string s, vector<string> &wordDict) {
        /* if (s.empty())
            return 1;
        bool ans = 0;
        for (int j = 0; j < wordDict.size(); j++) {
            if (s.size() >= wordDict[j].size() && s.substr(0, wordDict[j].size()) == wordDict[j]) {
                cout << s.substr(wordDict[j].size()) << endl;
                ans = ans || wordBreak(s.substr(wordDict[j].size()), wordDict);
            }
        }
        return ans;
        //超时 */
        vector<bool> dp(s.size() + 1, false);
        // dp[i]表示字符串s的前i个字符能否拆分成wordDict。
        unordered_set<string> m(wordDict.begin(), wordDict.end());
        dp[0] = true;
        //获取最长字符串长度
        int maxWordLength = 0;
        for (int i = 0; i < wordDict.size(); i++) {
            maxWordLength = max(maxWordLength, (int)wordDict[i].size());
        }
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = max(i - maxWordLength, 0); j < i; ++j) {
                if (dp[j] && m.find(s.substr(j, i - j)) != m.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
        // 45/45 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 83.55 % of cpp submissions (7.5 MB)
        //利用unordered_set实现快速查找
    }
};