一亩三分地论坛

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

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

[算法题] Letter Combinations of a Phone Number按键组合-细节问题

[复制链接] |试试Instant~ |关注本帖
macctown 发表于 2015-10-15 09:27:31 | 显示全部楼层 |阅读模式

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

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

x
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
中等难度题目,看到组合就想到dfs,然后实现。实现之后就一直溢出。后来发现是一个非常非常细节的问题,但是有点不明白。

代码是这样的:
  1. public static List<String> letterCombinations(String digits) {
  2.         List<String> res = new ArrayList<String>();
  3.         if(digits == null || digits.length()==0){
  4.                 return res;
  5.         }
  6.         StringBuilder tmp = new StringBuilder();
  7.         HashMap<Integer, String> map = new HashMap<Integer, String>();
  8.         map.put(1, "");
  9.         map.put(2, "abc");
  10.         map.put(3, "def");
  11.         map.put(4, "ghi");
  12.         map.put(5, "jkl");
  13.         map.put(6, "mno");
  14.         map.put(7, "pqrs");
  15.         map.put(8, "tuv");
  16.         map.put(9, "wxyz");
  17.         map.put(0, " ");
  18.         dfs(res, map, tmp, 0, digits);
  19.         
  20.         return res;
  21.     }

  22.         private static void dfs(List<String> res, HashMap<Integer, String> map, StringBuilder tmp,
  23.                         int num, String digits) {
  24.                 // TODO Auto-generated method stub
  25.                 if(num == digits.length()){
  26.                         res.add(tmp.toString());
  27.                         return;
  28.                 }
  29.                 Integer key = Integer.valueOf(String.valueOf(digits.charAt(num)));
  30.                 String letters = map.get(key);
  31.                
  32.                 for(int i=0;i<letters.length();i++){
  33.                         tmp.append(letters.charAt(i));
  34.                         dfs(res, map, tmp, num+1, digits);
  35.                         tmp.deleteCharAt(tmp.length()-1);
  36.                 }
  37.         }
复制代码
递归调用部分的第四个参数,也就是深度,或者说输入按键的第N个,这里要一直增加,一开始我用了num++,这个溢出,我还了解,后来我用了++num,还有在之前,先把num++,后面dfs里直接用增加后的num,这两种就会蹦出outOfIndex,发生在上面取key得那行,为啥会out呢,我上面有判断呀。

求解~求交流!~
epochou 发表于 2015-10-15 10:02:05 | 显示全部楼层
num++,  ++num  都会使num本身值改变,所以递归return回来后,for loop里的num值会不断增加,所以out of index.
回复 支持 反对

使用道具 举报

 楼主| macctown 发表于 2015-10-15 11:50:03 | 显示全部楼层
epochou 发表于 2015-10-15 10:02
num++,  ++num  都会使num本身值改变,所以递归return回来后,for loop里的num值会不断增加,所以out of in ...

了解了!。。num+1就只是传一个值,而不是改变num。。。懂了~谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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