22.Generate Partheses

2898 ワード

LeetCode データ構造面接試験数学深さ検索

22.Generate Partheses My Submissions
Question
Total Acceepted: 74274
Total Submissions: 211279
Difficulty: Medium
Given n pairs of parentheses、write a function to generate all cobinations of well-formed parentheses.
For example,given n = 3,a solution set is:"((()))", "(()())", "(())()", "()(())", "()()()"Subscribe to see which companies asked this question
ハイドTags

Backtrocing String
Hide Simiar Probles

(M)Letter Cobinations of a Phone Number (E)Valid Partheses
分析:
1、断言してください.いつも左のかっこを押してから右のかっこに入れます.
2,断言してください.押し込まれていない左括弧があれば、押し込みます.左括弧の数は必ず既存の左括弧を残してはいけません.
3,推測:すべての判例を生成するために遡及法を考慮することができる.
他の人のアルゴリズム:

//    ：
//  leetcode    ，       ！
//     ：
//           ，             。
//                  
class Solution {
public:
        
        vector<string> generateParenthesis(int n) {
            GenerateDFS("", n, n);
            return result;
        }
        
        //       curstr      left     right
        void GenerateDFS(string curstr, int left, int right)//              ，         
        {
            if(left == 0 && right == 0)
            {
                result.push_back(curstr);
                return;
            }
            if(left > 0)
                GenerateDFS(curstr + "(", left - 1, right);
            if(right>left && right>0)//                  
                GenerateDFS(curstr + ")", left, right - 1);
        }
private:
        vector<string> result;
};

痛定思痛:
1、括弧の生成規則が分かりませんでした.深さの検索トレース法とは見えませんでした.
2,締め切り条件ははっきりしていませんでした.
3、遡法思想を新たに悟る:
1)、回溯法概念
      追跡アルゴリズムは、実際にはエニュメレーションのような検索試行プロセスで、主に検索試行の過程で問題の解を探しています.解決条件が満たされていないことがわかったら、「トレース」に戻り、別の経路を試してみます.
   回顧法は優れた検索法を選んで、優れた条件を選んで前に探して目標を達成します.しかし、あるステップを探索した時、もとは優れていなかったり、目標に達していなかったりしたことを発見したら、もう一度選択し直します.このような行き止まりがないなら、戻って行く技術はトレース法です.トレース条件を満たすある状態の点を「トレースポイント」といいます.
     多くの複雑さ、規模の大きい問題は遡及法を使っています.「共通解問題方法」という美称があります.
2)、基本思想
   問題を含む全ての解の空間ツリーにおいて、深度優先検索の戦略に従って、ルートノードから空間ツリーの深さ探索を行う.ある結点を探るときは、まずその結点に問題の解が含まれているかどうかを判断し、もし含まれているなら、その結点から引き続き探索していきます.もしこの結点に問題の解が含まれていないならば、層ごとにその祖先の結点に遡ります.(実は逆トレースとは、トレース図の深さ優先検索アルゴリズムである)
       遡及法で問題のすべての解を求める場合は、根に遡り、根に結ぶすべての実行可能な子樹はすでに検索されて終わります.
       遡及法を使っていずれかの解を求める場合、問題の一つの解を検索すれば終了します.
3)トレース法で問題を解く一般的な手順:
    (1)与えられた問題に対して、問題の解決空間を確定する:
            まず問題の解空間を明確に定義し、問題の解空間は少なくとも問題の一つ(最適)解を含むべきである.
    (2)結点の拡張検索ルールを決定する
    (3)解空間は深さ優先で検索され、検索中に剪定関数で無効な検索を避ける.
連動第257題
【1】 257.Binary Tree Paths、http://blog.csdn.net/ebowtang/article/details/50493936
注:このブログはEbowTangのオリジナルです.その後も引き続き本文を更新します.転載する場合は、必ず本条情報をコピーしてください.
原文の住所:http://blog.csdn.net/ebowtang/article/details/50557414
作者のブログ:http://blog.csdn.net/ebowtang

データ構造とアルゴリズム分析学習ノート---第三章(チェーン)