1

私は Cracking the Coding Interview の問題 9.6 ページ 110 の問題に取り組んでいます。

ここに問題があります:
すべての有効な (例えば、n 対の括弧の適切に開いた組み合わせと閉じた組み合わせ) を出力するアルゴリズムを実装してください。例
b(1) - "()"
b(2) - "(()), () ()"
b(3) - "((())), (()()), (())(), ()(()), ()()()"
を使用しようとしています著者が 107 ページで説明しているボトムアップ再帰アプローチ - 「要素が 1 つしかないリストのような単純なケースの問題を解決する方法を知ることから始め、要素が 2 つ、次に要素が 3 つの場合の問題を解決する方法を見つけます。要素など。ここで重要なのは、前のケースから別のケースのソリューションを構築する方法を考えることです」

ここに私がこれまでに持っているコードがあります

static void print(int n) {
    print(n, new HashSet<String>(), "", "");
}

static void print(int n, Set<String> combs, String start, String  end) {
    if(n == 0) {
        if(!combs.contains(start + end)) {
            System.out.print(start + end);
            combs.add(start + end);
        }
    } else {
        print(n-1, combs, "(" + start, end +")");
        System.out.print(", ");
        print(n-1, combs, start, end + "()");
        System.out.print(", ");
        print(n-1, combs, "()" + start, end);
    }
}

このコードを取得するために、最初のケースから 2 番目のケースまで作業しました。
b(2) = "(b(1)), b(1),b(1)" このコードは、最初の 2 つのケースで機能します。しかし、私は3番目のケースに本当に苦労しています。ケース 2 からケース 3 に移行する方法、つまりケース 2 を使用してケース 3 に移行する方法について、誰かがヒントを教えてくれますか? (())、()() から
((()))、(()())、(())()、()(())、()()() ? b(2) から b(3) ではうまくいかないので、b(1) から b(2) まで見たパターンを放棄しますか?

4

2 に答える 2

3

この再帰式を使用して、b(n) から b(n + 1) を生成できます。

  • (b(n - x))b(x) with 0 <= x <= n

したがって、 all を反復処理することで、すべての組み合わせを取得できますx。

コード：

public static ArrayList<String> cal(int num){

    if(num == 0){
        ArrayList<String> list = new ArrayList();
        list.add("");
        return list;
    }else{
        ArrayList<String>result = new ArrayList();
        for(int i = 0; i <= num - 1; i++){
            ArrayList<String> a = cal(i);
            ArrayList<String> b = cal(num - 1 - i);
            for(String x : a){
                for(String y : b){
                    result.add("(" + x + ")" + y);
                }
            }
        }
        return result;
    }
}

入力: 3 出力:()()(), ()(()), (())(), (()()), ((()))

入力: 4 出力: ()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(())), ((())()), ((()())), (((())))

于 2015-02-27T03:51:06.407 に答える
2

元の回答で犯した間違いを指摘してくれたKhanna111に感謝します。これは不完全で、文字列パターンを過小評価していました。その結果、それに応じて回答を更新しました。

Pham Trungが正しい再帰式で答えてくれたことに感謝することを検討してください。私の答えは基本的に彼と同じですが、小さなサブ問題からパターンを構築する方法がわずかに異なるだけです (私のアプローチで詳細を説明する方が簡単だと思うため)。

================================================== ======================

ソリューションの更新

ssize の有効なパターンの場合、次のいずれかのケースに正確nにs該当します。

  • ケース 1:小さいサイズの 2 つの有効なパターンに分割s できない
  • ケース 2:小さいサイズの 2 つの有効なパターンに分割s できる

ケース 1 の場合、sは の形式でなければなりません(_____)。ここ_____で、 は size の有効なパターンですn - 1。tしたがって、この場合、 sizeのすべての有効なパターンについて、とを接頭辞および接尾辞としてそれぞれ (つまり)連結することによりn - 1、単純にパターンを構築します。st()s = (t)

ケース 2 の場合、 に分割できますs。uvここで、uとvはどちらも小さいサイズの有効なパターンです。この場合、 と のすべての可能なパターンを考慮する必要があります。ここで、は size の有効なパターンでありu、は sizeの 任意の有効なパターンです。vui = 1, 2, ..., n - 1vn - i

Whenの場合n = 0、明らかに空の文字列のみが有効なパターンであるためdp(0) = { "" }、基本ケースとして を使用します。パフォーマンスを向上させるためのキャッシュを使用した完全な実装を以下に示します。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class BalancingBrackets {

    private static Map<Integer, Set<String>> dp = new HashMap<>();

    public static void main(String[] args) {
        Set<String> result = compute(4);

        boolean isFirst = true;
        for (String s : result) {
            if (isFirst) {
                isFirst = false;
                System.out.print(s);
            } else {
                System.out.print(", " + s);
            }
        }
    }

    private static Set<String> compute(Integer n) {
        // Return the cached result if available
        if (dp.containsKey(n)) {
            return dp.get(n);
        }

        Set<String> set = new HashSet<>();

        if (n == 0) {
            // This is the base case with n = 0, which consists only of the
            // empty string
            set.add("");
        } else if (n > 0) {
            // For generating patterns in case 1
            for (String s : compute(n - 1)) {
                set.add("(" + s + ")");
            }

            // For generating patterns in case 2
            for (int i = 1; i < n; i++) {
                Set<String> leftPatterns = compute(i);
                Set<String> rightPatterns = compute(n - i);

                for (String l : leftPatterns) {
                    for (String r : rightPatterns) {
                        set.add(l + r);
                    }
                }
            }
        } else {
            // Input cannot be negative
            throw new IllegalArgumentException("Input cannot be negative.");
        }

        // Cache the solution to save time for computing large size problems
        dp.put(n, set);

        return set;
    }

}
于 2015-02-27T03:46:28.863 に答える