2019-12-17 240 views 评论

Leetcode题目解析（191217）：20&22&32

标签：leetcode

Leetcode 20：有效的括号

题目描述

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

有效字符串需满足：

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

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

代码实现

bool isValid(string s) {
    if (s.empty())
        return true;
    if (s.size() % 2 == 1)
        return false;
    stack&lt;char&gt; tt;
    for (int i = 0; i &lt; 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();
}

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

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 &lt; s.size(); ++i) {
        int prev_mark = mark;
        mark = max(0, mark + ((s[i] == '(') ? 1 : -1));
        if (mark == 0) {
            if (prev_mark &gt; 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 &gt;= 0; --i) {
        int prev_mark = mark;
        mark = max(0, mark + ((s[i] == ')') ? 1 : -1));
        if (mark == 0) {
            if (prev_mark &gt; 0) {
                res = max(right - i + 1, res);
            }
            else {
                right = i - 1;
            }
        }
    }
    return res;
}