Backtracking

Backtracking

93. 复原 IP 地址

解题思路：加“.”分割字符串

注意：isValid()中，如果得到的子串str为空，说明字符串s已经有三个“.”分割，并且最后一个点在最后一个位置，比如101.0.23.，

  1. s = s.substring(0, i + 1) + "." + s.substring(i + 1);得到字符串s = 101.0.23.
  2. ++pointNum;
  3. 进入下一轮backtracking(s, i + 2, pointNum); i + 2为.后面一位9
  4. 此时pointNum == 3，判断ip是否合法if (isValid(s, start, s.length() - 1))
  5. String str = s.substring(start, end + 1); 此时start为9，end + 1为9，String.subString左闭右开，所以得到的str为空
  6. 这种情况返回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
class Solution {

    List<String> res = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12)
            return res;
        backtracking(s, 0, 0);
        return res;
    }

    private void backtracking(String s, int start, int pointNum) {
        if (pointNum == 3) {
            if (isValid(s, start, s.length() - 1))
                res.add(s);
            return;
        }
        for (int i = start; i < s.length(); ++i) {
            if (isValid(s, start, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                ++pointNum;
                backtracking(s, i + 2, pointNum);
                --pointNum;
                s = s.substring(0, i + 1) + s.substring(i + 2); // 删除"."
            }
            else
                break;
        }
    }

    private boolean isValid(String s, int start, int end) {
        String str = s.substring(start, end + 1);
        if (str.isEmpty())
            return false;
        return Integer.valueOf(str) <= 255 && (str.equals("0") ||str.charAt(0) != '0');
    }
}

方法二：回溯(StringBuilder)

需要注意很多细节

  1. isValid

    1. 首先需要判断字符串是否为空;

    2. Integer.valueOf(s) <= 255的前提是以下else需要break，不然会超出整型最大值

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      for (int i = start; i < s.length(); ++i) {
          String str = s.substring(start, i + 1);
          if (isValid(str)) {
              path.append(str);
              path.append(".");
              backtracking(s, i + 1, split + 1);
              deleteSub();
          }
          else
              break;
      }

    3. 要么为0要么第一个字符不为0，s.equals("0") || s.charAt(0) != '0'

  2. 删除函数

    一般会做两次path.append操作，先append子串，再append .，所以删除操作先把.删除了，再删除上一个.之前的子串

    1
    2
    3
    4
    5
    private void deleteSub() {
        path.deleteCharAt(path.length() - 1);
        while (path.length() != 0 && path.charAt(path.length() - 1) != '.')
            path.deleteCharAt(path.length() - 1);
    }

    注意base case，如果剩余子串满足条件，那么会将子串append到path中，再加到res中，所以在此之后需要回溯一次，将新加入的子串删掉

    1
    2
    3
    4
    5
    6
    7
    8
    9
    if (split == 3) {
         String str = s.substring(start);
        if (isValid(str)) {
            path.append(str);
            res.add(path.toString());
            deleteSub();
        }
        return;
    }

代码

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
class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder path = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12)
            return res;
        backtracking(s, 0, 0);
        return res;
    }

    private void backtracking(String s, int start, int split) {
        if (split == 3) {
             String str = s.substring(start);
            if (isValid(str)) {
                path.append(str);
                res.add(path.toString());
                deleteSub();
            }
            return;
        }
        for (int i = start; i < s.length(); ++i) {
            String str = s.substring(start, i + 1);
            if (isValid(str)) {
                path.append(str);
                path.append(".");
                backtracking(s, i + 1, split + 1);
                deleteSub();
            }
            else
                break;
        }
    }

    private void deleteSub() {
        path.deleteCharAt(path.length() - 1);
        while (path.length() != 0 && path.charAt(path.length() - 1) != '.')
            path.deleteCharAt(path.length() - 1);
    }

    private boolean isValid(String s) {
        if (s.isEmpty())
            return false;
        return Integer.valueOf(s) <= 255 && (s.equals("0") || s.charAt(0) != '0');
    }
}

image-20230614114451417

方法三：StringBuilder + 剪枝

在方法二的基础上加入剪枝

s.length() - start表示未被选择的子串的长度，记为x吧，举例说明

如果split = 0，表示还没有进行分割，如果x > 12，一定不能满足条件，return；

