一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 906|回复: 8
收起左侧

[CareerCup] 求助 cc150 8.5, 答案看不懂~

[复制链接] |试试Instant~ |关注本帖
sqzhang17 发表于 2014-6-15 14:07:16 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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 。。。。。。(写不出了)

希望大师们指点~
readman 发表于 2014-6-15 15:21:11 | 显示全部楼层
首先, 其实我没明白你问什么, 这题是典型的dfs思想题, 在这里的str char组 是一个"动态数组", 他只是存储一个情况下(你stack中的一个frame)的当前char, 你可以理解成一个temp. 至于为什么打印出别的strnig, 因为每次str中的char是不一样的? 不知道你是不是问这个...你看你的stack的frame, 每次都update的. 所以打印出不一样的string
回复 支持 反对

使用道具 举报

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

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

你说的dfs是depth first search的意思是吧~?
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-15 16:23:01 | 显示全部楼层
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++) // 下一个循环的变量
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| sqzhang17 发表于 2014-6-16 03:20:10 | 显示全部楼层
readman 发表于 2014-6-15 16:23
嗯. dfs是一个思想, 也是一个通用模版
类似于:
public void dfs (数组,tmp, count)

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

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

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

使用道具 举报

readman 发表于 2014-6-16 10:46:35 | 显示全部楼层
sqzhang17 发表于 2014-6-16 03:20
哦哦~呵呵~好的~cs61b里面有讲过dfs~等我再回顾一下~

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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| sqzhang17 发表于 2014-6-16 13:26:10 | 显示全部楼层
readman 发表于 2014-6-16 10:46
dfs是一种递归的思路..二叉树可用, 数组可用, 排列可用..很多地方都可以

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

使用道具 举报

readman 发表于 2014-6-16 13:35:32 | 显示全部楼层
sqzhang17 发表于 2014-6-16 13:26
感觉递归好像运用的很多~但是感觉好难啊~哎~没有抓到精髓啊~慢慢磨练磨练吧~

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| sqzhang17 发表于 2014-6-16 14:07:42 | 显示全部楼层
readman 发表于 2014-6-16 13:35
递归的精髓在于, 你看到一个迭代, 就能写出递归.所以平时多写就好了....

嗯~好的~谢谢了~万分感谢~
回复 支持 反对

使用道具 举报

 楼主| sqzhang17 发表于 2014-6-16 14:07:51 | 显示全部楼层
readman 发表于 2014-6-16 13:35
递归的精髓在于, 你看到一个迭代, 就能写出递归.所以平时多写就好了....

嗯~好的~谢谢了~万分感谢~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表