算法题目汇总

动态规划算法实例

这是遇到的一些有趣的算法题，之后遇到会陆续汇总在这里。

Example 1

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。 - '.' 匹配任意单个字符 - '' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。 示例 2:

输入：s = "aa", p = "a" 输出：true 解释：因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。 示例 3：

输入：s = "ab", p = "." 输出：true 解释："." 表示可匹配零个或多个（'*'）任意字符（'.'）。 ### 解题思路 动态规划算法的基本思路是，定义状态 dp[i][j]，表示 s 的前 i 个字符是否能被 p 的前 j 个字符匹配。初始化时，dp[0][0]为true，因为空字符串和空模式是匹配的。

1. 如果p[j-1]是普通字符或'.'，那么有：

    dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');

2. 如果p[j-1]是'*'，那么有两种情况：

• *匹配零个前面的字符：

    dp[i][j] = dp[i][j-2];

• *匹配一个或多个前面的字符：

    dp[i][j] = dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.');

代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();
        // 创建 DP 表
        std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
        
        // 初始化：空字符串和空模式匹配
        dp[0][0] = true;

        // 处理模式 p 前 j 个字符能否匹配空字符串 s
        for (int j = 2; j <= n; j += 2) {
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        }

        // 填充 DP 表
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    // 两种情况：'*'匹配零个前面的字符或一个或多个前面的字符
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    // 普通字符或'.'匹配
                    dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }

        // 返回整个字符串和模式的匹配结果
        return dp[m][n];
    }
};

Example 2

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

• 示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"

• 示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"

• 示例 3： 输入：s = "" 输出：0

解题思路

动态规划算法的基本思路是，使用一个动态规划数组 dp，其中 dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度。

• 初始化： 将 dp 数组全部初始化为 0，因为默认情况下，以任何字符结尾的子串都不可能是有效的。
• 状态转移：
  • 如果 s[i] 是 (，则 dp[i] = 0，因为以 ( 结尾的字符串肯定无法形成有效括号子串。
  • 如果 s[i] 是 )：
    • 如果 s[i-1] 是 (（形如 ...()），则 dp[i] = dp[i-2] + 2（如果 i-2 有效则加上其值）。
    • 如果 s[i-1] 是 )（形如 ...))），则判断 s[i-dp[i-1]-1] 是否是 (，如果是，dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]。
• 求解最大长度： 在遍历过程中，不断更新最大的 dp[i] 值，即为所求的最长有效括号子串的长度。
• 边界条件：当字符串长度小于等于 1 时，直接返回 0。

代码实现

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
    if (n <= 1) return 0;
    
    std::vector<int> dp(n, 0);
    int maxLen = 0;

    for (int i = 1; i < n; ++i) {
        if (s[i] == ')') {
            if (s[i-1] == '(') {
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            } else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] == '(') {
                dp[i] = dp[i-1] + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
            }
            maxLen = std::max(maxLen, dp[i]);
        }
    }

    return maxLen;
    }
};