通过【lintCode-15全排列问题】学习DFS算法

小咪咪 2022-05-18 07:52 133阅读 0赞

*这周发现毕业一年后自己对于技术的激情好像变得已经没有以前那么热爱与执着了，不再像以前那样每天想着都在学习新的技术，也不再因为每天没有学习到新的东西而会感到负罪感。也或许是我在大公司里由于长期没有压力的工作让我习惯了这样的日子，日复一日的轻松惯了导致的，但偶尔理智的我知道这种轻松的日子并不是我所想要的，至少现阶段不是。干IT这行还是不能堕落原地踏步，得向前看不能掉队，应紧紧跟上科技的浪潮。*

*————————————————————————————————————————————————————*

*————————————————————————分隔线—————————————————————————*

*————————————————————————————————————————————————————*

### 描述 ###

给定一个数字列表，返回其所有可能的排列。

题目链接：[https://www.lintcode.com/problem/permutations/description][https_www.lintcode.com_problem_permutations_description]

做这个问题如果一时没想到解法，可以先参考一段比这个问题简单的**将0-N之前的所有排列全列出来**的DFS算法

import java.util.Scanner;
    
    public class dfs {
        public static int[] arr = new int[1000];
        public static int[] flag = new int[1000];//标志哪些数字已经被用
    
        public static void dfs(int order, int d) {
            if (order == d + 1) {
                for (int i = 1; i <= d; i++)
                    System.out.print(arr[i]);
                System.out.println();
                return;
            }
            for (int i = 1; i <= d; i++) {
                if (flag[i] == 0)//如果该数字未被占用
                {
                    arr[order] = i;
                    flag[i] = 1;//将该数字的访问权限置为1
                    dfs(order + 1, d);
                    flag[i] = 0;//重新将该数字的访问权限置为0
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.print("请输入一个全排列数:");
            while (in.hasNextInt()) {
                int ans = in.nextInt();//接收输入的数字
                System.out.println(ans + "的所有全排列如下:");
                dfs(1, ans);
            }
        }
    
    }

其运行结果如下图：

![70][]

有了上面的可参考代码后，再加以思考，可以发现上面代码的递归过程类似于建立了一颗可回溯的树，通过遍历每一个节点来找到符合条件的所有节点序列。

然后依葫芦画瓢，再将此问题的代码写出来：

![70 1][]

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class MyDfs {
        public static void main(String[] args) {
            MyDfs myDfs = new MyDfs();
            myDfs.permute(new int[]{1, 2, 3});
        }
    
        public List<List<Integer>> permute(int[] nums) {
            boolean[] hasAccessFlagArray = new boolean[nums.length];
            int[] tempArray = new int[nums.length];
            List<List<Integer>> resultList = new ArrayList<>();
            dfsFunc(0, tempArray, nums, hasAccessFlagArray, resultList);
            for (List<Integer> integers : resultList) {
                for (Integer integer : integers) {
                    System.out.print(integer + " ");
                }
                System.out.println();
            }
            return resultList;
        }
    
        private void dfsFunc(int index, int[] tempArray, int[] nums, boolean[] hasAccessFlagArray, List<List<Integer>> resultList) {
            if (index == nums.length) {
                List<Integer> subItemList = new ArrayList<>();
                for (int i = 0; i < nums.length; i++) {
                    subItemList.add(tempArray[i]);
                }
                resultList.add(subItemList);
            }
            for (int i = 0; i < nums.length; i++) {
                if (!hasAccessFlagArray[i]) {
                    hasAccessFlagArray[i] = true;
                    tempArray[index] = nums[i];
                    dfsFunc(index + 1, tempArray, nums, hasAccessFlagArray, resultList);
                    hasAccessFlagArray[i] = false;
                }
            }
        }
    }

[https_www.lintcode.com_problem_permutations_description]: https://www.lintcode.com/problem/permutations/description
[70]: /images/20220518/df1b56383dda473aa733b732bb844a96.png
[70 1]: /images/20220518/5bbf7d5fc70f4f5da73a8cdf5bfb4a47.png