算法刷题日志——回溯算法

全排列

used数组用来判断是否用过了

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path =  new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
            int len = nums.length;
         if(len==0){
             return res;
         }
          used = new boolean[len];
             dfs(nums);
            return res;
    }
    public void dfs(int[]nums){
        int n = nums.length;
        if(path.size()==n){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<n;i++){
          if(used[i]){
              continue;
          }else{
                  path.add(nums[i]);
                  used[i]=true;
            dfs(nums);
            path.remove(path.size()-1);
            used[i]=false;
            }
        }
    }
}
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

全排列 II

这里进行去重，有两种 一种用set进行去重，另外就是使用used数组进行判断去重

used数组去重：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
           int len = nums.length;
         if(len==0){
             return res;
         }
          used = new boolean[len];
          Arrays.sort(nums);
             dfs(nums);
            return res;
    }
    public void dfs(int[]nums){
        int n = nums.length;
        if(path.size()==n){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<n;i++){
          if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){
              continue;
          }
          if(used[i]==false){
                  path.add(nums[i]);
                  used[i]=true;
            dfs(nums);
            path.remove(path.size()-1);
            used[i]=false;
            }
        }
 }
}
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

set去重：

class Solution {
    Set<List<Integer>> res = new HashSet<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
            int len = nums.length;
            if(len==0){
                return new ArrayList<>(res);
            }
            Arrays.sort(nums);
            used = new boolean[len];
            dfs(nums);
            return new ArrayList<>(res);
    }
    public void dfs(int[] nums){
        int n = nums.length;
        if(path.size()==n){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<n;i++){
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            dfs(nums);
            path.remove(path.size()-1);
            used[i]=false;
        }
    }
}
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

491. 递增子序列

本题求自增子序列，是不能对原数组经行排序的，这题可以不加终止条件，startIndex每次都会加1，并不会无限递归。同一父节点下的同层上使用过的元素就不能在使用了
Java中的Map提供了getOrDefault()方法，对不存在的键值提供默认值的方法。
// 存在Key1，返回11，不存在的话就返回22
System.out.println(map.getOrDefault(1,22));
这里用map来代替一个判断去重的数组，存在就返回1，不存在则返回0来进行判断，
而且map是记录本层元素是否重复使用，新的一层map都会重新定义（清空），所以要知道map只负责本层！

class Solution {
    //结果集合
    List<List<Integer>> res = new ArrayList<>();
    //路径集合
    LinkedList<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        getSubsequences(nums,0);
        return res;
    }
    private void getSubsequences( int[] nums, int start ) {
        if(path.size()>1 ){
            res.add( new ArrayList<>(path) );
            // 注意这里不要加return，要取树上的节点
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=start ;i < nums.length ;i++){
            if(!path.isEmpty() && nums[i]< path.get(path.size()-1){
                continue;
            }
            // 使用过了当前数字
            if ( map.getOrDefault( nums[i],0 ) >=1 ){
                continue;
            }
            map.put(nums[i],map.getOrDefault( nums[i],0 )+1);
            path.add( nums[i] );
            getSubsequences( nums,i+1 );
            path.remove(path.size()-1);
        }
    }
}
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