likes
comments
collection
share

数据结构与算法 -- 使用DFS算法处理组合类和排列类问题(一维)

作者站长头像
站长
· 阅读数 7

本文将会介绍LeetCode中关于排列类和组合类的题目,详情见Top 100和Top 150中关于「回溯」板块的问题。

1基础概念

首先我们先了解什么是递归、深度优先搜索、回溯。

递归不是算法,我们通常叫递归是递归函数,最经典的就是斐波那契数列

首先我们需要知道什么是斐波那契数列,例如下:

1,1,2,3,5,8,13 ......

当n = 1 或者 n = 2 时,斐波那契数列的值为1,从第3项开始,其值等于前两项的和,如果使用暴力递归的方式,如下:


private int f(int N) {
    if (N == 1) {
        return 1;
    }
    if (N == 2) {
        return 1;
    }
    return f(N - 1) + f(N - 2);
}

递归是将大问题拆解成一些小问题,例如要求f(5)的值,先需要知道f(4)和f(3)的值,以此递归直到找到函数的出口,由小问题反推大问题。

深度优先搜索算法,也会使用到递归,经典的就是二叉树的前序遍历,如图:

数据结构与算法 -- 使用DFS算法处理组合类和排列类问题(一维)

利用系统栈+回溯的思想,在左侧子树先遍历到左侧叶子节点,然后回溯回到父节点,再去父节点的右子树查找。

其实回溯就是在回到上一层时,需要把状态复原,在深度优先搜索算法中,就存在回溯,只不过不需要我们自行处理。

2 组合类DFS

给定一个数组,求这个数组的全部子序列。

首先针对这种组合类的题目,我们可以先画出N叉决策树,通过查看N叉树的结构,来决定递归的三要素。

数据结构与算法 -- 使用DFS算法处理组合类和排列类问题(一维)

如上图所示,图中每个节点都是我们需要的,而在每一层节点到达数组的最后一个元素的时候,就会停止从而回溯返回。

public static List<List<Integer>> combine(int[] nums) {

    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    dfs(nums, 0, new ArrayList<>(), results);
    return results;
}


private static void dfs(int[] nums,
                        int startIndex,
                        List<Integer> subsets,
                        List<List<Integer>> results) {
    //递归的出口
    
    //这里需要对subset深拷贝的原因是,回溯会对subsets引用做操作
    //会导致结果集中的数据被篡改 
    results.add(new ArrayList<>(subsets));

    // 分解递归
    // [1] [2] [3]
    // [1,2] [1,3] [2,3]

    for (int i = startIndex; i < nums.length; i++) {
        subsets.add(nums[i]);
        dfs(nums, i + 1, subsets, results);
        subsets.remove(subsets.size() - 1);
    }

}

大家可以记住这个模板,在解决组合类问题的时候,可以套用这个模板。

2.1 DFS模板详解

其实对于求解组合类的算法题,这套模板可以解决90%的问题,我们详细介绍一下dfs这个方法。

首先我们根据题意来看:求解某个数组的子序列,什么是子序列,就是在数组中可以不连续,但是顺序不能变。 所以dfs的核心参数就是startIndex。

从题目开始的图中可以看,当startIndex = 0的时候,subset是空的,那么此时数组中所有的元素都可以用,横向看可以分成3份,可以理解为下面的3重循环。

private void combineForeach(int[] nums) {

    //假设此时nums = [1,2,3]

    for (int i = 0; i < nums.length; i++) {

        //此时 i= 0 nums[i] = 1 subset = [1]
        for (int j = i + 1; j < nums.length; j++) {

            //此时 j = 1 nums[j] = 2 subset = [1,2]
            
            for (int k = j + 1; k < nums.length; k++) {

                //此时 k = 2 nums[k] = 3 subset = [1,2,3]
            }
        }
    }

}

而碰到递归函数时,就会跳到下一层,此时0位置的元素将不能再用,因此只能跳到下一个元素的位置,此时startIndex = i+1 ,那么for循环可以分为2支就是[1,2],[1,3],如此下来就输出全部子序列。

假设题目要求,当前位置的元素可以无限次数的调用,但是当前位置的元素之前的元素将不可再被使用,求解当前数组的满足条件的序列。

那么此时dfs方法中startIndex就可以设置为i,而不是i+1,因为当前元素可以在下次递归的时候还可以再次使用。

2.2 LeetCode 39

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

