代码随想录Day39-动态规划：力扣第583m、72h、647m、516m、739m题

583. 两个字符串的删除操作

题目链接
代码随想录文章讲解链接

方法一：动态规划+滚动数组

用时：8m48s

思路

先计算两个字符串的最长公共子序列的长度L，答案为两字符串长度之和减去两倍的L。

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(n)$。

C++代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<int> dp(word2.length() + 1, 0);
        int tmp1 = 0, tmp2 = 0;
        for (int i = 1; i <= word1.length(); ++i) {
            tmp1 = dp[0];
            for (int j = 1; j <= word2.length(); ++j) {
                tmp2 = dp[j];
                if (word1[i - 1] == word2[j - 1]) dp[j] = tmp1 + 1;
                else dp[j] = max(dp[j - 1], dp[j]);
                tmp1 = tmp2;
            }
        }
        return word1.length() + word2.length() - 2 * dp[word2.length()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

看完讲解的思考

无。

代码实现遇到的问题

无。

---

72h. 编辑距离

题目链接
代码随想录文章讲解链接

方法一：动态规划

用时：26m28s

思路

dp数组：二维dp数组，dp[i][j]表示word1[:i]和word2[:j]的最小编辑距离。
状态转移：

1. words1[i] == words2[j]：
   • words1[:i-1] 变成 words2[:j-1]，words1[i]和words2[j]保持不变，所需步数为dp[i - 1][j - 1]。
   • words1[:i-1] 变成 words2[:j]，删除 words1[i]，所需步数为dp[i][j - 1] + 1。
   • words1[:i] 变成 words2[:j-1]，添加 words2[j]，所需步数为dp[i - 1][j] + 1。
   • dp[i][j]为上述三种情况的最小值，即dp[i][j] = myMin(dp[i - 1][j - 1], dp[i][j - 1] + 1, dp[i - 1][j] + 1)。
2. words1[i] != words2[j]：
   • words1[:i-1] 变成 words2[:j-1]，将words1[i]替换成words2[j]，所需步数为dp[i - 1][j - 1] + 1。
   • words1[:i-1] 变成 words2[:j]，删除 words1[i]，所需步数为dp[i][j - 1] + 1。
   • words1[:i] 变成 words2[:j-1]，添加 words2[j]，所需步数为dp[i - 1][j] + 1。
   • dp[i][j]为上述三种情况的最小值，即dp[i][j] = myMin(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1, dp[i - 1][j] + 1)。

• 时间复杂度：$O(nm)$。
• 空间复杂度：$O(nm)$。

C++代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));  // dp数组
        for (int j = 1; j <= len2; ++j) dp[0][j] = j;  // dp数组初始化
        for (int i = 1; i <= len1; ++i) {
            dp[i][0] = i;  // dp数组初始化
            for (int j = 1; j <= len2; ++j) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = myMin(dp[i - 1][j - 1], dp[i][j - 1] + 1, dp[i - 1][j] + 1);
                else dp[i][j] = myMin(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
            }
        }
        return dp[len1][len2];
    }

    int myMin(int a, int b, int c) {
        int res = a;
        if (b < res) res = b;
        if (c < res) res = c;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：动态规划+滚动数组

用时：7m5s

思路

方法一空间优化。

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(n)$。

C++代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        vector<int> dp(len2 + 1, 0);
        int tmp1 = 0, tmp2 = 0;
        for (int j = 1; j <= len2; ++j) dp[j] = j;
        for (int i = 1; i <= len1; ++i) {
            tmp1 = dp[0];
            dp[0] = i;
            for (int j = 1; j <= len2; ++j) {
                tmp2 = dp[j];
                if (word1[i - 1] == word2[j - 1]) dp[j] = myMin(tmp1, dp[j - 1] + 1, dp[j] + 1);
                else dp[j] = myMin(tmp1, dp[j - 1], dp[j]) + 1;
                tmp1 = tmp2;
            }
        }
        return dp[len2];
    }

    int myMin(int a, int b, int c) {
        int res = a;
        if (b < res) res = b;
        if (c < res) res = c;
        return res;
    }
};
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

看完讲解的思考

无。

代码实现遇到的问题

无。

---

647m. 回文子串

题目链接
代码随想录文章讲解链接

方法一：动态规划

用时：29m58s

思路

dp数组：二维dp数组，dp[i][j]表示以第i至j个字符组成的子串是否是回文串。
状态转移：