如果split = 1，表示分割了一段，如果x > 9，一定不能满足条件，return；

1
2
if (s.length() - start > 3 * (4 - split))
    return;

代码

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
class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder path = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0, 0);
        return res;
    }

    private void backtracking(String s, int start, int split) {
        if (split == 3) {
             String str = s.substring(start);
            if (isValid(str)) {
                path.append(str);
                res.add(path.toString());
                deleteSub();
            }
            return;
        }
        if (s.length() - start > 3 * (4 - split))
            return;
        for (int i = start; i < s.length(); ++i) {
            String str = s.substring(start, i + 1);
            if (isValid(str)) {
                path.append(str);
                path.append(".");
                backtracking(s, i + 1, split + 1);
                deleteSub();
            }
            else
                break;
        }
    }

    private void deleteSub() {
        path.deleteCharAt(path.length() - 1);
        while (path.length() != 0 && path.charAt(path.length() - 1) != '.')
            path.deleteCharAt(path.length() - 1);
    }

    private boolean isValid(String s) {
        if (s.isEmpty())
            return false;
        return Integer.valueOf(s) <= 255 && (s.equals("0") || s.charAt(0) != '0');
    }
}

131. 分割回文串

方法一：回溯

二刷

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
class Solution {

    List<List<String>> res = new LinkedList<>();
    Deque<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return res;
    }

    private void backtracking(String s, int start) {
        if (start == s.length()) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i < s.length(); ++i) {
            String split = s.substring(start, i + 1);
            if (isValid(split)) {
                path.add(split);
                backtracking(s, i + 1);
                path.pollLast();
            }
        }

    }

    private boolean isValid(String split) {
        int start = 0, end = split.length() - 1;
        while (start < end) {
            if (split.charAt(start++) != split.charAt(end--))
                return false;
        }
        return true;
    }
}

方法二：回溯 + DP预处理

使用动态规划得到所有子串是否是回文

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false 这个状态转移方程是什么意思呢？

当只有一个字符时，比如 a 自然是一个回文串。 当有两个字符时，如果是相等的，比如 aa，也是一个回文串。 当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s[i]==s[j] 时，自然要看 dp[i+1][j-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
31
32
33
34
35
36
37
38
39
class Solution {
    public List<List<String>> partition(String s) {
        n = s.length();
        this.s = s;
        dp = new boolean[n][n];
        // dp[i][j] = ch1 == ch2 && (j - i + 1 <= 2) || dp[i + 1][j - 1]
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j) && (j - i + 1 <= 2 || dp[i + 1][j - 1]))
                    dp[i][j] = true;
            }
        }
        dfs(0);
        return res;
    }

    public void dfs(int index) {
        if (index == n) {
            res.add(new LinkedList(path));
            return;
        }
        for (int i = index; i < n; ++i) {
            String sub = s.substring(index, i + 1);
            if (dp[index][i]) {
                path.add(sub);
                dfs(i + 1);
                path.pollLast();
            }
        }
    }

    boolean[][] dp;

    List<List<String>> res = new LinkedList<>();
    Deque<String> path = new LinkedList<>();
    // StringBuilder sb = new StringBuilder();
    int n;
    String s;        
}

剑指 Offer II 085. 生成匹配的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<String> res = new LinkedList<>();
    public List<String> generateParenthesis(int n) {
        backtracking(n, n, "");
        return res;
    }

    private void backtracking(int leftNum, int rightNum, String parenthesis) {
        if (leftNum == 0 && rightNum == 0) {
            res.add(parenthesis);
            return;
        }
        if (leftNum > 0) {
            backtracking(leftNum - 1, rightNum, parenthesis + "(");
        }
        if (leftNum < rightNum) {
            backtracking(leftNum, rightNum - 1, parenthesis + ")");
        }
    }
}

