美文网首页
46. 全排列

46. 全排列

作者: justonemoretry | 来源:发表于2020-08-15 18:45 被阅读0次

    自己解法

    这个题的思路比较简单,就是经典的回溯法,但是写起来并没有那么的得心应手,主要是对于还可以使用的元素的处理不是特别清晰,最开始是可使用元素也用了回溯的操作,这样发现循环里面会存在增加元素,而继续进行的情况,把这个地方改成每次新维护数组以后就可以了。

    class Solution {

        List<List<Integer>> output = new ArrayList<>(16);

        List<Integer> res = new ArrayList<>(16);

        int count;

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

            if (nums.length == 0) {

                return output;                 

            }

            count = nums.length;

            List<Integer> remainNums = Arrays.stream(nums)

                            .boxed()

                            .collect(Collectors.toList());

            dfs(remainNums);

            return output;

        }

        public void dfs(List<Integer> remainNums) {

            if (res.size() == count) {

                output.add(new ArrayList<Integer>(res)); 

                return;            

            }

            for (int i = 0; i < remainNums.size(); i++) {

                int a = remainNums.get(i);

                List<Integer> remainList = new ArrayList<Integer>(remainNums);

                res.add(a);

                remainList.remove(i);

                dfs(remainList);

                res.remove(res.size() - 1);

            }

        } 

    }

    官方解法

    首先解法思路都是一样的,这种是用了个boolean[] used来维护哪些下标是已经访问过的,在回溯的过程中,置used[i]为false,来重置,这样处理整体更协调一些。

    import java.util.ArrayList;

    import java.util.List;

    public class Solution {

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

            // 首先是特判

            int len = nums.length;

            // 使用一个动态数组保存所有可能的全排列

            List<List<Integer>> res = new ArrayList<>();

            if (len == 0) {

                return res;

            }

            boolean[] used = new boolean[len];

            List<Integer> path = new ArrayList<>();

            dfs(nums, len, 0, path, used, res);

            return res;

        }

        private void dfs(int[] nums, int len, int depth,

                        List<Integer> path, boolean[] used,

                        List<List<Integer>> res) {

            if (depth == len) {

                res.add(new ArrayList<Integer>(path));

                return;

            }

            for (int i = 0; i < len; i++) {

                if (!used[i]) {

                    path.add(nums[i]);

                    used[i] = true;

                    dfs(nums, len, depth + 1, path, used, res);

                    // 注意:这里是状态重置,是从深层结点回到浅层结点的过程,代码在形式上和递归之前是对称的

                    used[i] = false;

                    path.remove(path.size() - 1);

                }

            }

        }

        public static void main(String[] args) {

            int[] nums = {1, 2, 3};

            Solution solution = new Solution();

            List<List<Integer>> lists = solution.permute(nums);

            System.out.println(lists);

        }

    }

    相关文章

      网友评论

          本文标题:46. 全排列

          本文链接:https://www.haomeiwen.com/subject/qiwadktx.html