我尝试做经典问题来实现一种算法来打印 n 对括号的所有有效组合。
我找到了这个程序(效果很好):
public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
String s = String.copyValueOf(str);
list.add(s);
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[count] = '(';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = ')';
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}
public static ArrayList<String> generateParens(int count) {
char[] str = new char[count*2];
ArrayList<String> list = new ArrayList<String>();
addParen(list, count, count, str, 0);
return list;
}
据我了解,我们的想法是尽可能添加左括号。对于右括号,只有当剩余的右括号数量大于左括号时,我们才会添加它。如果我们使用了所有左括号和右括号,我们会将新组合添加到结果中。我们可以确定不会有任何重复构造的字符串。
对我来说,这种递归就像我们使用树时,例如我们进行前序遍历:我们每次都可能去左节点,如果不行,我们就向右走,然后我们尝试向左走就在这一步之后。如果不能,我们“返回”并向右走,然后重复遍历。在我看来,这里的想法完全相同。
所以,我天真地认为时间复杂度会是 O(log(n))、O(n.log(n)) 或类似对数的东西。但是,当我尝试搜索时,我发现了一个叫做“加泰罗尼亚语数量”的东西,我们可以用它来计算括号组合的数量......(https://anonymouscoders.wordpress.com/2015/07/20/its-all-about-catalan/)
您认为时间复杂度是多少?我们可以在这里应用主定理吗?