(lintcode)第15题 全排列(没有重复数字)

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

样例
给出一个列表[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;
   }
}

 

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

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

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

公众号:秦怀杂货店

 

 

 

上一篇:(lintcode)第12题带最小值操作的栈


下一篇:(lintcode)第18题 带重复元素的子集