江苏龙网

  1. 主页 > 生活百科 > >

回溯算法的题目，这样做，秒杀( 二 )

回溯算法

ok，我们去运行一下，看看如何 。

回溯算法的题目，这样做，秒杀

文章插图
 
他说我超出时间限制，说明算法是有问题的，我们再看一下上面我们写的代码，我们发现，其实我们每次遍历数组的时候都是从0开始遍历的，导致很多重复的元素遍历了，也就是我们得start变量并没有用到，最后，我们把遍历的时候不每次从0开始，而是从当前的start开始遍历，选过的元素我们排除，看一下结果 。
    List<List<Integer>> list = new ArrayList<>();    public List<List<Integer>> subsets(int[] nums) {        if(nums.length == 0){            return null;        }        List<Integer> temp = new ArrayList<>();        backTrace(0, nums, temp);        return list;    }    public void backTrace(int start, int[] nums, List<Integer> temp){        list.add(new ArrayList<>(temp));        //从start开始遍历，避免重复        for(int j = start; j < nums.length; j++){            temp.add(nums[j]);            backTrace(j+1,nums,temp);            temp.remove(temp.size()-1);        }    }发现完美通过，good job！！
回溯算法的题目，这样做，秒杀

文章插图
 
另外，我们要注意一个点就是：list.add(new ArrayList<>(temp));不要写成list.add(temp);，否则，输出的结果就是空集，你思考一下应该就知道为什么了 。
通过，这个题目，其实，我们就把回溯算法的一个大致的框架可以整理出来了，以后做其他题目，照猫画虎，一顿操作就可以了 。
回到backTrace函数，其实就是一个选择/撤销选择的过程，其中的for循环也是一个选择的过程，还有一个点就是base case需要在这个函数来处理 。那么，我们就可以把框架整理出来 。
    public void backTrace(int start, int[] nums, List<Integer> temp){        base case处理        //选择过程        for(循环选择){            选择            backTrace(递归);            撤销选择        }    }ok，上面已经讲了一个子集的问题，接下来，再来一个更有点意思的子集的题目 。
2 子集问题用于引入回溯算法框架的那个题目其实比较简单，但是，思想是不变的，这个框架很重要，其他的题目基本上都是在上面的框架上进行修改的，比如，剪枝操作等 。
90. 子集 II 中等难度
回溯算法的题目，这样做，秒杀

文章插图
 
这个题目与前面的子集题目相比较，差别就在于补鞥呢包含重复的子集，也就是不能顺序改变而已，元素一样的子集出现 。
这个题目框架还是不变的，但是，要做一下简单的剪枝操作：怎么排除掉重复的子集 。
这里有两种方法可以解决这个问题，而且，后面其他的题目出现不能出现重复子集这样的限制条件的时候，都是可以用这两种方法进行解决的 。
  • 方法一：利用Set去重特性解题
我们还是先把上面的框架搬下来，然后再进行修改 。
    List<List<Integer>> list = new ArrayList<>();    public List<List<Integer>> subsets(int[] nums) {        if(nums.length == 0){            return null;        }        List<Integer> temp = new ArrayList<>();        backTrace(0, nums, temp);        return list;    }    public void backTrace(int start, int[] nums, List<Integer> temp){        list.add(new ArrayList<>(temp));        //从start开始遍历，避免重复        for(int j = start; j < nums.length; j++){            temp.add(nums[j]);            backTrace(j+1,nums,temp);            temp.remove(temp.size()-1);        }    }


推荐阅读


上一篇：什么叫淘宝客pid 淘宝客pid在哪里

下一篇：淘宝老客户优惠券如何设置 淘宝怎么设置淘客优惠券