MEE-RICE短篇选课,毕业,就业介绍(个人观点)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 5734|回复: 14
收起左侧

[算法题] 以Generate Parentheses为例,backtrack的题到底该怎么去思考?

[复制链接] |试试Instant~
我的人缘0
coldfire8 发表于 2016-2-20 19:44:27 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  83% (122)
 
 
16% (24)  踩

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

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

x
本帖最后由 coldfire8 于 2016-2-20 19:57 编辑

比如Generate Parentheses这道经典的backtrack,代码如下:
  1. public static List<String> generateParenthesis2(int n) {
  2.         List<String> res = new ArrayList<>();
  3.         backtrack("", res, n, n);
  4.         return res;
  5.     }

  6.     public static void backtrack(String sublist, List<String> res, int left, int right) {
  7.         if (left == 0 && right == 0) {
  8.             res.add(sublist);
  9.             return;
  10.         }
  11.         if (left > right)
  12.             return;
  13.         if (left > 0)
  14.             backtrack(sublist + "(", res, left - 1, right);
  15.         if (right > 0)
  16.             backtrack(sublist + ")", res, left, right - 1);
  17.     }
复制代码
实在是不知道这是怎么写出来的,为什么要这么写。。自己跟了一下debug才知道是怎么回事。。感觉和其他比较直观的backtrack不一样。。有童鞋能帮忙理一下这种backtrack题的诀窍和思路么?谢谢!!

上一篇:一遇到Tree的问题就抓瞎啊,求问有没有什么理解的窍门……
下一篇:stock maximize 不能 pass tests, 求正确 java code

本帖被以下淘专辑推荐:

我的人缘0
stellari 发表于 2016-2-21 12:39:12 | 显示全部楼层
本楼: 【顶】   100% (13)
 
 
0% (0)   【踩】
全局: 顶  98% (389)
 
 
1% (4)  踩
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行(因为违反了某些限定条件),就返回;如果某种选择试到最后发现是正确解,就将其加入解集

所以你思考递归题时,只要明确三点就行:选择 (Options),限制 (Restraints),结束条件 (Termination)。即“ORT原则”(这个是我自己编的)

对于这道题,在任何时刻,你都有两种选择:
1. 加左括号
2. 加右括号

同时有以下限制:
1. 如果左括号已经用完了,则不能再加左括号了。
2. 如果已经出现的右括号和左括号一样多,则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。

结束条件是:
左右括号都已经用完

结束后的正确性:
左右括号用完以后,一定是正确解。因为1. 左右括号一样多,2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集(有时也可能出现结束以后不一定是正确解的情况,这时要多一步判断)。

递归函数传入参数:
限制和结束条件中有“用完”和“一样多”字样,因此你需要知道左右括号的数目
当然你还需要知道当前局面sublist解集res

因此,把上面的思路拼起来就是代码:

  1. if (左右括号都已用完) {
  2.   加入解集,返回
  3. }
  4. //否则开始试各种选择
  5. if (还有左括号可以用) {
  6.   加一个左括号,继续递归
  7. }
  8. if (右括号小于左括号) {
  9.   加一个右括号,继续递归
  10. }
复制代码
你帖的那段代码逻辑中加了一条限制:“3. 是否还有右括号剩余。如有才加右括号”。这是合理的。不过对于这道题,如果满足限制1、2时,3一定自动满足,所以可以不判断3。

这题其实是最好的backtracking初学练习之一,因为ORT三者都非常简单明显。你不妨按上述思路再梳理一遍,还有问题的话再说。

评分

参与人数 12大米 +61 收起 理由
yangchaoyue888 + 3 很有用的信息!
FightOn + 10 给你点个赞!
MrRD + 1 给你点个赞!
熊猫杀很大缺积分 + 5 很有用的信息!
CinL + 5 回答的很好!
富民文 + 3 感谢分享!
kamibear + 3 厉害
liqingfd + 5 感谢分享!
阿童木 + 10 你的回答每次都能解决我好多想不通的问题!.
OO0OO + 3 很有用的信息!
lefttree + 3 感谢分享!
jigsaw_Becky + 10 感谢分享!

查看全部评分

回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
FightForTomo 发表于 2017-7-31 11:48:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  52% (764)
 
 
47% (694)  踩
brn 发表于 2017-7-31 11:10
多写写和tree有关的题?

好的。谢谢建议。
有没有某个书的递归章节讲的比较详细。一步一步的。
例题是medium难度的。
回复

使用道具 举报

我的人缘0
xiaozhuxiaozhu 发表于 2016-2-21 18:42:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  73% (970)
 
 
26% (344)  踩
解题思路。。。。多做
回复

使用道具 举报

我的人缘0
jigsaw_Becky 发表于 2016-2-20 19:52:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (658)
 
 
6% (43)  踩
我也觉得backtrack很容易搞晕!看高人怎么解答的!
回复

使用道具 举报

我的人缘0
hongyuheng 发表于 2016-2-20 22:18:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
其实我觉得正着看更容易一些,就是使劲先往左边塞,左边塞满了就往右边塞。然后backtrack,删一个左边的,再重复上述策略。
class Solution {
public:
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    vector<string> generateParenthesis(int n) {
        // Write your code here
        if(n == 0)
            return {};

        vector<string> res;
        string line;
        dfs(line, n, 0, 0, res);
        return res;
    }

    void dfs(string line, int n, int left, int right, vector<string>& res){
        if(left == n && right == n){
            res.push_back(line);
            return;
        }

        if(left < n){
            line.push_back('(');
            dfs(line, n, left+1, right, res);
            line.pop_back();
        }

        if(right < left){
            line.push_back(')');
            dfs(line, n, left, right+1, res);
            line.pop_back();
        }

    }
};

回复

使用道具 举报

我的人缘0
jigsaw_Becky 发表于 2016-2-21 12:48:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (658)
 
 
6% (43)  踩
stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

thanks~每次你的回答都这么清晰!
回复

使用道具 举报

我的人缘0
 楼主| coldfire8 发表于 2016-2-21 18:24:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (122)
 
 
16% (24)  踩
stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

感谢您的回复,真是超级清晰~顺便问一下,『有时也可能出现结束以后不一定是正确解的情况,这时要多一步判断』您说的这种情况我好像还没有遇到过,请问有什么例子可以借鉴么?多谢!
回复

使用道具 举报

我的人缘0
cheese_harry 发表于 2017-6-8 23:29:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (158)
 
 
7% (12)  踩
stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

收藏这个答案》。

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

我的人缘0
FightForTomo 发表于 2017-6-9 02:35:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  52% (764)
 
 
47% (694)  踩
xiaozhuxiaozhu 发表于 2016-2-21 18:42
解题思路。。。。多做

递归真是理解无能。。
回溯法我就打算把那10来到排列组合 全背下来。
回复

使用道具 举报

我的人缘0
carriejx 发表于 2017-6-9 06:41:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
FightForTomo 发表于 2017-6-9 02:35
递归真是理解无能。。
回溯法我就打算把那10来到排列组合 全背下来。

你说的排列组合都是哪些?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|联系我们&一亩三分地论坛声明

GMT+8, 2018-11-21 14:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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