做物流有哪些网站,中国做外贸网站有哪些,中国企业500强排名2021,携程网站用js怎么做本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3
输出[((())),(()()),(())(),()(()),()()()]示例 2
输入n 1
输出[()]提示
1 n 8 解法 暴力递归生成 2 2 n 2^{2n} 22n 个序列
每个位置可以使用 ( 或者 ) 因此总共有 2 2 n 2^{2n} 22n 个序列。我们全部生成出来然后检查每个是否有效即可。
为了生成所有序列我们可以使用递归。长度为 n n n 的序列就是在长度为 n − 1 n - 1 n−1 的序列前加一个 ( 或 ) 。
为了检查序列是否有效我们遍历这个序列并使用一个变量 balance \textit{balance} balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance \textit{balance} balance 的值小于零或者结束时 balance \textit{balance} balance 的值不为零那么该序列就是无效的否则它是有效的。
class Solution {
private:vectorstring ans;bool valid(const string s) {int balance 0;for (char c : s) {if (c () balance;else --balance;if (balance 0) return false;}return balance 0;}void dfs(string s, int n) {if (n s.size()) {if (valid(s)) ans.push_back(s); // 检查是否有效序列return;}s (;dfs(s, n);s.pop_back();s );dfs(s, n);s.pop_back();}
public:vectorstring generateParenthesis(int n) {string current;dfs(current, n * 2);return ans;}
};复杂度分析
时间复杂度 O ( 2 2 n n ) O(2^{2n}n) O(22nn) 对于 2 2 n 2^{2n} 22n 个序列中的每一个我们用于建立和验证该序列的复杂度为 O ( n ) O(n) O(n) 。空间复杂度 O ( n ) O(n) O(n) 除了答案数组之外我们所需要的空间取决于递归栈的深度每一层递归函数需要 O ( 1 ) O(1) O(1) 的空间最多递归 2 n 2n 2n 层因此空间复杂度为 O ( n ) O(n) O(n) 。 解法2 回溯剪枝
方法一还有改进的余地我们可以只在序列仍然保持有效时才添加 (, ) 而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点
如果已用左括号数量不大于 n n n 我们可以放一个左括号。如果已用左括号的数量大于已用右括号数量我们可以放一个右括号。
class Solution {
private:vectorstring ans;void dfs(const string s, int l, int r) {if (l 0 || l r) return;if (l 0 r 0) {ans.push_back(s);return;}dfs(s (, l - 1, r);dfs(s ), l, r - 1);}
public:vectorstring generateParenthesis(int n) {dfs(, n, n);return ans;}
};复杂度分析这依赖于理解 g e n e r a t e P a r e n t h e s i s ( n ) generateParenthesis(n) generateParenthesis(n) 中有多少个元素。这个分析超出了本文的范畴但事实证明这是第 nnn 个卡特兰数 1 n 1 ( 2 n n ) \dfrac{1}{n1}\dbinom{2n}{n} n11(n2n) 这是由 4 n n n \dfrac{4^n}{n\sqrt{n}} nn 4n 渐近界定的。
时间复杂度 O ( 4 n n ) O(\dfrac{4^n}{\sqrt{n}}) O(n 4n) 在回溯过程中每个答案需要 O ( n ) O(n) O(n) 的时间复制到答案数组中。空间复杂度 O ( n ) O(n) O(n) 除了答案数组之外我们所需要的空间取决于递归栈的深度每一层递归函数需要 O ( 1 ) O(1) O(1) 的空间最多递归 2 n 2n 2n 层因此空间复杂度为 O ( n ) O(n) O(n) 。 解法3 按括号序列的长度递归记忆化搜索或动态规划
任何一个括号序列都一定是由 ( 开头并且第一个 ( 一定有一个唯一与之对应的 ) 。这样一来每一个括号序列可以用 ( a ) b (a)b (a)b 来表示其中 a a a 与 b b b 分别是一个合法的括号序列可以为空。
这样就把生成 n n n 对括号的所有序列这一问题分解为「生成 a a a 对括号的所有序列」「生成 b b b 对括号的所有序列」两个规模更小但是本质相同的子问题 a b n − 1 abn-1 abn−1 接着在 a a a 对括号的所有序列外面加上一个括号这样就得到了 n n n 对括号的所有序列并且完成了问题的分解。 总结一下就是找到了一个最优子结构将原问题转换为较小子问题求解。这道题的动态规划解难就是因为这个最优子结构不好想到。 一个示例如下 i 0 i 0 i0 结果是空 i 1 i 1 i1 结果有一种 ( ) () () i 2 i 2 i2 结果有两种 ( ) ( ) , ( ( ) ) ()(),\ (()) ()(), (()) i 3 i 3 i3 的结果使用公式 ( a ) b 有如下三种情况共5种结果以花括号来表示新添加的括号 a 2 , b 0 a 2, b 0 a2,b0 { ( ) ( ) } , { ( ( ) ) } \{()()\},\ \{(())\} {()()}, {(())} a 1 , b 1 a 1, b 1 a1,b1 { ( ) } ( ) \{()\}() {()}() a 0 , b 2 a 0, b 2 a0,b2 { } ( ) ( ) , { } ( ( ) ) \{\}()(), \{\}(()) {}()(),{}(())
为了生成所有长度为 2 n 2n 2n具有 n n n 个括号的括号序列我们定义一个函数 g e n e r a t e ( n ) generate(n) generate(n) 来返回所有可能的括号序列。那么在函数 generate ( n ) \textit{generate}(n) generate(n) 的过程中
我们需要枚举 a a a 从 0 0 0 开始一直到 n − 1 n - 1 n−1 并递归调用 g e n e r a t e ( a ) generate(a) generate(a) 计算 a a a 的所有可能性相应的 b b b 从 n − 1 n - 1 n−1 一直到 0 0 0 递归调用 g e n e r a t e ( b ) generate(b) generate(b) 即可计算 b b b 的所有可能性遍历 a a a 与 b b b 的所有可能性并拼接即可得到所有长度为 2 n 2n 2n 的括号序列。
为了节省计算时间我们在每次 g e n e r a t e ( i ) generate(i) generate(i) 函数返回之前把返回值存储起来下次再调用 g e n e r a t e ( i ) generate(i) generate(i) 时可以直接返回不需要再递归计算即记忆化搜索。
class Solution {
private:shared_ptrvectorstring cache[100] {nullptr}; // string[][]shared_ptrvectorstring generate(int n) {if (cache[n] ! nullptr) return cache[n];if (n 0) cache[0] shared_ptrvectorstring(new vectorstring{});else {auto result shared_ptrvectorstring(new vectorstring);for (int i 0; i ! n; i) {auto lefts generate(i);auto rights generate(n - i - 1);for (const string left : *lefts)for (const string right : *rights)result - push_back(( left ) right);}cache[n] result;}return cache[n];}
public:vectorstring generateParenthesis(int n) {return *generate(n);}
};动态规划解法如下
class Solution {
public:vectorstring generateParenthesis(int n) {if (n 0) return {};if (n 1) return { () };vectorvectorstring dp(n 1);dp[0] { };dp[1] { () };for (int parenthesisNum 2; parenthesisNum n; parenthesisNum) {for (int i 0; i parenthesisNum; i) {int j parenthesisNum - i - 1;for (string a : dp[i])for (string b : dp[j]) dp[parenthesisNum].push_back(( a ) b);}}return dp[n];}
};复杂度分析
时间复杂度 O ( 4 n n ) O(\dfrac{4^n}{\sqrt{n}}) O(n 4n) 该分析与 方法二 类似空间复杂度 O ( 4 n n ) O(\dfrac{4^n}{\sqrt{n}}) O(n 4n) 此方法除答案数组外中间过程中会存储与答案数组同样数量级的临时数组是我们所需要的空间复杂度。
