一亩三分地论坛

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

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

[Leetcode] 同样的思路不同实现,请教为何超时

[复制链接] |试试Instant~ |关注本帖
wujingzhishui 发表于 2016-8-2 16:31:30 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 wujingzhishui 于 2016-8-2 16:51 编辑

在做combination sumIV(lc377) 时候, 我用了数组来记录以前计算过的次数, discuss 有人用了map来存,代码基本一样,但是我的超时了, 他的却很快跑完。 IDE 测试了下我的也跑了很久跑不完,请教一下原因,代码贴在下面了,谢谢各位解答:
这是我的实现,超时:
  1. public int combinationSum4(int[] nums, int target) {
  2.          
  3.          int[] count = new int[target + 1];
  4.          return combinationSumHelper(nums, target, count);
  5.     }
  6.   
  7.     private int combinationSumHelper(int[] candidates, int target, int[] count){
  8.           if(target == 0){
  9.             return 1;
  10.         }
  11.         if(target < 0)
  12.                 return 0;
  13.         if(count[target] != 0)
  14.                 return count[target];
  15.         int sum = 0;
  16.         for(int i = 0; i < candidates.length; i++){
  17.             sum += combinationSumHelper(candidates, target - candidates[i],count);
  18.         }
  19.         count[target] = sum;
  20.         return count[target];
  21.      }
复制代码
这是discuss的实现,很快跑完:
  1. Map<Integer, Integer> map = new HashMap<>();
  2.     public int combinationSum4(int[] nums, int target) {
  3.         int count = 0;
  4.         if (nums == null || nums.length ==0 || target < 0 ) return 0;
  5.         if ( target ==0 ) return 1;
  6.         if (map.containsKey(target)) return map.get(target);
  7.         for (int num: nums){
  8.             count += combinationSum4(nums, target-num);
  9.         }
  10.         map.put(target, count);
  11.         return count;
  12.     }
复制代码
mnmunknown 发表于 2016-8-2 21:15:28 | 显示全部楼层
本帖最后由 mnmunknown 于 2016-8-2 23:01 编辑

个人理解是,因为 int[] 的初始化值本来就是 0 ,但同时在你的代码中如果 target < 0 (当前 sum 超了),也会返回 0,对于 sum > target 的情况下并没有实现完全的 “记忆化搜索”,后面的计算中遇到 sum > target 的重复子问题不会立刻返回原来的结果,而是重算一遍,所以超时了。

我把你的代码粘贴到 leetcode 上,对于 int[] count 做了 Arrays.fill(count, -1) 然后 dfs 中以是否为 -1 为标准判断当前子问题是否计算过,就 AC 了~ 17个test case 用时 1ms
----

编辑纠正下,是相对于所有已经计算过但是解的个数 = 0 的子问题,当前代码都会重复计算,不单单是 sum > target 的情况
回复 支持 反对

使用道具 举报

 楼主| wujingzhishui 发表于 2016-8-3 07:54:43 | 显示全部楼层
mnmunknown 发表于 2016-8-2 21:15
个人理解是,因为 int[] 的初始化值本来就是 0 ,但同时在你的代码中如果 target < 0 (当前 sum 超了),也 ...

多谢解答哈, coin change 也是一样实现, 然后竟然过了所有test, 看来上一题test case 不够大
回复 支持 反对

使用道具 举报

 楼主| wujingzhishui 发表于 2016-8-3 08:55:26 | 显示全部楼层
mnmunknown 发表于 2016-8-2 21:15
个人理解是,因为 int[] 的初始化值本来就是 0 ,但同时在你的代码中如果 target < 0 (当前 sum 超了),也 ...

仔细看了下, 还是有个问题, 第二段代码用map也是一个思路赋值, 但是确可以啊。。
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-8-3 22:20:24 | 显示全部楼层
wujingzhishui 发表于 2016-8-3 08:55
仔细看了下, 还是有个问题, 第二段代码用map也是一个思路赋值, 但是确可以啊。。

map 不一样啊~ java 里新开一个 int[] array 默认里面填的都是 0 ,只靠某个位置上的值是不是 0 无法确定这个 sum 到底有没有计算过;但是 HashMap 新开之后不会默认你有这个 key,肯定是 put 进去的,containsKey 如果 返回 true 就说明这个子问题之前肯定计算过了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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