本文共 953 字,大约阅读时间需要 3 分钟。
这个问题让人想到火车进站的次序问题,解的数量可以用卡特兰数求出。
因此我想到其实括号的排列和栈混洗的各个情况是一一对应的。
现有1、2、3三个数字,栈混洗后有123,132,213,231,321五种情况,312是不合法的。
而观察可以发现123这种情况对应着“()()()”这种情况,而132则对应着“()(())”这种情况,因为左括号代表一次入栈,右括号代表一次出栈,同理213就是“(())()”等等。
因此,用递归方法解这个问题,n代表了栈中元素数量,当然栈是“虚拟的”,m代表未入栈的元素个数,每个元素只能入栈一次,也只能出栈一次,这样模拟出栈混洗的各种情况。
public ListgenerateParenthesis(int n) { List result = new LinkedList(); getAllResult(result,0,n,new StringBuilder()); return result; } public void getAllResult(List l,int n,int m,StringBuilder sb){ if(n==0 && m==0){ l.add(sb.toString()); return; } if(m<0||n<0) return; if(m>0){ StringBuilder sr = new StringBuilder(sb);//用一个新串传入下一层递归 getAllResult(l,n+1,m-1,sr.append('(')); } if(n>0){ StringBuilder sr = new StringBuilder(sb); getAllResult(l,n-1,m,sr.append(')')); } }
转载地址:http://ifdii.baihongyu.com/