那么这道题就是同位置的元素可以被多次选取,但这种情况下需要注意,因为i始终会满足循环的条件,for循环不会退出递归就不会结束,因此需要通过一些条件使得递归退出。


public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();
    if(candidates == null || candidates.length == 0){
        return results;
    }
    dfs(candidates,0,new ArrayList(),results,0,target);
    return results;
}


private void dfs(int[] nums,
                 int startIndex,
                 List<Integer> subsets,
                 List<List<Integer>> results,
                 int sum,
                 int target){
    //递归出口
    if(sum == target){
        results.add(new ArrayList(subsets));
    }

    //这种情况下,直接return跳出递归即可
    if(sum > target){
        return;
    }

    for(int i = startIndex;i<nums.length;i++){
        subsets.add(nums[i]);
        //下一轮,关键在于index的选取,因为题意中说到,元素可以被无限次数的使用
        //因此,下一轮依然可以从当前数字的位置i开始
        dfs(nums,i,subsets,results,sum + nums[i],target);
        //回溯
        subsets.remove(subsets.size()-1);
    }
}

那么如果要求不能重复地使用数字,那么就需要将下一次的dfs中的startIndex置为 i+1.

2.3 小结

所以,任意combination类型的题目,都可以采用上述DFS模版,只需要根据题意调整startIndex的位置,同时需要考虑递归的出口,防止出现StackOverFlow。

如果题目要求:任意数字在任意一次递归中都可以使用,那么startIndex就将失去意义,后续衍生的问题将会是全排列的问题,与startIndex无关。

3 排列类DFS

排列和组合的不同之处在于,假设数组长度为n,全排列的个数为n的阶乘,而子序列的个数为 2n2^n2n,可以画出决策树来看。

数据结构与算法 -- 使用DFS算法处理组合类和排列类问题(一维)

跟组合类的不同在于,排列类只有在根节点才会是最终我们要的值,因为全排列不会涉及到字符的增加或者减少,因此递归的出口只需要判断字符串的长度是否与模板长度一致即可。

public static List<List<Integer>> combine2(int[] nums) {

    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    dfs(nums, new boolean[nums.length], new ArrayList<>(), results);
    return results;
}


private static void dfs(int[] nums,
                        boolean[] visited,
                        List<Integer> subsets,
                        List<List<Integer>> results) {
    //递归的出口
    if (subsets.size() == nums.length) {
        results.add(new ArrayList<>(subsets));
    }

    // 分解递归
    // [] -> [1],[2],[3] ...
    // [1] -> [1,2] [1,3] ...

    for (int i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue;
        }
        //只添加没有访问过的数字
        subsets.add(nums[i]);
        visited[i] = true;
        dfs(nums, visited, subsets, results);
        //回溯的过程
        subsets.remove(subsets.size() - 1);
        visited[i] = false;
    }

}

3.1 DFS模板详解

与组合类的DFS不同的是,排列类的问题大都要求求解与模版长度相同的结果,例如全排列,所以每个元素在迭代的过程中都可能被用到,因此没有startIndex,反而会有一个boolean类型的数组用来标记已经被访问的元素。

例如字符串123,当访问第一个数字的时候,那么剩余的两个数字2,3都可以被使用;当访问数字2的时候,此时只剩下数字3可以被访问,最终拿到一个结果。

所以在for循环的时候,如果某个元素被访问了直接跳过。

3.2 全排列问题

已知一个字符串,求字符串的全排列,要求不允许出现重复的元素。

数据结构与算法 -- 使用DFS算法处理组合类和排列类问题(一维)

如果只是求全排列,例如字符串abb,那么个数就是 3!=3∗2∗1=63!=3*2*1 = 63!=321=6,但是因为字符串中存在相同的元素,所以不可避免会有重复的全排列元素,因此需要去重。


public static List<String> permutation(String digits) {
    List<String> results = new ArrayList<>();
    if (digits == null || digits.equals("")) {
        return results;
    }
    dfs(digits, new boolean[digits.length()], "", results);
    return results;
}


private static void dfs(String digits,
                        boolean[] visited,
                        String permute,
                        List<String> results) {
    //递归的出口
    if (permute.length() == digits.length()
            && !results.contains(permute)) {
        results.add(permute);
    }
    //拆解递归
    for (int i = 0; i < digits.length(); i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        dfs(digits, visited, permute + digits.charAt(i), results);
        //回溯
        visited[i] = false;
    }
}

最终输出的结果:[abb, bab, bba]
转载自:https://juejin.cn/post/7317468725514584127
评论
请登录