所有题解方法请移步github-Leecode_summary
78. 子集
今天的收获很大，知道了我不适合做算法 :)
刚开始用最原始的方法，感觉会写的很复杂，然后看分类Backtracking，突然想到是不是可以用回溯，然后我折腾了快两个小时 :)，最后还是差一点，尽管很绝望，能学到的东西还是蛮多的...
我最难理解的是回溯算法，所以还是在这里详细的解释一下。其中回溯算法可以以 深度优先遍历 和 宽度优先遍历为基础，详情见右下图(都是神仙方法啊)：
看了很久，跟树结合很巧妙，在搜索过程可根据约束条件剪枝（避免不必要的搜素）
回溯算法（深度优先遍历）
|
想象成一棵树，类似树的遍历
|
|---|
90.子集II
既然题目要求不能有重复的子集，就要从两个方面着手：
1. 找出所有子集->筛选
2. 找子集的过程中主动避免重复->剪枝
我就只会做最笨的方法咯，但肯定是有比较trick的方法...（多看多想，总结一下），比如统计频数法，又比如数组排序再组合
今日份的Tips: list的相等问题：
>>> list1 = [1, 2, 3, 4] list2 = [1, 2, 3, 4] list3 = [4, 3, 2, 1]
>>> list1 == list2 # 判断严格相等 (元素及顺序相等)
True
>>> list1 == list3
False
>>> sorted(list1) == sorted(list3) # 只要求元素相等
>>> list1.sort() == list3.sort() #sorted()生成新的数组/list.sort()对自身改变
77. 组合
这个题目就是子集的子集？？，还是“换汤不换药”，遍历会了什么都好做，只不过是往上加点条件罢了..不过多撰述了..
39.组合总数
用最笨的方法 超最长的时 ><
刷题刷到现在，看了题解回溯、剪枝，终于有点感觉，在书里面见识的算法是实实在在可以用来解决问题的~ 做题的时候在想，怎么能在append的同时鉴别是否重复呢，但我真的想不到...好菜啊...题解还有动态规划解决方案可以思考一下
题解两种遍历：
1 全部遍历(包含重复数组)，逐个判断是否符合要求
2 从根源上避免重复数组
总算是发现了我能理解且复现的方法: 树与剪枝 参考代码
另外动态规划方法也蛮不错的，要领会其思想
组合总数II
思考：1.遍历不包括自身 2.怎么剪枝
子集II和组合II的关键剪枝步骤：if j>i and nums[j] == nums[j-1]: continue,真的好使
全排列I&II
我发现带有重复元素的排列组合问题比较简单的做法都是先排序，在回溯过程中主动剪枝 √。
网友评论