博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
39 Combination Sum
阅读量:7113 次
发布时间:2019-06-28

本文共 1657 字,大约阅读时间需要 5 分钟。

2017/07/23 Update

今天做发现这种for+递归并不是我想象的n*n模型,第二个n是堆栈深度,完全取决于你什么时候return,如果不return就会stackOverFlow。N queens是N*N因为人为制定了终止条件是n。


这题第一次做还是去年了。。Intellij里显示着:Created by DrunkPiano on 2016/12/30. 那时候还没有写简书,这里补上。 转眼已经4个月过去了。第一次写这题时候的心情郁闷死了,根本不知道dfs干嘛,恢复现场干嘛。。练习真是有用的,我现在有种感觉就是无论做什么事情只有你在上面花了工夫了才会出点成果,比如弹吉他,再没有天分的人 天天练的话也能练好一首曲子。但是还有些例外,就是同样是投入练习,有的人会弹得好,有的人会弹得差;打dota也一样,有的人打了几年还是菜鸡,这就不仅仅是练习了,如果除去天分的话,影响成果的就是练习的方法,比如是否善于总结,会不会对某个点进行针对性训练等等。

再写这道题的时候思路很清楚,用全排列(permuattions)的那种一层层递归的套路。但是漏掉了一个问题,就是忘记让for的初始值再进入下一层的时候不能从自己之前的数开始,否则就duplicated了,例如这样一个case:

Input: [2,3,6,7] 7 Output: [[2,2,3],[2,3,2],[3,2,2],[7]] Expected: [[2,2,3],[7]]

这题跟N皇后其实有相似之处,最终都会形成一个n * n的matrix的遍历形式,很清晰的DFS,为什么要让i = start也很清楚:

最后贴下代码,注意 if(i>0 && candidates[i] == candidates[i-1]) continue;这句可以把提高一些速度。

List
> result = new ArrayList<>(); public List
> combinationSum(int[] candidates, int target) { if (candidates == null || candidates.length == 0) return result; dfs(target, new ArrayList
(), candidates , 0); return result; } private void dfs(int target, List
item, int[] candidates, int start) { if (target < 0) return; if (target == 0) { result.add(new ArrayList<>(item)); return; } for (int i = start; i < candidates.length; i++) { // //加上下面这句对结果没有影响,但会减少很多次循环,因为同一个数字可以复用(每次从i开始),所以重复数字就没有意义了 if(i>0 && candidates[i] == candidates[i-1]) continue; item.add(candidates[i]); dfs(target - candidates[i], item, candidates, i); item.remove(item.size() - 1); } }复制代码

对于, 除了能想到下一层从start + 1 开始之外,还是有几点需要注意的,具体可以去那篇看看。

转载于:https://juejin.im/post/5a31314cf265da431b6d34d4

你可能感兴趣的文章
《C#高级编程》笔记系列--点滴记录(持续更新中……)
查看>>
采用泳道图工具跟踪项目进度或者问题解决进度
查看>>
sql server 2008学习1–系统数据库
查看>>
找零钱的两种方法
查看>>
DM642图像处理程序的主要结构
查看>>
从微软的DBML文件中我们能学到什么(它告诉了我们什么是微软的重中之重)~三 分部类是否破坏了单一职责...
查看>>
redis的主从配置 扩容
查看>>
HDU1004 Let the Balloon Rise
查看>>
jquery 校验中国身份证号码
查看>>
PicPopupWindow的使用
查看>>
以最简单的登录为例,诠释JS面向对象的简单实例
查看>>
value toDF is not a member of org.apache.spark.rdd.RDD
查看>>
活动安排问题--贪心算法
查看>>
ZOJ1070 Bode Plot
查看>>
[LeetCode] Graph Valid Tree
查看>>
web程序员标准环境之DreamWeaver【推荐】
查看>>
springMvc源码学习之:利用springMVC随时随地获取HttpServletRequest等对象
查看>>
无限分页
查看>>
iOS - UIColor
查看>>
Java最最常用的100个类排序(非官方)
查看>>