方法二：StringBuilder

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
class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder path = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        backtracking(n, n);
        return res;
    }

    private void backtracking(int left, int right) {
        if (left == 0 && right == 0) {
            res.add(path.toString());
            return;
        }
        if (left > 0) {
            path.append("(");
            backtracking(left - 1, right);
            path.deleteCharAt(path.length() - 1);
        }
        if (left < right) {
            path.append(")");
            backtracking(left, right - 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

77. 组合

方法一：

剪枝：

  1. 当前最多用n - i + 1
  2. 当前还需要加入k - path.size()个数组

n - i + 1 >= k - path.size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }

    private void backtracking(int n, int k, int start) {
        if (path.size() == k) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
            path.add(i);
            backtracking(n, k, i + 1);
            path.pollLast();
        }
    }
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        // 防止底层扩容
        Deque<Integer> path = new ArrayDeque<>(k);
        backtracking(path, n, k, 1);
        return res;
    }
    private void backtracking(Deque<Integer> path, int n, int k, int start) {
        if (k == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        // 若n=3，k=2,即从[1,2,3]中选两个数，如果当前什么都没选(k=2)，n - k + 1= 2，
        // 说明至少要从2开始，才能满足选两个数这个要求
        int bound = n - k + 1;
        if (start > bound)
            return;
        backtracking(path, n, k, start + 1);
        path.addLast(start);
        backtracking(path, n, k - 1, start + 1);
        path.removeLast();
    }
}

两种方法的树形结构（求子集为例子）

216. 组合总和 III

方法一：

注意：backtracking(k - 1, n - i, i + 1);k - 1，别写成--k!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return res;
    }

    private void backtracking(int k, int n, int start) {
        if (k == 0) {
            if (n == 0)
                res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i <= 9 - (k - path.size()) + 1; ++i) {
            path.offerLast(i);
            backtracking(k - 1, n - i, i + 1);
            path.pollLast();
        }
    }

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return res;
    }

    private void backtracking(int k, int n, int start) {
        if (k == 0) {
            if (n == 0)
                res.add(new LinkedList<>(path));
            return;
        }
       int bound = 9 - k + 1;
        if (start > bound)
            return;
        backtracking(k, n, start + 1);
        path.offerLast(start);
        backtracking(k - 1, n - start, start + 1);
        path.pollLast();
    }
}

39. 组合总和

无重复元素，每个元素可以无限次选取

方法一：

剪枝：

1
2
if (target < candidates[i])
   break;

可重复选取，所以backtracking传入的是当前下标i

1
backtracking(candidates, target - candidates[i], i);

剪枝的条件是把数组排序

1
Arrays.sort(candidates);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<List<Integer>> res = new LinkedList<>();
Deque<Integer> path = new LinkedList<>();

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    backtracking(candidates, target, 0);
    return res;
}

private void backtracking(int[] candidates, int target, int start) {
    if (target < 0)
        return;
    if (target == 0) {
        res.add(new LinkedList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; ++i) {
        if (target < candidates[i])
            break;
        path.offerLast(candidates[i]);
        backtracking(candidates, target - candidates[i], i);
        path.pollLast();
    }
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, int start) {
        if (target < 0 || start == candidates.length)
            return;
        if (target == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        backtracking(candidates, target, start + 1);
        path.offerLast(candidates[start]);
        backtracking(candidates, target - candidates[start], start);
        path.pollLast();
    }
}

40. 组合总和 II

数组内有重复元素，每个元素只能使用一次，解集不能包含重复组合

方法一：

剪枝

1
2
if (candidates[i] > target)
    break;

去重

1
2
if (i > start && candidates[i] == candidates[i - 1])
    continue;
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 LinkedList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, int start) {
        if (target == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            if (candidates[i] > target)
                break;
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            path.offerLast(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            path.pollLast();
        }
    }
}

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return res;
    }

    private void backtracking(int[] nums, int start) {
        if (start == nums.length) {
            res.add(new LinkedList<>(path));
            return;
        }
        backtracking(nums, start + 1);
        path.offerLast(nums[start]);
        backtracking(nums, start + 1);
        path.pollLast();
    }
}

491. 递增子序列

方法一：顺序DFS

注意：

  1. HashSet的位置！！！每进入一层递归，就会在for循环前创建一个HashSet，这样可以保证树层去重，并且树枝不会去重
  2. peekLast()! 不是peek()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0);
        return res;
    }
    public void backtracking(int[] nums, int start) {
        if (path.size() >= 2)
            res.add(new LinkedList(path));
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; ++i) {
            if ((!path.isEmpty() && nums[i] < path.peekLast()))
                continue;
            if (set.contains(nums[i]))
                continue;
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.pollLast();
        }
    }
}

