g**********y
发帖数: 14569 | 1 前天在版上看到打印所有矩阵结合次序(Catalan Numbers)的讨论，最后给出的程序比
较长，我想了一下，既然都是Catalan Numbers, 那么生成Dyck word list的程序应该
可以变形成矩阵结合次序。
CareerCup给出的Dyck word list程序很简洁，我就试着映射了一下：
先推‘A’进栈
对应Dyck word (比如XXXYYY), 遇到X, push nextChar 进栈；
遇到Y, 如果pop()出两个，结合后推进栈
==============================================================
以上是写完后在路上刚悟到的，这个映射应该还算简单。如果不用映射，谁能给个更简洁的解法？
附Java code ==>
public void generate(int count) {
print(count, count, new char[2*count], 0);
}
public void print(int l, int r, char[] str, int count) {
if (l==0 && r==0) print(str);
if (l>0) {
str[count] = 'X';
print(l-1, r, str, count+1);
}
if (r>l) {
str[count] = 'Y';
print(l, r-1, str, count+1);
}
}
private void print(char[] str) {
Stack s = new Stack();
int k = 0;
s.push(getChar(k++));
for (int i=0; i
if (str[i] == 'X') {
s.push(getChar(k++));
}
else {
String t = s.pop();
s.push("(" + s.pop() + t + ")");
}
}
System.out.println(s.pop());
}
private String getChar(int k) {
char c = (char) ('A' + k);
return c + "";
} |
|
