IVN
0%

回溯法(2)

Posted on Edited on In
Symbols count in article: 12k Reading time ≈ 11 mins.

backtracking经典题选编(2)

51. N-Queens

思路：

  1. 从上往下，一行一行填
  2. 某一行元素逐个判断，valid则填入并继续探索下一行（，否则跳过，直接探索该行下一个元素）
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
import java.util.ArrayList;
import java.util.List;

public class LeetCode51 {
    List<List<String>> res;
    public List<List<String>> solveNQueens(int n) {
        this.res=new ArrayList<>();
        char[][] board=new char[n][n];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j]='.';
            }
        }
        backtracking(board,n,0);
        return this.res;
    }

    List<String> toList(char[][] board){
        List<String> list=new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            StringBuilder sb=new StringBuilder();
            for (int j = 0; j < board[0].length; j++) {
                sb.append(board[i][j]);
            }
            list.add(sb.toString());
        }
        return list;
    }

    void backtracking(char[][] board,int n, int row){
        if(row==n){
            List<String> list=toList(board);
            this.res.add(new ArrayList<>(list));
            return;
        }


        for (int i = 0; i < n; i++) {
            if(valid(board,n,row,i)){
                board[row][i]='Q';
                backtracking(board,n,row+1);
                board[row][i]='.';
            }
        }
    }

    boolean valid(char[][] board,int n,int row,int col){
        //从上往下填的，只需考察上方元素，下方都是空
        //正上方不能有Q
        for (int i = 0; i < row; i++) {
            if(board[i][col]=='Q'){
                return false;
            }
        }
        //左上不能有Q
        int r=row-1;
        int c=col-1;
        while(r>=0 && c>=0){
            if(board[r][c]=='Q'){
                return false;
            }
            r--;
            c--;
        }
        //右上不能有Q
        r=row-1;
        c=col+1;
        while(r>=0 && c<n){
            if(board[r][c]=='Q'){
                return false;
            }
            r--;
            c++;
        }
        return true;
    }
}

131. Palindrome Partitioning

本题难点：

  • 切割问题可以抽象为组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文
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
List<List<String>> res;
public List<List<String>> partition(String s) {
    this.res=new ArrayList<>();
    backtracking(new ArrayList<>(),s,0);
    return this.res;
}

boolean isPalindrome(String s, int start, int end){
    while(start<end){
        if(s.charAt(start)!=s.charAt(end)){
            return false;
        }
        start++;
        end--;
    }
    return true;
}

void backtracking(List<String> list,String s,int start){
    if(start>=s.length()){
        this.res.add(new ArrayList<>(list));
        return;
    }
    for (int i = start; i < s.length(); i++) {
        if(isPalindrome(s,start,i)){
            list.add(s.substring(start,i+1)); //s[start,i]加进去了
            backtracking(list,s,i+1); //继续探索s[i+1,length-1]
            list.remove(list.size()-1);
        }
    }
}

93. Restore IP Addresses

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
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> res=new ArrayList<>();
        backtracking(res,new LinkedList<>(),s,3,0);
        return res;
    }

    boolean isValid(String s, int start, int end){
        if(start<end && s.charAt(start)=='0' || end-start>=3){
            return false;
        }
        int sum=0;
        int digit=1;
        while(start<=end){
            sum+=(s.charAt(end)-'0')*digit;
            digit*=10;
            end--;
        }
        return sum<=255 ? true : false; //注意int溢出 2147483647
    }

    void backtracking(List<String> res, LinkedList<String> list, String s, int dot, int start){
        if(start>=s.length()){
            return;
        }
        if(dot==0){
            if(isValid(s,start,s.length()-1)){
                StringBuilder sb=new StringBuilder();
                for (String s1 : list) {
                    sb.append(s1);
                }
                sb.append(s.substring(start,s.length()));
                res.add(new String(sb));
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if(isValid(s,start,i)){
                list.add(s.substring(start,i+1));
                list.add(".");
                backtracking(res,list,s,dot-1,i+1);
                list.removeLast();
                list.removeLast();
            }
        }
    }
}

