要求:给定一个数字列表,返回其所有可能的排列。

样例
给出一个列表[1,2,3],其全排列为:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路:我们首先想到的是使用递归来实现,递归里面利用了回溯法和深度优先搜索。假如有1,2,3,那么第一层递归的第一层循环里会往list里面加入1,调用第二层递归加入2,同样第三层递归加入了3,第四层递归已经加满了数,没有再加入数,直接返回,则执行第三层的remove一个数,执行第二层的remove,再递归加入3,递归里面再递归加入2,然后再remove 2,remove 3,remove 1,第一层递归第二次循环里加入2,递归加入1,再递归加入3,依次类推。

所以递归代码如下:

 

class Solution {    /**     * @param nums: A list of integers.     * @return: A list of permutations.     */    public List<List> permute(int[] nums) {        List<List> res = new ArrayList<>();        if(nums == null)            return res;        if(nums.length == 0)        {                res.add(new ArrayList());            return res;        }        ArrayListlist = new ArrayList<>();        dfs(res, list, nums);        return res;   }    private void dfs(List<List> res, ArrayListlist, int[] nums) {        int n = nums.length;        if(list.size() == n)        {                res.add(new ArrayList(list));            return;        }        for(int i = 0;i < n;i++) {            if(list.contains(nums[i]))                continue;            list.add(nums[i]);            dfs(res, list, nums);            list.remove(list.size() - 1);        }    }}

还有一种非递归实现的方法,思路如下:也就是使用插入法,假如传进去的数字是1,2,3,那么先把1放进去list中得到【1】,把【1】放到list(存放list的list)中得到【【1】】然后取出【【1】】里面的第一个list【1】,往里面插入2,这个数字,有两种插法,就产生了两种排列【1,2】【2,1】,放进去得到【【1,2】,【2,1】】,然后取出【1,2】,插入3,有三种情况【3,1,2】,【1,3,2】,【1,2,3】,把它们放进去就是【【2,1】,【3,1,2】,【1,3,2】,【1,2,3】】,接着把【2,1】取出来,将3插进去,也有3中插法,就得到了最后的排列【【3,1,2】,【1,3,2】,【1,2,3】,【3,2,1】,【2,3,1】,【2,1,3】】,直到这里数组中的元素已经全部插入完毕。

 

代码如下:

 

class Solution {    /**     * @param nums: A list of integers.     * @return: A list of permutations.     */    public List<List> permute(int[] nums) {        List<List> res = new ArrayList<List>();          if ( nums == null)              return res;        if( nums.length == 0)        {                res.add(new ArrayList());            return res;        }        Listlist = new ArrayList<>();        list.add(nums[0]);        res.add(new ArrayList(list));        for(int i=1;i<nums.length;i++) {            int size1 = res.size();            for(int j=0;j<size1;j++) {                int size2 = res.get(0).size();                for(int k=0;k<=size2;k++) {                    ArrayListtemp = new ArrayList<>(res.get(0));                    temp.add(k,nums[i]);                    res.add(temp);                }                res.remove(0);            }        }        return res;   }}

 

如果有所帮助,脸皮厚求个赞~

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

 

 

 

©著作权归作者所有:来自51CTO博客作者秦怀杂货店的原创作品,如需转载,请注明出处,否则将追究法律责任

更多相关文章

  1. (lintcode)第5题第k大元素
  2. 函数编写n的阶乘的两种方法:循环和递归
  3. SkipList和java中ConcurrentSkipListMap的实现
  4. Ubuntu Linux 安装 .7z 解压和压缩文件
  5. 【递归】JavaScript实现99乘法表的编写(双层for循环与递归方法)
  6. influxDB安装部署及入门
  7. 2021-04-12:判断二叉树是否是搜索二叉树?
  8. Java常见排序算法之插入排序
  9. MySQL SQL hint 提示

随机推荐

  1. pyuthon高级技巧2
  2. python闭包变量迟邦定
  3. 廖雪峰Python教程 学习笔记3 hello.py
  4. 如果前面的任务成功,芹菜会运行任务
  5. Python简介及入门
  6. 函数参数中裸星号的目的是什么?
  7. 用python写MapReduce函数——以WordCount
  8. cv2.createShapeContextDistanceExtracto
  9. 关于python中的类方法(classmethod)和静态
  10. IIS 部署 python web框架 Flask