递归相关的题目

找一个字符串的不重复的子序列

递归的思路：每次按要这个位置的字符和不要这个位置的字符两种情况去递归，当i = s.length()时，保存当前的子序列。用hashSet去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   public static String[] generatePermutation(String str) {
	char[] s = str.toCharArray();
	HashSet<String> set = new HashSet<>();
	f2(s, 0, new char[s.length], 0, set);
	int m = set.size();
	String[] ans = new String[m];
	int i = 0;
	for (String cur : set) {
		ans[i++] = cur;
	}
	return ans;
}


   // i是当前要处理的字符的索引,path是当前已经保存的路径，size是path的索引
public static void f2(char[] s, int i, char[] path, int size, HashSet<String> set) {
	if (i == s.length) {
		set.add(String.valueOf(path, 0, size));
	} else {
		path[size] = s[i];
		f2(s, i + 1, path, size + 1, set);
		f2(s, i + 1, path, size, set);
	}
}

找一个数组中的所有子数组，顺序可以任意

思路：先将数组排序，然后每次对同一个数讨论，要0个，要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
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    int[] path = new int[11];
    Arrays.sort(nums);
    findSubsetsWithDup(0,nums,0,path,ans);
    return ans;
}

public void findSubsetsWithDup(int i,int[] nums,int size,int[] path,List<List<Integer>> ans){
    if(i==nums.length){
        List<Integer> temp =new ArrayList<>();
        for(int j=0;j<size;j++){
            temp.add(path[j]);
        }
        ans.add(temp);
    }else {
        //找出下一个跟自己不同的数的位置
        int j = i+1;
        while(j < nums.length && nums[j] == nums[i]){
            j++;
        }
        // 要0个
        findSubsetsWithDup(j,nums,size,path,ans);
        // 依次要多个
        for(;i<j;i++){
            path[size++] = nums[i];
            findSubsetsWithDup(j,nums,size,path,ans);
        }
    }
}

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路： 每次拿一个数跟当前下标的第一个数交换，然后递归调用将下标+1，递归完成后再交换回来。终止条件就算下标==nums.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans =new ArrayList<>();
    findPermute(nums,0,ans);
    return ans;
}

public void findPermute(int[] nums,int i,List<List<Integer>> ans){
    // 终止条件
    if(i == nums.length){
        List<Integer> temp = new ArrayList<>();
        for(int j=0;j<nums.length;j++){
            temp.add(nums[j]);
        }
        ans.add(temp);
    }else {
        // 依次交换
        for(int j = i;j<nums.length;j++){
            swap(nums,i,j);
            findPermute(nums,i+1,ans);
            // 交换回来
            swap(nums,i,j);
        }
    }
}

拓展：如果有重复数字，则需要去重

思路： 每次递归的时候维护一个set这个set记录哪些数来到过我这个下标，如果发现一个数已经来到过，则不进行交换，也不递归跳过即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   public static void f(int[] nums, int i, List<List<Integer>> ans) {
	if (i == nums.length) {
		List<Integer> cur = new ArrayList<>();
		for (int num : nums) {
			cur.add(num);
		}
		ans.add(cur);
	} else {
		HashSet<Integer> set = new HashSet<>();
		for (int j = i; j < nums.length; j++) {
			// nums[j]没有来到过i位置，才会去尝试
			if (!set.contains(nums[j])) {
				set.add(nums[j]);
				swap(nums, i, j);
				f(nums, i + 1, ans);
				swap(nums, i, j);
			}
		}
	}
}

N皇后问题

思路：维护一个路径数组path[],path的第几个数的值表示第几行的皇后放在第几列，每次循环每一行的列去判断是否合法，如果合法则递归调用下一行，并且size++.终止条件是size == n 即找到合法的一个解。

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
public static List<List<String>> solveNQueens(int n) {
    List<List<String>> ans = new ArrayList<>();
    int[] path = new int[n];
    findSolveNQueens(0,n,path,ans);
    return ans;
}

public static void findSolveNQueens(int size,int n,int[] path,List<List<String>> ans){
    // 终止条件
    if(size == n){
        List<String> temp = new ArrayList<>();
        for(int i =0;i<size;i++){
            StringBuilder sb =new StringBuilder();
            int pos =path[i];
            for(int j =0 ;j<pos;j++){
                sb.append('.');
            }
            sb.append('Q');
            for(int j = pos+1;j<n;j++){
                sb.append('.');
            }
            temp.add(sb.toString());
        }
        ans.add(temp);
    }else {
        // 依次尝试
        for(int i =0;i<n;i++){
            // 尝试第i列
            if(isvalid(i,path,size)){
                // 合法
                path[size] = i;
                findSolveNQueens(size+1,n,path,ans);
            }
        }
    }
}

public static boolean isvalid (int i ,int[] path,int size){
    for(int k = 0; k< size; k++){
        if(i==path[k]){
            return false;
        }
        if( Math.abs(size-k) == Math.abs(i-path[k])){
            return false;
        }
    }
    return true;
}

拓展： 利用位运算去判断当前位置是否合法。

示例图片
示例图片
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
   public static int totalNQueens2(int n) {
	if (n < 1) {
		return 0;
	}
	// n = 5
	// 1 << 5 = 0...100000 - 1
	// limit  = 0...011111; 
	// n = 7
	// limit  = 0...01111111; 
	int limit = (1 << n) - 1;
	return f2(limit, 0, 0, 0);
}

// limit : 当前是几皇后问题
// 之前皇后的列影响：col
// 之前皇后的右上 -> 左下对角线影响：left
// 之前皇后的左上 -> 右下对角线影响：right
public static int f2(int limit, int col, int left, int right) {
	if (col == limit) {
		// 所有皇后放完了！
		return 1;
	}
	// 总限制
	int ban = col | left | right;
	// ~ban : 1可放皇后，0不能放
	int candidate = limit & (~ban);
	// 放置皇后的尝试！
	int place = 0;
	// 一共有多少有效的方法
	int ans = 0;
	while (candidate != 0) {
		// 提取出最右侧的1
		// 0 0 1 1 1 0
		// 5 4 3 2 1 0
		// place : 
		// 0 0 0 0 1 0
		// candidate : 
		// 0 0 1 1 0 0
		// 5 4 3 2 1 0
		// place : 
		// 0 0 0 1 0 0
		// candidate : 
		// 0 0 1 0 0 0
		// 5 4 3 2 1 0
		// place : 
		// 0 0 1 0 0 0
		// candidate : 
		// 0 0 0 0 0 0
		// 5 4 3 2 1 0
		place = candidate & (-candidate);
		candidate ^= place;
		ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);
	}
	return ans;
}