algorithm

Posted on

backtracking

1. Permutation

在当前的进度上，接下来有很多的元素，并且是等价的，需要，接受一个，然后替换另一种可能性，过程中失败回到上一个状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//nums不需要排序，但是不能有重复元素
private void backtracking(List<List<Integer>> list,List<Integer> tempList,int[] nums){
    if(tempList.size()==nums.length){
        list.add(new ArrayList<>(tempList));//在很多的递归过程中都需要注意：如果List<Integer> newList=tempList，指向的还是同一个对象，导致最后的结果中都是同一个元素。
    	return;
    }
    for(int i=0;i<nums.length;i++){
		if(tempList.contains(nums[i]))continue;//nums中不能有重复元素。前tempList.size()个元素都要重新过一遍，浪费时间，下面方法用的是复制数组（去掉加入到tempLis中的元素，只剩下没有加入的）
        tempList.add(nums[i]);
        backtracking(list,tempList,nums);
        tempList.remove(tempList.size()-1);
    }
}

//当nums有重复元素的时候，在for循环中想办法两个重复变量相邻时候互换位置是同一个排列的重复情况
//容易想到用复制元素的方法，但每层都要额外的空间，
public void backtrack(List<List<Integer>> res,List<Integer> tmp,int[] nums,int len){
    if(len==tmp.size()){
        res.add(new ArrayList(tmp));
       return;
    }
    for(int i=0;i<nums.length;i++){
        if(i>0&&nums[i]==nums[i-1])continue;//此时跳过了重复元素，但是该重复元素后面还要用。
        tmp.add(nums[i]);
        backtrack(res,tmp,removedArray(nums,i),len);
        tmp.remove(tmp.size()-1);
    }
}
public int[] removedArray(int[] nums,int x){
    int[] re=new int[nums.length-1];
    int j=0;
    for(int i=0;i<nums.length;i++){
        if(i==x)continue;
        else
            re[j++]=nums[i];
    }
    return re;
}

//用一个数组标记数字是否已经用到
private void solve(int depth, int[] nums, List<List<Integer>> ans, List<Integer> cur, boolean[] used) {
        if (depth == nums.length) {
            ans.add(new ArrayList<Integer>(cur));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])) continue;
            used[i] = true; cur.add(nums[i]);
            solve(depth + 1, nums, ans, cur, used);
            used[i] = false; cur.remove(cur.size() - 1);
        }
  }

//交换的思想，将整个数列看成两个部分，第一个数字和其余的数字，全排列只有两种情况，交换一下就行。对于其余的数字，依然采用这种方式，递归的求出全排列。
//c++
class Solution {
public:
    void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
        if (i == j-1) {
            res.push_back(num);
            return;
        }
        for (int k = i; k < j; k++) {
            if (i != k && num[i] == num[k]) continue;
            swap(num[i], num[k]);
            recursion(num, i+1, j, res);//值传递，传递的是副本，不是同一个num
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >res;
        recursion(num, 0, num.size(), res);
        return res;
    }
};