1. 当s[i] != s[j]时，第i至j个字符组成的子串肯定不是回文串。
2. 当s[i] == s[j]时，如果第i+1至j-1个字符组成的子串是回文串，则第i至j个字符组成的子串也是，否则不是。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$。

C++代码

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        int res = 0;
        for (int i = 0; i < len; ++i) dp[i][i] = true;
        for (int j = 0; j < len; ++j) {
            for (int i = 0; i < j; ++i) {
                if (s[i] == s[j]) dp[i][j] = i + 1 > j - 1 ? true : dp[i + 1][j - 1];
                res += dp[i][j];
            }
        }
        return res + len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：动态规划+滚动数组

用时：5m47s

思路

方法一空间优化。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n)$。

C++代码

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();
        vector<bool> dp(len, false);
        int res = 0;
        for (int j = 0; j < len; ++j) {
            for (int i = 0; i <= j; ++i) {
                if (s[i] == s[j]) dp[i] = i + 1 > j - 1 ? true : dp[i + 1];
                else dp[i] = false;
                res += dp[i];
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法三：遍历+双指针

思路

遍历字符串，统计以每个字符或每两个字符为中心的回文子串的数量，统计回文子串时用双指针。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。

C++代码

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();
        int res = 0;
        for (int i = 0; i < len; ++i) {
            res += extend(s, i, i, len);
            res += extend(s, i, i + 1, len);
        }
        return res;
    }

    // 双指针
    int extend(const string& s, int i, int j, int len) {
        int res = 0;
        while (i >= 0 && j < len && s[i--] == s[j++]) ++res;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

看完讲解的思考

无。

代码实现遇到的问题

无。

---

516m. 最长回文子序列

题目链接
代码随想录文章讲解链接

方法一：动态规划

用时：33m32s

思路

dp数组：二维dp数组，dp[i][j]表示第i至j个字符组成的子串中最长回文子序列（LPS）的长度。
状态转移：对于第i至j个字符组成的子串，我们要基于第i+1至j-1个字符组成的子串。

1. s[i] == s[j]：对于第i+1至j-1个字符组成的子串来说，两头的字符相等，所以LPS的长度+2，即dp[i][j] = dp[i + 1][j - 1] + 2。
2. s[i] != s[j]：对于第i+1至j-1个字符组成的子串来说，两头的字符不一样，同时增加他们两个无法使LPS的长度增加，考虑只增加一个，分别是只增加左边的字符和只增加右边的字符，LPS的长度为两者中的最大值，即dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$。

C++代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for (int j = 0; j < len; ++j) {
            dp[j][j] = 1;
            for (int i = j - 1; i >= 0; --i) {
                dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] + 2 : max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][len - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：动态规划+滚动数组

用时：4m3s

思路

方法一用滚动数组优化空间复杂度。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n)$。

C++代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        vector<int> dp(len, 0);
        int tmp1 = 0, tmp2 = 0;
        for (int j = 0; j < len; ++j) {
            tmp1 = dp[j];
            dp[j] = 1;
            for (int i = j - 1; i >= 0; --i) {
                tmp2 = dp[i];
                dp[i] = s[i] == s[j] ? tmp1 + 2 : max(dp[i + 1], dp[i]);
                tmp1 = tmp2;
            }
        }
        return dp[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

看完讲解的思考

无。

代码实现遇到的问题

无。

---

739m. 每日温度

题目链接
代码随想录文章讲解链接

方法一：单调栈（自己想的

用时：16m43s

思路

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

C++代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int size = temperatures.size();
        vector<int> res(size, 0);
        stack<pair<int, int>> stk;
        stk.push(pair<int, int>(temperatures[size - 1], size - 1));

        for (int i = size - 2; i >= 0; --i) {
            while (!stk.empty() && temperatures[i] >= stk.top().first) stk.pop();
            res[i] = stk.empty() ? 0 : stk.top().second - i;
            stk.push(pair<int, int>(temperatures[i], i));
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：单调栈

思路

其实不用存具体元素，只用存下标。

• 时间复杂度：$O()$
• 空间复杂度：$O()$

C++代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int size = temperatures.size();
        vector<int> res(size, 0);
        stack<int> stk;
        stk.push(size - 1);

        for (int i = size - 2; i >= 0; --i) {
            while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) stk.pop();
            res[i] = stk.empty() ? 0 : stk.top() - i;
            stk.push(i);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

看完讲解的思考

无。

代码实现遇到的问题

无。

---

最后的碎碎念

动态规划，完结撒花！！！
拖了好久，终于刷完了动态规划，最近忙比赛，时间太紧了，基本没什么时间刷题。