46. 全排列

把树形结构画出来就懂了

for (int i = 0; i < nums.length; ++i) { if (used[i]) continue;与 for (int i = 0; i < nums.length && !used[i]; ++i) 的区别

这两个循环的区别在于循环终止条件的判断逻辑。

  1. 第一个循环： 

    1
    2
    3
    4
    5
    for (int i = 0; i < nums.length; ++i) {
        if (used[i])
            continue;
        // 其他代码逻辑
    }
    这个循环会遍历数组 nums 的所有元素，但在每次迭代中，如果当前元素已经被标记为 used[i]，则会使用 continue 跳过后续的代码逻辑，直接进入下一次迭代。

  2. 第二个循环： 

    1
    2
    3
    for (int i = 0; i < nums.length && !used[i]; ++i) {
        // 其他代码逻辑
    }
    这个循环同样会遍历数组 nums 的所有元素，但在每次迭代中，会先检查终止条件 i < nums.length && !used[i]。只有当两个条件都满足时，才会执行循环体中的代码逻辑。如果其中任何一个条件不满足，循环就会终止。

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
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path;
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        // 防止底层扩容
        path = new ArrayDeque<>(nums.length);
        used = new boolean[nums.length];
        backtracking(nums, 0);
        return res;
    }

    private void backtracking(int[] nums, int start) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (used[i])
                continue;
            path.offerLast(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1);
            used[i] = false;
            path.pollLast();
        }
    }
}

47. 全排列 II

  1. 为了去重，需要先将数组排序
  2. 树层去重，树枝不需要去重
  3. 上一个相同的数如果used[i - 1] == false，那么说明已经被遍历过，并且将used数组赋值回false，这个时候就不需要遍历当前nums[i]了；如果used[i - 1] == true，那么说明是在同一路径上
1
2
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
               continue;
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
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path;
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 防止底层扩容
        path = new ArrayDeque<>(nums.length);
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(nums, 0);
        return res;
    }

    private void backtracking(int[] nums, int start) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (used[i])
                continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
                continue;
            path.offerLast(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1);
            used[i] = false;
            path.pollLast();
        }
    }
}

698. 划分为k个相等的子集

二刷没做出，三刷ac

优质题解

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
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    int[] bucket;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0)
            return false;
        int target = sum / k;
        bucket = new int[k];
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            ++l;
            --r;
        }
        return backtracking(nums, k, target, 0);
    }

    private boolean backtracking(int[] nums, int k, int target, int index) {
        if (index == nums.length)
            return true;
        for (int i = 0; i < k; ++i) {
            if (i > 0 && bucket[i - 1] == bucket[i])
                continue;
            if (nums[index] + bucket[i] > target)
                continue;
            bucket[i] += nums[index];
            if (backtracking(nums, k, target, index + 1))
                return true;
            bucket[i] -= nums[index];
        }
        return false;
    }

}

51. N 皇后

方法一：回溯

可以通过(c == colum[i] || r + c == i + colum[i] || r - c == i - colum[i])来判断是否同列，同对角线

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
class Solution {
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        colum = new int[n]; // 第i行选择的列号
        dfs(0);
        return res;
    }

    public void dfs(int index) {
        if (index == n) { // index是行
            res.add(build());
            return;
        }
        for (int i = 0; i < n; ++i) { // i是列
            if (isValid(index, i)) {
                colum[index] = i;
                dfs(index + 1);
            }
        }
    }

    public boolean isValid(int r, int c) {
        for (int i = 0; i < r; ++i) {
            if (c == colum[i] || r + c == i + colum[i] || r - c == i - colum[i])
                return false;
        }
        return true;
    }

    public List<String> build() {
        List<String> s = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int x : colum) {
            for (int i = 0; i < x; ++i)
                sb.append('.');
            sb.append('Q');
            for (int i = 0; i < n - x - 1; ++i)
                sb.append('.');
            s.add(sb.toString());
            sb = new StringBuilder();
        }
        return s;
    }

    List<List<String>> res = new ArrayList<>();
    Deque<String> path = new LinkedList<>();
    int[] colum;
    int n;

    
}

473. 火柴拼正方形

与698. 划分为k个相等的子集一道题

