并没有看起来那么简单leetcode Generate Parentheses-白红宇

并没有看起来那么简单leetcode Generate Parentheses

阅读量：5813 次

发布时间：2019-06-18

本文共 2264 字，大约阅读时间需要 7 分钟。

它给出了这个问题的探讨。

超时的代码：

这个当n等于7时，已经要很长时间出结果了。这个算法的复杂度是O(n^2)。

#include
     
      #include
      
       #include
       
        #include
        using namespace std;bool isValid(string s) {    map
         
           smap;    smap.insert(make_pair('(', ')'));    stack
          
            ss; int i = 0; int L = s.length(); while (i
           
             F(int n, string s, vector
            
              &result, vector
             
               a){ if (n < 1) { return result; } if (n == 1) { for (int i = 0; i < a.size(); i++) { string t = s; t += a[i]; if (isValid(t)) result.push_back(t); } } else { for (int i = 0; i < a.size(); i++) { string t = s; t += a[i]; F(n - 1, t, result, a); } } return result;}vector
              
                generateParenthesis(int n) { vector
               
                 a = { '(',')'}; vector
                
                  result; string s = ""; return F(n*2, s, result, a);}int main(){ vector
                 
                   result = generateParenthesis(7); for (int i = 0; i < result.size(); i++) { cout << result[i].c_str() << endl; } return 0;}

上面的解法显然代价是O(2^n)这个肯定超时。不知道自己当时写的时候就没有分析一下，加上今天写hiho coder上的那一题，由此可见对内存的开销和时间的代价还是不够敏感！

这个题分析一下还是简单的，首先就两中符号，不是这个就是另一个，所以只要满足当前左括号的数目大于右括号就可以加在字符串后添加右括号，如果左括号没有放完就是左括号的数目还没有到n，那么就可以继续放左括号。但是但是但是但是但是……哎，我竟然又犯了一个错误。

递归是递归，循环是循环不要混。 递归时一定要保证一次循环加一个。

我刚开始想的是当左括号大于右括号是可以这样写

if (left > right){

unguarded_generate(n, left + 1, right, result, s + ')');

unguarded_generate(n, left, right + 1, result, s + ')');

}

too young too simple啊！

AC代码：

1 #include
     
       2 #include
      
        3  4 using namespace std; 5  6 void unguarded_generate(int n, int left, int right, vector
       
         &result, string s){ 7     if (left == n&&right == n){ 8         result.push_back(s); 9     }10     else{11         if (left != n){12             unguarded_generate(n, left + 1, right, result, s + '(');13         }14         if (left > right&&right != n){15             unguarded_generate(n, left, right + 1,result, s + ')');16         }17     }18 }19 20 vector
        
          generateParenthesis(int n)21 {22     vector
         
           ret;23     unguarded_generate(n, 0, 0, ret, "");24     return ret;25 }26 27 28 int main(){29     vector
          
            result = generateParenthesis(3);30 for (int i = 0; i < result.size(); i++){31 cout << result[i].c_str() << endl;32 }33 }

转载于:https://www.cnblogs.com/chaiwentao/p/4428062.html

你可能感兴趣的文章