37. Sudoku Solver

思考：为什么这种void写法不行，一定要将helper设为boolean

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//wrong answer!
void backtracking(char[][] board,int row,int col,int index){
    if(index>=row*col){
        return;
    }
    int i=index/row;
    int j=index%row;
    if(board[i][j]!='.'){
        backtracking(board,row,col,index+1);
    }else{
        for (char c = '1'; c <= '9'; c++) {
            if(valid(board,c,i,j)){
                board[i][j]=c;
                backtracking(board,row,col,index+1);
                board[i][j]='.';
            }
        }
    }
}
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
public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board){
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){
                        board[i][j] = k;
                        if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }

491. Increasing Subsequences

注意去重逻辑：不能对原数组排序，所以排序+visited数组老方法不行！

不仅是和该元素前一个相比较，而是和该元素之前的全部元素相比较

新去重思路：在每一层开一个map，每一层的相同元素只有第一个元素保留，其余都剪枝

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
public List<List<Integer>> findSubsequences(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    backtracking(res,new LinkedList<>(),nums,0);
    return res;
}

void backtracking(List<List<Integer>> res, LinkedList<Integer> list, int[] nums,int start ){
    if(start>=nums.length){
        return;
    }
    Map<Integer,Integer> map=new HashMap<>();
    for (int i = start; i < nums.length; i++) {
        if(!list.isEmpty() && list.getLast()>nums[i]){
            continue;
        }
        if(map.getOrDefault(nums[i],0)>=1){
            continue;
        }
        list.add(nums[i]);
        map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        if(list.size()>=2){
            res.add(new LinkedList<>(list));
        }
        backtracking(res,list,nums,i+1);
        list.removeLast();
    }
}

优化思路：由于元素范围有限，可用数组代替map

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
public class LeetCode491 {
    List<List<Integer>> res;
    LinkedList<Integer> list;
    public List<List<Integer>> findSubsequences(int[] nums) {
        res=new ArrayList<>();
        list=new LinkedList<>();
        backtracking(nums,0);
        return res;
    }

    void backtracking(int[] nums,  int start){
        if(list.size()>=2){
            res.add(new LinkedList<>(list));
        }
        if(start==nums.length){
            return;
        }
        boolean[] visited=new boolean[201];
        for (int i = start; i < nums.length; i++) {
            if(visited[nums[i]+100]){
                continue;
            }
            if(list.size()==0 || nums[i]>=list.getLast()){
                list.add(nums[i]);
                visited[nums[i]+100]=true;
                backtracking(nums,i+1);
                list.removeLast();
                //注意，某一个值visited过了，就一直标记，这一层再也不选用
            }
        }
    }
}

332. Reconstruct Itinerary

You must use all the tickets once and only once.

list.get(0)=”JFK” 起点给定

回溯终止条件：所有票都used， 即 list.length==tickets.length+1

哪些票valid: used==false && 起点.equals(list.getLast())

结果itineray不止一条：取字典序最小的一条

超时的笨方法：

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
List<String> res;
public List<String> findItinerary(List<List<String>> tickets) {
    this.res=new ArrayList<>();
    List<String> list=new ArrayList<>();
    backtracking(list,tickets,new boolean[tickets.size()]);
    return res;
}

void backtracking( List<String> list, List<List<String>> tickets, boolean[] used){
    if(list.size()==tickets.size()+1){
        if(res.size()==0 || better(list,res)){
            res=new ArrayList<>(list);
        }
        return;
    }
    if(list.size()==0){
        for (int i = 0; i < tickets.size(); i++) {
            if(tickets.get(i).get(0).equals("JFK")){
                list.add("JFK");
                list.add(tickets.get(i).get(1));
                used[i]=true;
                backtracking(list,tickets,used);
                list.remove(list.size()-1);
                list.remove(list.size()-1);
                used[i]=false;
            }
        }
    }else{
        for (int i = 0; i < used.length; i++) {
            if(used[i]){
                continue;
            }
            String last=list.get(list.size()-1);
            if(tickets.get(i).get(0).equals(last)){
                list.add(tickets.get(i).get(1));
                used[i]=true;
                backtracking(list,tickets,used);
                list.remove(list.size()-1);
                used[i]=false;
            }
        }
    }


}