方法一：回溯

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 LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    int[] bucket = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = Arrays.stream(matchsticks).sum();
        if (sum % 4 != 0)
            return false;
        int target = sum / 4, l = 0, r = matchsticks.length - 1;
        Arrays.sort(matchsticks);
        while (l < r) {
            int temp = matchsticks[l];
            matchsticks[l] = matchsticks[r];
            matchsticks[r] = temp;
            ++l;
            --r;
        }
        return backtracking(matchsticks, 0, target);
    }

    private boolean backtracking(int[] matchsticks, int index, int target) {
        if (index == matchsticks.length)
            return true;
        for (int i = 0; i < 4; ++i) {
            if (i > 0 && bucket[i - 1] == bucket[i])
                continue;
            if (matchsticks[index] + bucket[i] > target)
                continue;
            bucket[i] += matchsticks[index];
            if (backtracking(matchsticks, index + 1, target))
                return true;
            bucket[i] -= matchsticks[index];
        }
        return false;
    }
}

2305. 公平分发饼干

参考题解

这一题和分割数组的最大值的区别是，这里的cookies不需要连续取！！！！！

方法一：回溯

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
class Solution {
    int res = Integer.MAX_VALUE;
    int[] bucket;
    public int distributeCookies(int[] cookies, int k) {
        Arrays.sort(cookies);
        bucket = new int[k];
        backtracking(cookies, k, 0);
        return res;
    }

    private void backtracking(int[] cookies, int k, int index) {
        if (index == cookies.length) {
            int curAns = Integer.MIN_VALUE;
            for (int count : bucket){
                curAns = Math.max(curAns, count);
            }
            res = Math.min(res, curAns);
            return;
        }
        for (int i = 0; i < k; ++i) {
            if (i > 0 && bucket[i - 1] == bucket[i])
                continue;
            bucket[i] += cookies[index];
            backtracking(cookies, k, index + 1);
            bucket[i] -= cookies[index];
        }
    }
}

方法二：回溯 + 二分

求最小的最大值

  1. 用k个框(bucket)装一个数组，所有框统一尺寸，要求框的最小尺寸

  2. left是数组的最大元素，right是数组元素之和，如果把框的尺寸设为left，那么大概率不能容纳所有数组元素：

    left = mid + 1；如果把框的尺寸设为right，肯定能装下数组所有元素：right = mid - 1

  3. 只要check(cookies, mid, k)为true，说明mid刚刚好或者选大了，框的上界可以进一步缩小，

    当最后一次满足check(cookies, mid, k)为true并向左滑动右区间，之后只会向右滑动左区间，

    最后left = right + 1退出while循环，left就是最小的最大值

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
class Solution {
    int[] bucket;
    public int distributeCookies(int[] cookies, int k) {
        bucket = new int[k];
        Arrays.sort(cookies);
        int l = 0, r = cookies.length - 1, sum = 0;
        while (l < r) {
            int temp = cookies[l];
            cookies[l] = cookies[r];
            cookies[r] = temp;
            sum += temp + cookies[l];
            ++l;
            --r;
        }
        if (cookies.length % 2 != 0)
            sum += cookies[cookies.length / 2];
        l = cookies[0]; // 数组最大值
        r = sum;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(cookies, mid, k)) // mid刚刚好或者选大了，bucket的上界可以进一步缩小
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int[] cookies, int mid, int k) {
        bucket = new int[k];
        return backtracking(cookies, mid, k, 0);
    }

    private boolean backtracking(int[] cookies, int limit, int k, int index) {
        if (index == cookies.length)
            return true; // 如果能遍历到这一步，说明所有元素都被装入桶中;如果有元素不能放入任意一个桶中，会走完for循环，return false
        for (int i = 0; i < k; ++i) {
            if (i > 0 && bucket[i - 1] == bucket[i]) // 如果两个桶已装容量一致，那么把当前饼干放在哪个桶效果都一样
                continue;
            if (bucket[i] + cookies[index] > limit)
                continue;
            bucket[i] += cookies[index];
            if (backtracking(cookies, limit, k, index + 1))
                return true; // 如果有一种选择已经满足了，return true
            bucket[i] -= cookies[index];
        }
        return false;
    }
}

1723. 完成所有工作的最短时间

与2305. 公平分发饼干一模一样

