Leetcode题目解析(191217):20&22&32

Leetcode 20:有效的括号

题目描述

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

代码实现

bool isValid(string s) {
    if (s.empty())
        return true;
    if (s.size() % 2 == 1)
        return false;
    stack<char> tt;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
            tt.push(')');
        else if (s[i] == '[')
            tt.push(']');
        else if (s[i] == '{')
            tt.push('}');
        else if (tt.empty() || tt.top() != s[i])
            return false;
        else
            tt.pop();
    }
    return tt.empty();
}

复杂度

时间复杂度:O(n),n为字符串长度
空间复杂度:O(n),n为字符串长度

复杂度分析

Leetcode 22:括号生成

题目描述

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。例如,给出 n = 3,生成结果为:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题思路

用回溯法可以比较容易的做出来,因为前面回溯法说的比较多了,这里就不再累述。但是有一点注意的是,backtrack()中第三个判断一定要是right<left才可以,而不是right<n,因为right的数量目标是等于left,在已经有了left个左括号的时候,右括号数量right不能超过left。

代码实现

void backtrack(int left,int right, int n, string& s, vector<string>& result)
{
    if (left == n && right == n)
    {
        result.push_back(s);
        return;
    }
    if (left < n) {
        s += "(";
        backtrack(left + 1, right, n, s, result);
        s.pop_back();
    }
    //下面的意思是,右括号不可能多于左括号的数量,当然也不能少于左括号的数量
    if (right < left) {
        s += ")";
        backtrack(left, right + 1, n, s, result);
        s.pop_back();
    }
    
}
vector<string> generateParenthesis(int n) {
    vector<string> res;
    string s;
    backtrack(0, 0, n, s, res);
    return res;
}

复杂度

复杂度分析

Leetcode 32:最长有效括号

题目说明

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。

解题思路

参考:https://leetcode-cn.com/problems/longest-valid-parentheses/solution/c-liang-ci-bian-li-jie-fa-by-da-li-wang/

代码实现

int longestValidParentheses(string s) {
    int res = 0;
    int left = 0;
    int mark = 0;
    //从左到右
    for (int i = 0; i < s.size(); ++i) {
        int prev_mark = mark;
        mark = max(0, mark + ((s[i] == '(') ? 1 : -1));
        if (mark == 0) {
            if (prev_mark > 0) {
                res = max(i - left + 1, res);
            }
            else {
                left = i + 1;
            }
        }
    }
    mark = 0;
    int right = s.size() - 1;
    //从右到左
    for (int i = s.size() - 1; i >= 0; --i) {
        int prev_mark = mark;
        mark = max(0, mark + ((s[i] == ')') ? 1 : -1));
        if (mark == 0) {
            if (prev_mark > 0) {
                res = max(right - i + 1, res);
            }
            else {
                right = i - 1;
            }
        }
    }
    return res;
}

复杂度

复杂度分析
空间复杂度:O(n)【dp数组长度】
时间复杂度:O(n)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注