求助 cc150 8.5， 答案看不懂~

Implement an algorithm to print all valid (e g , properly opened and closed) combi- nations of n-pairs of parentheses

public static void printPar(int l, int r, char[] str, int count) {
                if (l < 0 || r < l) return; // invalid state
                if (l == 0 && r == 0) {
                        System.out.println(str); // found one, so print it
                        } else {
                                if (l > 0) { // try a left paren, if there are some available
                                        str[count] = '(';
                                        printPar(l - 1, r, str, count + 1);
                                }
                                if (r > l) { // try a right paren, if there’s a matching left
                                        str[count] = ')';
                                printPar(l, r - 1, str, count + 1);
                                }
                }
        }
       
       
        public static void printPar(int count) {
                char[] str = new char[count*2];
                printPar(count, count, str, 0);
        }

调用printPar的时候只declare了一个char[]~这样是不是只能又一个string吗？为什么能打印出别的string呢？我尝试着画stack的图~画到了如下图我就画不出来了~
printPar(2,2,"",0)
        str="("
        printPar(1,2,"(",1)
                str="(("
                printPar(0,2,"(("2)
                        str="(()"
                        printPar(0,1,"(()",3)
                                str="(())"
                                printPar(0,0,"(())",4)
                                        print(str)
                        return
                return
        printPar(1,1"((",2)
                str 。。。。。。（写不出了）

希望大师们指点~

首先, 其实我没明白你问什么, 这题是典型的dfs思想题, 在这里的str char组 是一个"动态数组", 他只是存储一个情况下(你stack中的一个frame)的当前char, 你可以理解成一个temp. 至于为什么打印出别的strnig, 因为每次str中的char是不一样的? 不知道你是不是问这个...你看你的stack的frame, 每次都update的. 所以打印出不一样的string

readman 发表于 2014-6-15 15:21
首先, 其实我没明白你问什么, 这题是典型的dfs思想题, 在这里的str char组 是一个"动态数组", 他只是存储一 ...

哦哦~不好意思哈~本人转cs的~刚看完cs61b~想尝试着做做CC150~做了前3章~发现用到了好多recursive的方法~所以想先做做第8章~加强一下~

你说的dfs是depth first search的意思是吧~？

sqzhang17 发表于 2014-6-15 16:07
哦哦~不好意思哈~本人转cs的~刚看完cs61b~想尝试着做做CC150~做了前3章~发现用到了好多recursive的方法~ ...

嗯. dfs是一个思想, 也是一个通用模版
类似于:
public void dfs (数组,tmp, count)
for(int i = 0 ; i < 数组长度; i++) {
if(tmp or 数组 满足什么条件) {
   做一些事情
}
dfs(数组, tmp, cont++) // 下一个循环的变量
}

readman 发表于 2014-6-15 16:23
嗯. dfs是一个思想, 也是一个通用模版
类似于:
public void dfs (数组,tmp, count)

哦哦~呵呵~好的~cs61b里面有讲过dfs~等我再回顾一下~

我记得dfs和bfs是运用在graph题目下的~怎么这种题目也可以用？

不好意思~麻烦你解答了我这个小白的一些百亩的问题~惭愧啊~

sqzhang17 发表于 2014-6-16 03:20
哦哦~呵呵~好的~cs61b里面有讲过dfs~等我再回顾一下~

我记得dfs和bfs是运用在graph题目下的~怎么这种 ...

dfs是一种递归的思路..二叉树可用, 数组可用, 排列可用..很多地方都可以

readman 发表于 2014-6-16 10:46
dfs是一种递归的思路..二叉树可用, 数组可用, 排列可用..很多地方都可以

感觉递归好像运用的很多~但是感觉好难啊~哎~没有抓到精髓啊~慢慢磨练磨练吧~

sqzhang17 发表于 2014-6-16 13:26
感觉递归好像运用的很多~但是感觉好难啊~哎~没有抓到精髓啊~慢慢磨练磨练吧~

递归的精髓在于, 你看到一个迭代, 就能写出递归.所以平时多写就好了....

readman 发表于 2014-6-16 13:35
递归的精髓在于, 你看到一个迭代, 就能写出递归.所以平时多写就好了....

嗯~好的~谢谢了~万分感谢~

readman 发表于 2014-6-16 13:35
递归的精髓在于, 你看到一个迭代, 就能写出递归.所以平时多写就好了....

嗯~好的~谢谢了~万分感谢~