电信保温杯笔记——代码随想录 刷题攻略 回溯算法_左程云回溯算法

电信保温杯笔记——代码随想录 刷题攻略

代码随想录 刷题攻略
电信保温杯笔记——代码随想录 刷题攻略

1.关于回溯算法，你该了解这些！

讲义地址

2.回溯算法：组合问题

讲义地址

第77题. 组合

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return res;
    }
    public void combineHelper(int n, int k, int idx){
        if (path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < n + 1; i++){
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.回溯算法：组合问题再剪剪枝

讲义地址

4.回溯算法：求组合总和！

讲义地址

216.组合总和III

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        combinationSum3Helper(k, n, 1, 0);
        return res;
    }
    public void combinationSum3Helper(int k, int n, int idx, int sum){
        if (path.size() == k){
            if (sum == n){
                res.add(new ArrayList(path));
            }
            return;
        }

        for (int i = idx; i < 10 - (k - path.size() - 1); i++){
            // 原本是i < n + 1，n + 1 = 10，但如果i超过限度，
            // 后面更深层的递归里i就没有可取的值，所以此轮i不能超过这个限度，
            // path已选size()个元素，此轮有一个元素，此轮i取值后，path有size() + 1个元素，
            // 更深层的递归还有k - path.size() - 1个元素，所以此轮取值应该排除最后k - path.size() - 1个元素
            if (sum + i > n){
                break;
            }
            path.add(i);
            combinationSum3Helper(k, n, i + 1, sum + i);
            path.removeLast();
        }
    }
}
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

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        combinationSum3Helper(k, n, 1, 0);
        return res;
    }
    public void combinationSum3Helper(int k, int n, int idx, int sum){
        if (path.size() == k){
            if (sum == n){
                res.add(new ArrayList(path));
            }
            return;
        }

        for (int i = idx; i < 10 - (k - (path.size() + 1)) ; i++){
            // 原本是i < n + 1，n + 1 = 10，但如果i超过限度，
            // 后面更深层的递归里i就没有可取的值，所以此轮i不能超过这个限度，
            // path已选size()个元素，此轮有一个元素，此轮i取值后，path有size() + 1个元素，
            // 更深层的递归还有k - path.size() - 1个元素，所以此轮取值应该排除最后k - path.size() - 1个元素
            if (!isValid(sum, i, n)){
                break;
            }

            path.add(i);
            combinationSum3Helper(k, n, i + 1, sum + i);
            path.removeLast();
        }
    }
    public boolean isValid(int sum, int i, int n){
        if (sum + i > n){
            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

5.回溯算法：电话号码的字母组合

讲义地址

17.电话号码的字母组合

leetcode地址

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0){
            return res;
        }
        letterVombinationsHelper(digits, 0);
        return res;
    }
    public void letterVombinationsHelper(String digits, int idx){
        if (idx == digits.length()){
            res.add(path.toString());
            return;
        }
        char c = digits.charAt(idx);
        Integer num = c - '0';
        String str = map[num];
        for (int i = 0; i < str.length(); i++){
            path.append(str.charAt(i));
            letterVombinationsHelper(digits, idx + 1);
            path.deleteCharAt(path.length() - 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

6.本周小结！（回溯算法系列一）

讲义地址

7.回溯算法：求组合总和（二）

讲义地址

39. 组合总和

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0){
            return res;
        }
        Arrays.sort(candidates);
        combineHelper(candidates, target, 0, 0);
        return res;
    }

    public void combineHelper(int[] candidates, int target, int sum, int idx){
		// #
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++){
            if (sum + candidates[i]> target){
                return; // 这里可以return，可以break，因为candidates是经过排序的，所以没有关系，这个判断也可以写在#号的位置，但那样就多了path的add和removeLast的步骤，效率变低
            }
            path.add(candidates[i]);
            combineHelper(candidates, target, sum + candidates[i], i); // 这个i是与前门题目的区别
            path.removeLast();
        }
    }
}
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

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSumHelper(candidates, target, 0, 0);
        return res;
    }
    public void combinationSumHelper(int[] candidates, int target, int startNum, int sum){
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startNum; i < candidates.length; i++){
            if (!isValid(candidates, i, target, sum)){
                break;
            }

            path.add(candidates[i]);
            combinationSumHelper(candidates, target, i, sum + candidates[i]);
            path.removeLast();
        }
    }
    public boolean isValid(int[] candidates, int i, int target, int sum){
        if (sum + candidates[i] > target){
            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

8.回溯算法：求组合总和（三）

讲义地址

左边元素的used必定是true，右边元素的used为false。

40.组合总和II

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0){
            return res;
        }
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        //加标志数组，用来辅助判断同层节点是否已经遍历
        boolean[] used = new boolean[candidates.length];
        combinationSum2Helper(candidates, target, 0, 0, used);
        return res;
    }
    public void combinationSum2Helper(int[] candidates, int target, int idx, int sum, boolean[] used){
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        // i 是从0开始还是index开始，决定了它是否是组合
        for (int i = idx; i < candidates.length; i++){
            if (sum + candidates[i] > target){
                break;
            }
            //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]){
                continue;
            }
            used[i] = true;
            path.add(candidates[i]);
            combinationSum2Helper(candidates, target, i + 1, sum + candidates[i], used);
            path.removeLast();
            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
35
36
37

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0){
            return res;
        }
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        //加标志数组，用来辅助判断同层节点是否已经遍历
        boolean[] used = new boolean[candidates.length];
        combinationSum2Helper(candidates, target, 0, 0, used);
        return res;
    }
    public void combinationSum2Helper(int[] candidates, int target, int idx, int sum, boolean[] used){
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        // i 是从0开始还是index开始，决定了它是否是组合
        for (int i = idx; i < candidates.length; i++){
            if (!isValid1(candidates, i, sum, target)){
                break;
            }
            if (!isValid2(candidates, i, used)){
                continue;
            }
            used[i] = true;
            path.add(candidates[i]);
            combinationSum2Helper(candidates, target, i + 1, sum + candidates[i], used);
            path.removeLast();
            used[i] = false;
        }
    }
    public boolean isValid1(int[] candidates, int i, int sum, int target){
        if (sum + candidates[i] > target){
            return false;
        }
        return true;
    }
    public boolean isValid2(int[] candidates, int i, boolean[] used){
        //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
        if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]){
            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

9.回溯算法：分割回文串

讲义地址

131.分割回文串

leetcode地址

精简版

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return res;
    }

    public void backTracking (String s, int idx){
        if (idx >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = idx; i < s.length(); i++){
            if (!isPalindrome(s, idx, i)){
                continue;
            }
            String str = s.substring(idx, i + 1);
            path.add(str);
            backTracking(s, i + 1);
            path.removeLast();
        }
    }

    public boolean isPalindrome(String str, int left, int right){
        for (int i = left, j = right; i < j; i++, j--){
            if (str.charAt(i) != str.charAt(j)){
                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

框架板

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return res;
    }

    public void backTracking (String s, int idx){
        if (idx == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = idx; i < s.length(); i++){
            if (!isValid(s, idx, i)){
                continue;
            }
            String str = s.substring(idx, i + 1);
            path.add(str);
            backTracking(s, i + 1);
            path.removeLast();
        }
    }
    public boolean isValid(String str, int left, int right){
        for (int i = left, j = right; i < j; i++, j--){
            if (str.charAt(i) != str.charAt(j)){
                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

10.回溯算法：复原IP地址

讲义地址

93.复原IP地址

leetcode地址

精简版

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        restoreIpAddressesHelper(s, 0, 0);
        return res;
    }

    public void restoreIpAddressesHelper(String s, int idx, int pathSize) {
        if (idx == s.length() || pathSize > 4){
            if (idx == s.length() && pathSize == 4) {
                res.add(path.toString());
            }
            return;
        }
        for (int i = idx; i < idx + 3 && i < s.length(); i++){
            if (i - idx > 0 && s.charAt(idx) == '0'){
                continue;
            }
            int temp  = Integer.parseInt(s.substring(idx, i + 1));
            if (temp < 0 || temp > 255){
                continue;
            }

            path.append(s.substring(idx, i + 1));
            if (pathSize < 3) {
                path.append(".");
            }
            restoreIpAddressesHelper(s, i + 1, pathSize + 1);
            path.delete(idx + pathSize, i + pathSize + 2);
        }
    }
}
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

框架板

class Solution {
    List<String> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        restoreIpAddressesHelper(s, 0);
        return res;
    }

    public void restoreIpAddressesHelper(String s, int idx) {
        if (path.size() == 4){
            if (idx == s.length()) {
                res.add(toString(path));
            }
            return;
        }
        for (int i = idx + 1; i < idx + 4 && i < s.length() + 1; i++){
            if (!isValid1(s, idx, i)){
                continue;
            }
            String str = s.substring(idx, i);
            if (!isValid2(str)){
                continue;
            }
            path.add(str);
            restoreIpAddressesHelper(s, i);
            path.removeLast();
        }
    }
    public boolean isValid1(String s, int start, int end){
        if (end - start > 1 && s.charAt(start) == '0'){
            // 0开头且长度>1
            return false;
        }
        return true;
    }
    public boolean isValid2(String s){
        int num = Integer.parseInt(s);
        if (num < 0 || num > 255){
            return false;
        }
        return true;
    }
    public String toString(LinkedList<String> path){
        String str = "";
        for (int i = 0; i < path.size() - 1; i++){
            str += path.get(i) + ".";
        }
        str += path.get(path.size() - 1);
        return str;
    }
}
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

11.回溯算法：求子集问题！

讲义地址

78.子集

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>());
        subsetsHelper(nums, 0);
        return res;
    }
    public void subsetsHelper(int[] nums, int idx){
        if (idx == nums.length){
            return;
        }
        for (int i = idx; i < nums.length; i++){
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            subsetsHelper(nums, i + 1);
            path.removeLast();

        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

12.本周小结！（回溯算法系列二）

讲义地址

13.回溯算法：求子集问题（二）

讲义地址

90.子集II

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        res.add(new ArrayList<>());
        subsetsWithDupHelper(nums, 0, used);
        return res;
    }
    public void subsetsWithDupHelper(int[] nums, int idx, boolean[] used){
        if (idx == nums.length){
            return;
        }
        for (int i = idx; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            subsetsWithDupHelper(nums, i + 1, used);
            path.removeLast();
            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

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        res.add(new ArrayList<>());
        subsetsWithDupHelper(nums, 0, used);
        return res;
    }
    public void subsetsWithDupHelper(int[] nums, int idx, boolean[] used){
        if (idx == nums.length){
            return;
        }
        for (int i = idx; i < nums.length; i++){
            if (!isValid(nums, i, used)){
                continue;
            }

            used[i] = true;
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            subsetsWithDupHelper(nums, i + 1, used);
            path.removeLast();
            used[i] = false;
        }
    }
    public boolean isValid(int[] nums, int i, boolean[] used){
        if (i > 0 && nums[i] == nums[i - 1] && !used[i -1]){
            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

14.回溯算法：递增子序列

讲义地址

491.递增子序列

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        findSubsequencesHelper(nums, 0);
        return res;
    }

    public void findSubsequencesHelper(int[] nums, int idx){
        if (path.size() > 1){
            res.add(new ArrayList<>(path));
        }
        HashMap<Integer, Integer> used = new HashMap<>();

        for (int i = idx; i < nums.length; i++){
            if (used.getOrDefault(nums[i], 0) > 0){
                // 已经用过
                continue;
            }
            if (path.size() > 0 && path.getLast() > nums[i]){
                // 不递增
                continue;
            }
            // 没用过
            used.put(nums[i], 1);

            path.add(nums[i]);
            findSubsequencesHelper(nums, i + 1);
            path.removeLast();
        }
    }
}
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

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        findSubsequencesHelper(nums, 0);
        return res;
    }

    public void findSubsequencesHelper(int[] nums, int idx){
        if (path.size() == nums.length){
            return;
        }
        // 记录当前轮遍历，元素是否用过
        HashMap<Integer, Integer> used = new HashMap<>();

        for (int i = idx; i < nums.length; i++){
            if (!isValid1(nums, used, i)){
                continue;
            }
            if (!isValid2(nums, i)){
                continue;
            }
            
            used.put(nums[i], 1);
            path.add(nums[i]);
                if (path.size() > 1){
                res.add(new ArrayList<>(path));
            }
            findSubsequencesHelper(nums, i + 1);
            path.removeLast();
        }
    }
    public boolean isValid1(int[] nums, HashMap<Integer, Integer> used, int i){
        if (used.getOrDefault(nums[i], 0) > 0){
            // 已经用过
            return false;
        }
        return true;
    }
    public boolean isValid2(int[] nums, int i){
        if (path.size() > 0 && nums[i] < path.getLast()){
            // 不递增
            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

15.回溯算法：排列问题！

讲义地址

46.全排列

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        permuteHelper(nums, used);
        return res;
    }
    public void permuteHelper(int[] nums, boolean[] used){
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            permuteHelper(nums, used);
            path.removeLast();
            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

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        permuteHelper(nums, used);
        return res;
    }
    public void permuteHelper(int[] nums, boolean[] used){
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (!isValid(i, used)){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            permuteHelper(nums, used);
            path.removeLast();
            used[i] = false;
        }
    }
    public boolean isValid(int i, boolean[] used){
        if (used[i]){
            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

16.回溯算法：排列问题（二）

讲义地址

47.全排列 II

leetcode地址

精简版

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        permuteUniqueHelper(nums, used);
        return res;
    }

    public void permuteUniqueHelper(int[] nums, boolean[] used){
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
            if (!used[i]){
                used[i] = true;
                path.add(nums[i]);
                permuteUniqueHelper(nums, used);
                path.removeLast();
                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

框架板

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        permuteUniqueHelper(nums, used);
        return res;
    }

    public void permuteUniqueHelper(int[] nums, boolean[] used){
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (!isValid1(nums, i, used)){
                continue;
            }
            if (!isValid2(i, used)){
                continue;
            }
            
            used[i] = true;
            path.add(nums[i]);
            permuteUniqueHelper(nums, used);
            path.removeLast();
            used[i] = false;
        }
    }
    public boolean isValid1(int[] nums, int i, boolean[] used){
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
            return false;
        }
        return true;
    }
    public boolean isValid2(int i, boolean[] used){
        if (used[i]){
            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

17.本周小结！（回溯算法系列三）

讲义地址

18.回溯算法去重问题的另一种写法

讲义地址

19.回溯算法：重新安排行程

讲义地址

332.重新安排行程

leetcode地址

1
1

20.回溯算法：N皇后问题

讲义地址

第51题. N皇后

leetcode地址
左神视频有最高效的做法：位运算，一周刷爆LeetCode，算法da神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解 笔记

方式一：使用数组代替位运算

精简版

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        if (n == 0){
            return res;
        }
        if (n == 1){
            path.add("Q");
            res.add(new ArrayList<>(path));
            return res;
        }
        int[] colLim = new int[n];
        int[] leftLim = new int[n];
        int[] rightLim = new int[n];
        Arrays.fill(colLim, 1);
        Arrays.fill(leftLim, 1);
        Arrays.fill(rightLim, 1);
        solveNQueensHelper(n, colLim, leftLim, rightLim);
        return res;
    }
    public void solveNQueensHelper(int n, int[] colLim, int[] leftLim, int[] rightLim){
        if (path.size() == n){
            res.add(new ArrayList<>(path));
            return;
        }
        int[] newLeftLim = getNewLeftLim(leftLim);
        int[] newRightLim = getNewRightLim(rightLim);
        int[] wholeLim = getWholeLim(colLim, newLeftLim, newRightLim);
        for (int i = 0; i < n; i ++){
            if (wholeLim[i] == 0){
                continue;
            }
            String str = getPathItem(n, i);

            path.add(str);
            colLim[i] = 0;
            newLeftLim[i] = 0;
            newRightLim[i] = 0;
            solveNQueensHelper(n, colLim, newLeftLim, newRightLim);
            colLim[i] = 1;
            newLeftLim[i] = 1;
            newRightLim[i] = 1;
            path.removeLast();
        }
    }
    public int[] getNewLeftLim(int[] leftLim){
        int len = leftLim.length;
        int[] newLeftLim = new int[len];
        for (int i = 0; i < len - 1; i++){
            newLeftLim[i] = leftLim[i + 1];
        }
        newLeftLim[len - 1] = 1;
        return newLeftLim;
    }
    public int[] getNewRightLim(int[] rightLim){
        int len = rightLim.length;
        int[] newRightLim = new int[len];
        for (int i = len - 1; i > 0; i--){
            newRightLim[i] = rightLim[i - 1];
        }
        newRightLim[0] = 1;
        return newRightLim;
    }
    public int[] getWholeLim(int[] colLim, int[] leftLim, int[] rightLim){
        int len = colLim.length;
        int[] wholeLim = new int[len];
        for (int i = 0; i < len; i++){
            wholeLim[i] = colLim[i] * leftLim[i] * rightLim[i];
        }
        return wholeLim;
    }
    public String getPathItem(int n, int i){
        char[] chars = new char[n];
        for (int j = 0; j < n; j++){
            if (j == i){
                chars[j] = 'Q';
            }else{
                chars[j] = '.';
            }
        }
        return new String(chars);
    }
}
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
77
78
79
80
81
82
83
84

框架板

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        if (n == 0){
            return res;
        }
        if (n == 1){
            path.add("Q");
            res.add(new ArrayList<>(path));
            return res;
        }
        int[] colLim = new int[n];
        int[] leftLim = new int[n];
        int[] rightLim = new int[n];
        Arrays.fill(colLim, 1);
        Arrays.fill(leftLim, 1);
        Arrays.fill(rightLim, 1);
        solveNQueensHelper(n, colLim, leftLim, rightLim);
        return res;
    }
    public void solveNQueensHelper(int n, int[] colLim, int[] leftLim, int[] rightLim){
        if (path.size() == n){
            res.add(new ArrayList<>(path));
            return;
        }
        int[] newLeftLim = getNewLeftLim(leftLim);
        int[] newRightLim = getNewRightLim(rightLim);
        int[] wholeLim = getWholeLim(colLim, newLeftLim, newRightLim);
        for (int i = 0; i < n; i ++){
            if (!isValid(wholeLim, i)){
                continue;
            }
            String str = getPathItem(n, i);

            path.add(str);
            colLim[i] = 0;
            newLeftLim[i] = 0;
            newRightLim[i] = 0;
            solveNQueensHelper(n, colLim, newLeftLim, newRightLim);
            colLim[i] = 1;
            newLeftLim[i] = 1;
            newRightLim[i] = 1;
            path.removeLast();
        }
    }
    public int[] getNewLeftLim(int[] leftLim){
        int len = leftLim.length;
        int[] newLeftLim = new int[len];
        for (int i = 0; i < len - 1; i++){
            newLeftLim[i] = leftLim[i + 1];
        }
        newLeftLim[len - 1] = 1;
        return newLeftLim;
    }
    public int[] getNewRightLim(int[] rightLim){
        int len = rightLim.length;
        int[] newRightLim = new int[len];
        for (int i = len - 1; i > 0; i--){
            newRightLim[i] = rightLim[i - 1];
        }
        newRightLim[0] = 1;
        return newRightLim;
    }
    public int[] getWholeLim(int[] colLim, int[] leftLim, int[] rightLim){
        int len = colLim.length;
        int[] wholeLim = new int[len];
        for (int i = 0; i < len; i++){
            wholeLim[i] = colLim[i] * leftLim[i] * rightLim[i];
        }
        return wholeLim;
    }
    public String getPathItem(int n, int i){
        char[] chars = new char[n];
        for (int j = 0; j < n; j++){
            if (j == i){
                chars[j] = 'Q';
            }else{
                chars[j] = '.';
            }
        }
        return new String(chars);
    }
    public boolean isValid(int[] wholeLim, int i){
        if (wholeLim[i] == 0){
            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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

方式二：二维字符数组表示棋盘

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }


    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(getPath(chessboard));
            return;
        }

        for (int col = 0; col < n; ++col) {
            if (!isValid(row, col, n, chessboard)) {
                continue;
            }
            chessboard[row][col] = 'Q';
            backTrack(n, row + 1, chessboard);
            chessboard[row][col] = '.';
        }

    }


    public List<String> getPath(char[][] chessboard) {
        List<String> path = new ArrayList<>();

        for (char[] c : chessboard) {
            path.add(new String(c));
        }
        return path;
    }


    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i = 0; i < row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                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
