1

我正在研究破解编码面试中的一个问题，问题 9.6 第 110 页。

这就是问题所在：
实现一个算法来打印所有有效的（例如，正确打开和关闭的 n 对括号组合。示例
b(1) - "()"
b(2) - "(()), () ()"
b(3) - "((()))、(()())、(())()、()(())、()()()"
我正在尝试使用作者在第 107 页讨论的自下而上递归方法 - “我们首先知道如何解决一个简单案例的问题，比如只有一个元素的列表，然后弄清楚如何解决两个元素的问题，然后是三个元素元素等等。这里的关键是考虑如何从前一个案例中构建一个案例的解决方案“

这是我到目前为止的代码

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);
    }
}

为了得到这个代码，我从第一种情况到第二种情况。我看到
b(2) = "(b(1)), b(1),b(1)" 这段代码确实适用于前两种情况。不过，我真的在为第三种情况苦苦挣扎。有人可以给我一个提示（不是全部答案，可以翻到书的后面），关于如何从案例 2 到案例 3，或者换句话说，使用案例 2 到案例 3？就像你会如何从 (()), ()() 到
((())), (()()), (())(), ()(()), ()()() ? 你会放弃从 b(1) 到 b(2) 看到的模式，因为它对 b(2) 到 b(3) 不起作用吗？

4

2 回答 2

3

我们可以使用这个递归公式从 b(n) 到 b(n + 1) 生成：

  • (b(n - x))b(x) 与 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的答案归功于他。我的回答与他的基本相同，只是我从较小的子问题中构建模式的方式略有不同（因为我发现在我的方法中解释细节更容易）。

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

更新解决方案

对于任何有效s的 size模式n，s恰好属于以下情况之一：

  • 情况1：s 不能分成两个更小尺寸的有效模式
  • 案例2：s 可以划分为两个更小尺寸的有效模式

对于第 1 种情况，s必须是 形式(_____)，其中_____是 size 的有效模式n - 1。因此，在这种情况下，对于每个有效t的 size模式，我们只需通过将and分别作为前缀和后缀连接来n - 1构造一个模式（即）。st()s = (t)

对于案例 2，我们可以划分s为uv、 whereu和v都是较小尺寸的有效模式。在这种情况下，我们必须考虑 and 的所有可能模式u，v其中u可以是任何有效的大小模式i = 1, 2, ..., n - 1，而v 可以是任何有效的大小模式n - i。

当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 回答