方法一：二分 + 回溯

这里的二分和之前做的二分不太一样

  1. 要求最小的最大值，我们用二分去测试，如果允许每个bucket的最大值为mid，是否能用k个bucket容纳下jobs的所有元素
  2. l取jobs中最大的元素，r取jobs的和sum，比如每个bucket的最大值为sum，那么一个bucket就能容纳下jobs的所有元素，那么肯定是要取更小的bucket的最大值
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
class Solution {
    int[] bucket;
    public int minimumTimeRequired(int[] jobs, int k) {
        bucket = new int[k];
        Arrays.sort(jobs);
        int l = 0, r = jobs.length - 1;
        while (l < r) {
            int temp = jobs[l];
            jobs[l] = jobs[r];
            jobs[r] = temp;
            ++l;
            --r;
        }
        l = jobs[0];
        r = Arrays.stream(jobs).sum();
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(jobs, mid, k)) // mid刚好或者选大了
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int[] jobs, int limit, int k) {
        bucket = new int[k];
        return backtracking(jobs, limit, k, 0);
    }


    private boolean backtracking(int[] jobs, int limit, int k, int index) {
        if (index == jobs.length)
            return true;
        for (int i = 0; i < k; ++i) {
            if (i > 0 && bucket[i - 1] == bucket[i])
                continue;
            if (jobs[index] + bucket[i] > limit)
                continue;
            bucket[i] += jobs[index];
            if (backtracking(jobs, limit, k, index + 1))
                return true;
            bucket[i] -= jobs[index];
        }
        return false;
    }
}

优化求sum部分

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
class Solution {
    int[] bucket;
    public int minimumTimeRequired(int[] jobs, int k) {
        bucket = new int[k];
        Arrays.sort(jobs);
        int l = 0, r = jobs.length - 1, sum = 0;
        while (l < r) {
            int temp = jobs[l];
            jobs[l] = jobs[r];
            jobs[r] = temp;
            sum += temp + jobs[l];
            ++l;
            --r;
        }
        if (jobs.length % 2 != 0)
            sum += jobs[jobs.length / 2];
        l = jobs[0]; // 数组最大值
        r = sum;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(jobs, mid, k)) // mid刚好或者选大了
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int[] jobs, int limit, int k) {
        bucket = new int[k];
        return backtracking(jobs, limit, k, 0);
    }


    private boolean backtracking(int[] jobs, int limit, int k, int index) {
        if (index == jobs.length)
            return true;
        for (int i = 0; i < k; ++i) {
            if (i > 0 && bucket[i - 1] == bucket[i])
                continue;
            if (jobs[index] + bucket[i] > limit)
                continue;
            bucket[i] += jobs[index];
            if (backtracking(jobs, limit, k, index + 1))
                return true;
            bucket[i] -= jobs[index];
        }
        return false;
    }
}

二刷

省略check，每次在dfs前重新初始化bucket数组

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
public int minimumTimeRequired(int[] jobs, int k) {
    bucket = new int[k];
    Arrays.sort(jobs);
    int l = 0, r = jobs.length - 1, sum = 0;
    while (l < r) {
        int temp = jobs[l];
        jobs[l] = jobs[r];
        jobs[r] = temp;
        sum += temp + jobs[l];
        ++l;
        --r;
    }
    if (jobs.length % 2 == 1)
        sum += jobs[jobs.length / 2];
    l = jobs[0];
    r = sum;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (dfs(jobs, k, mid, 0))
            r = mid - 1;
        else
            l = mid + 1;
    }
    return l;
}


int[] bucket;

private boolean dfs(int[] jobs, int k, int target, int index) {
    if (index == jobs.length) {
       bucket = new int[k];
       return true;
    }
    for (int i = 0; i < k; ++i) {
        if (i > 0 && bucket[i - 1] == bucket[i])
            continue;
        if (bucket[i] + jobs[index] > target)
            continue;
        bucket[i] += jobs[index];
        if (dfs(jobs, k, target,index + 1))
            return true;
        bucket[i] -= jobs[index];
    }
    return false;
}

Algorithms > backtracking
#回溯
Backtracking
https://leopol1d.github.io/2023/05/20/backtracking/
作者
Leopold
发布于
2023年5月20日
许可协议