leetcode20、22

2024-06-03 16:25| 来源: 网络整理| 查看: 265

有效括号 1、判断有效的括号1.1、题目1.2、思路1.3、题解 2、生成有效的括号2.1、题目2.2、思路2.3、题解 3、最长有效括号3.1、题目3.2、思路3.3、题解参考

1、判断有效的括号 1.1、题目

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

有效字符串需满足：

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

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

输入: "()" 输出: true 输入: "()[]{}" 输出: true 输入: "(]" 输出: false 输入: "([)]" 输出: false 1.2、思路

核心思路：栈，首先我们应该明确如下两条规则：

1、一个「合法」括号组合的左括号数量一定等于右括号数量。2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 if (c == '(') left++; else // 遇到右括号 left--; if (left int len = s.size(); if(len % 2 != 0) return false; stackstack; mapm = {{')','('},{']','['},{'}','{'}};//注意这里面括号的顺序，根据右侧括号，找左侧 for(int i = 0;i if(stack.empty()) return false; if(m[s[i]] == stack.top()) stack.pop();//遇到右括号就pop else return false; } } return stack.empty(); } }; 2、生成有效的括号 2.1、题目

题目链接数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 2.2、思路

对于括号合法性的判断，主要是借助「栈」这种数据结构，而对于括号的生成，一般都要利用回溯递归的思想。

重复两条规则：

1、一个「合法」括号组合的左括号数量一定等于右括号数量。2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 }; // 记录所有合法的括号组合 vector res; // 回溯过程中的路径 string track; // 可用的左括号和右括号数量初始化为 n backtrack(n, n, track, res); return res; } // 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个 void backtrack(int left, int right, string& track, vector& res) { // 若左括号剩下的多，说明不合法。剩的多因为用的少嘛，左侧先填充的，所以就这样了。 if (right stack a; for (auto v : s) { if (v == '(') { a.push(v); } else if (!a.empty() && a.top() == '(') { a.pop(); } else return false; } return a.empty(); } int longestValidParentheses(string s) { int maxLen = 0; for (int i = 0; i if (isVaild(s.substr(i, j))) { if (j > maxLen) { maxLen = j; } } } } return maxLen; } class Solution { public: int longestValidParentheses(string s) { int size = s.length(); vector dp(size, 0); int maxVal = 0; for(int i = 1; i if (s[i - 1] == '(') { dp[i] = 2; if (i - 2 >= 0) { dp[i] = dp[i] + dp[i - 2]; } } else if (dp[i - 1] > 0) { if ((i - dp[i - 1] - 1) >= 0 && s[i - dp[i - 1] - 1] == '(') { dp[i] = dp[i - 1] + 2; if ((i - dp[i - 1] - 2) >= 0) { dp[i] = dp[i] + dp[i - dp[i - 1] - 2]; } } } } maxVal = max(maxVal, dp[i]); } return maxVal; } };

复杂度分析：

时间复杂度：O(n)。遍历整个字符串一次，就可以将 dp 数组求出来. 空间复杂度： O(n)。需要一个大小为 n 的 dp 数组.

参考

https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/he-fa-kuo-hao-sheng-cheng

【本文地址】

公司简介

联系我们