本文讲述的是有关于排列问题,这也是算法中的一个重要的方法:回溯法。
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
题目大意:给出一个数组,这个数组是没有重复数字的,求出这个数组的全排列。
思路:这个其实就是一个树形问题。树形问题采用回溯法是较为经典的方法。
List<List<Integer>> res = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0) return res;
LinkedList<Integer> p = new LinkedList<>();
used = new boolean[nums.length];
permuteHelper(nums,0,p);
return res;
}
public void permuteHelper(int[] nums,int index,LinkedList<Integer> list){
if (nums.length == index) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
res.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,index+1,list);
used[i] = false;
list.removeLast();
}
}
}
我个人是不喜欢采用全局变量的,所以还是该为了函数变量。代码如下:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permuteRes = new ArrayList<>();
boolean[] used = new boolean[nums.length];
if (nums == null || nums.length == 0) return permuteRes;
LinkedList<Integer> p = new LinkedList<>();
permuteHelper(nums,p,permuteRes,used);
return permuteRes;
}
public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
permuteRes.add(listClone);
return;
}
for (int i = 0 ;i<nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,permuteRes,used);
used[i] = false;
list.removeLast();
}
}
}
这是一个最为基本的排列问题,下面我们来看看一个有重复数字的数组,看看是如何让进行排列的。
List<List<Integer>> res = new ArrayList<>();
boolean[] used; //采用的是全局变量,记录当前的元素是否已经使用了
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length]; // 注意,虽然 used是定义的类的成员变量,但是分配空间可以在子函数里面进行
if (nums.length == 0||nums == null) return res; //如果数组为空或者数组里面没有元素 返回res
LinkedList<Integer> p = new LinkedList<>(); //这里定义为LinkedList的目的是在结尾进行增删操作。
// 如果是ArrayList的话,只能在结尾添加,不能在结尾删除
permute_recursion( nums,0,p); // 初始时候。index的值为0,
return res;
}
/**
*
* @param nums
* @param index
* @param list
*/
public void permute_recursion(int[] nums, int index, LinkedList<Integer> list ) {
if (nums.length == index) { //当前的索引已经超出了 数组的最大的索引 ,说明list中存储的数据已经是一个完整的组合了
LinkedList<Integer> list_clone = (LinkedList<Integer>)list.clone();//java参数是引用专递机制,发现list中存储的是一个完整的组合后,
//将这个组合 克隆一份 添加到res中,否则后续的程序会修改list
res.add(list_clone); //将克隆后的组合添加到res中
return;
}
for (int i =0;i <nums.length ;i++){
if (used[i] == false ){ //这里采用的是一个boolean的数组,来记录当前的索引的元素是否已经使用过
list.addLast(nums[i]); //将新的元素添加到list的尾部,
used[i] = true; // 同时将used的数组 设置为true 表示这个元素已经使用过了
permute_recursion(nums,index+1,list); // 递归
used[i] = false; //清除这个used的标记
list.removeLast(); // 递归完毕后,将最后一个数据删除,以便于尝试其他的组合,这一步也就是回溯算法的“回溯”的体现所在
}
}
}
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路:有重复数字的排列的结果与没有重复数字的排列结果相比较,就是把没有重复数字的排列结果中相同的去掉了。所以我们可以很容易的想到借用java的Set数据结构,可以很容易的排重。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permuteRes = new ArrayList<>();
Set<LinkedList<Integer>> set = new HashSet<>();
boolean[] used = new boolean[nums.length];;
if (nums == null || nums.length == 0) return permuteRes;
LinkedList<Integer> p = new LinkedList<>();
permuteHelper(nums,p,set,used);
return new ArrayList<>(set);
}
public void permuteHelper(int[] nums,LinkedList<Integer> list, Set<LinkedList<Integer>> set, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
set.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,set,used);
used[i] = false;
list.removeLast();
}
}
}
思路:能不能在查找的过程中就排除重复的情况呢?若果能,那么怎么排除呢?重复的情况又是怎样的呢?带着这些问题,我们发现重复的情况是:拿题目中[1,1,2]来说,如果第一次选1(0),第二次选择1(1),与第一次选1(1),第二次选择1(0),这是同样的结果,这就是重复的原因,所以当索引为i的数字等于索引为i-1的数字时候,如果索引为i-1的数字没有被使用,那么这种情况就是重复的,应该跳过,转化为程序就是:nums[i]== nums[i-1]&&used[i-1]==false,同时要要考虑此时i>0;所以这个时候,for循环中的判断就是if(used[i]||(i>0&&nums[i]== nums[i-1]&&used[i-1]==false)),满足条件则跳过。
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> permuteRes = new ArrayList<>();
boolean[] used = new boolean[nums.length];
if (nums == null || nums.length == 0) return permuteRes;
permuteHelper(nums,new LinkedList<>(),permuteRes,used);
return permuteRes;
}
public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
permuteRes.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i]||(i>0&&nums[i] == nums[i-1]&&used[i-1]==false)) continue;
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,permuteRes,used);
used[i] = false;
list.removeLast();
}
}
还要注意的是,这样的解法必须数组数有序的数组,由于LeetCode46中的数组是没有重复数字的,因此不需要有序,所以首先要将数组进行一个排序处理。另外:解法二在查找的过程中就已经排除了重复的值,解法一是将左右的找到放在一个Set中进行去重,这样的时间效率显然没有解法二高。这种解法与解法一的不同之处在于,本解法是在查找到过程中就将不符合要求的情况排除出去,因此算法的效率有很明显的提升。
对与排列组合问题,首先想到的是采用回溯算法,回溯算法是算法中的几个较为经典的算法之一,这个算法的核心思想就是回溯的过程,代码中的list.removeLast();
很多人认为回溯和递归是一样的,其实不然。在回溯法中可以看到有递归的身影,但是两者是有区别的。回溯法从问题本身出发,寻找可能实现的所有情况。和穷举法的思想相近,不同在于穷举法是将所有的情况都列举出来以后再一一筛选,而回溯法在列举过程如果发现当前情况根本不可能存在,就停止后续的所有工作,返回上一步进行新的尝试。递归是从问题的结果出发,例如求 n!,要想知道 n!的结果,就需要知道 n*(n-1)! 的结果,而要想知道 (n-1)! 结果,就需要提前知道 (n-1)*(n-2)!。这样不断地向自己提问,不断地调用自己的思想就是递归。回溯和递归唯一的联系就是,回溯法可以用递归思想实现。
本算法就是回溯的体现,有关组合的问题可以参照《leetCode 77&39. Combinations & Combination Sum》;
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。