（LeetCode）Java 求解全排列

缺乏、安全感 2022-10-26 04:57 133阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、总结

## 一、题目 ##

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

![在这里插入图片描述][20210201212326290.png]

--------------------

解析：  
该题也是明显的回溯问题。

题目要求选过的数字不能重复选，  
例如\[1,2,3\]，第一次选了1，第二次只能选\[2,3\]，如果第二次选择2，第三次只能选3.

所以需要设置一个布尔数组，用来判定一个数字是否已经被选过。

## 二、代码 ##

class Solution { 
        List<List<Integer>> lists = new ArrayList();
    
        public List<List<Integer>> permute(int[] nums) { 
            //初始化判定数组都为 false
            boolean[] flag = new boolean[nums.length];
            //index 用来计数已经选定了几个
            findPermute(flag, nums, 0);
            return lists;
        }
    
        Deque<Integer> deque = new LinkedList<>();
    
        public void findPermute(boolean[] flag, int[] nums, int index) { 
            if (index == nums.length) { 
                lists.add(new ArrayList(deque));
                return;
            }
            for (int i = 0; i < nums.length; i++) { 
                //如果该数字还没被选定过，则加入双端队列
                if (flag[i] == false) { 
                    deque.add(nums[i]);
                    flag[i] = true;
                    findPermute(flag, nums, index + 1);
                    flag[i] = false;
                    //移出双端队列的最后一位
                    deque.pollLast();
                }
            }
        }
    }

## 三、总结 ##

该题和前面做的回溯不同，需要自己设定一个数组flag判定状态，设定一个数字index记录已经选定了几位

//初始化判定数组都为 false
    boolean[] flag = new boolean[nums.length];

同样复习下双端队列的使用：

//初始化双端队列
    Deque<Integer> deque = new LinkedList<>();
    //末尾入队列
    deque.add(nums[i]);
    //队头入队列
    deque.addFirst(nums[i]);
    //移出双端队列的最后一位
    deque.pollFirst();
    //移出双端队列的最后一位
    deque.pollLast();

还有这里的拷贝操作：

lists.add(new ArrayList(deque));

[20210201212326290.png]: /images/20221024/947a65c5c59d471283935b8e62dd9503.png