56
57
58
59
60
61
62
63
64
65

21.回溯算法：解数独

讲义地址

37. 解数独

leetcode地址

class Solution {
    boolean find = false;
    char[] set = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board, 0);
    }

    public void solveSudokuHelper(char[][] board, int count) {
        if (count == 81) {
            find = true;
            return;
        }

        int row = count / 9;
        int col = count % 9;

        if (board[row][col] == '.') {
            for (int i = 1; i < 10; i++) {
                if (find){
                    break;
                }
                if (!isValid(board, set[i], row, col)) {
                    continue;
                }
                board[row][col] = set[i];
                solveSudokuHelper(board, count + 1);
                if (!find) {
                    board[row][col] = '.';
                }
            }
        } else {
            solveSudokuHelper(board, count + 1);
        }
    }

    public boolean isValid(char[][] board, char c, int row, int col) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c || board[i][col] == c) {
                return false;
            }
        }
        int baseRow = (row / 3) * 3;
        int baseCol = (col / 3) * 3;
        for (int i = baseRow; i < baseRow + 3; i++) {
            for (int j = baseCol; j < baseCol + 3; j++) {
                if (board[i][j] == c) {
                    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

22.一篇总结带你彻底搞透回溯算法！

讲义地址

总结

class Solution{
	List<List<E>> res = new ArrayList<>();
	LinkedList<E> path = new LinkedList<>();
	StringBuilder path = new StringBuilder();
	public List<List<String>> backTracking(String... args){
		boolean[] used;
		backTrackingHelper(args);
		return res;
	}
	public void backTrackingHelper(String... args){
		if (终止){
			res.add(new ArrayList<>(path));
			return;
		}

		for (){
			if (!isValid(args){
				continue;
			}
			path.add();
			backTrackingHelper(args);
			path.removeLast();
		}
	}
	public boolean isValid(String... args){
		if (满足){
			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