boolean better(List<String> l1,List<String> l2){
    StringBuilder sb1=new StringBuilder();
    StringBuilder sb2=new StringBuilder();
    for (String s : l1) {
        sb1.append(s);
    }
    for (String s : l2) {
        sb2.append(s);
    }
    if(sb1.toString().compareTo(sb2.toString())<0){
        return true;
    }else{
        return false;
    }
}

笨方法不行，考虑先排序，再backtracking, 保证“小”票先被used

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
List<String> res;
boolean found;
public List<String> findItinerary(List<List<String>> tickets) {
    tickets.sort(new Comparator<List<String>>() {
        @Override
        public int compare(List<String> o1, List<String> o2) {
            return !o1.get(0).equals(o2.get(0)) ? o1.get(0).compareTo(o2.get(0)) : o1.get(1).compareTo(o2.get(1));
        }
    });
    this.res=new ArrayList<>();
    List<String> list=new ArrayList<>();
    backtracking(list,tickets,new boolean[tickets.size()]);
    return res;
}

void backtracking( List<String> list, List<List<String>> tickets, boolean[] used){
    if(list.size()==tickets.size()+1){
        res=new ArrayList<>(list);
        found=true;
        return;
    }
    if(list.size()==0){
        for (int i = 0; i < tickets.size(); i++) {
            if(tickets.get(i).get(0).equals("JFK")){
                list.add("JFK");
                list.add(tickets.get(i).get(1));
                used[i]=true;
                backtracking(list,tickets,used);
                list.remove(list.size()-1);
                list.remove(list.size()-1);
                used[i]=false;
            }
        }
    }else{
        for (int i = 0; i < used.length; i++) {
            if(found){
                break;
            }
            if(used[i]){
                continue;
            }
            String last=list.get(list.size()-1);
            if(tickets.get(i).get(0).equals(last)){
                list.add(tickets.get(i).get(1));
                used[i]=true;
                backtracking(list,tickets,used);
                list.remove(list.size()-1);
                used[i]=false;
            }
        }
    }
}

320. Generalized Abbreviation

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
List<String> res=new ArrayList<>();
Set<String> set=new HashSet<>();
LinkedList<String> list=new LinkedList<>();
public List<String> generateAbbreviations(String word) {
    backtracking(word,0);
    return res;
}

void backtracking(String word, int start){
    if(start==word.length()){
        StringBuilder sb=new StringBuilder();
        for (String s : list) {
            sb.append(s);
        }
        String s=sb.toString();
        if(!set.contains(s)){
            set.add(s);
            res.add(s);
        }
        return;
    }
    //word[start,i]
    boolean avoid=false;
    if(!list.isEmpty()){
        String last=list.getLast();
        if(Character.isDigit(last.charAt(0))){
            avoid=true;
        }
    }
    for (int i = start; i < word.length(); i++) {
        String sub=word.substring(start,i+1);
        list.add(sub);
        backtracking(word,i+1);
        list.removeLast();
        if(!avoid){
            int len=sub.length();
            list.add(Integer.toString(len));
            backtracking(word,i+1);
            list.removeLast();
        }
    }
}

254. Factor Combinations

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;
List<Integer> list;
public List<List<Integer>> getFactors(int n) {
    res=new ArrayList<>();
    list=new ArrayList<>();
    backtracking(n,2);
    return res;
}

void backtracking(int cur, int start){
    if(cur==1){
        if(list.size()>1){
            res.add(new ArrayList<>(list));
        }
        return;
    }
    for (int i = start; i <= cur; i++) {
        if(cur%i==0) {
            list.add(i);
            backtracking(cur / i, i);
            list.remove(list.size() - 1);
        }
    }
}