经典回溯

发表于 | 分类于 ， ， |

N皇后问题、复原IP地址、解数独

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
49
class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        //'.'表示空，'Q'表示皇后，初始化空棋盘
        vector<string> board(n,string(n,'.'));
        backtrack(board,0);
        return res;
    }
    //路径：board中小于row的那些行都已经成功放置了皇后
    //选择列表：第row行的所有列都是放置皇后的选择
    //结束条件：row超过board的最后一行，说明棋盘放满了
    void backtrack(vector<string>& board, int row){
        //触发结束条件
        if(row==board.size()){
            res.push_back(board);
            return;
        }
        int n=board[row].size();
        for(int col=0; col<n;col++){
            //排除不合法选择
            if(!isValid(board, row, col)) continue;
            // 做选择
            board[row][col]='Q';
            //回溯 进行下一行决策
            backtrack(board, row+1);
            //撤销选择
            board[row][col]='.';
        }
    }
    //是否可以在board[row][col]放置皇后
    bool isValid(vector<string>& board, int row, int col){
        int n=board.size();
        //检查列中是否有皇后互相冲突
        for(int i=0;i<row;i++){
            if(board[i][col]=='Q') return false;
        }
        //检查右上方是否有皇后互相冲突
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(board[i][j]=='Q') return false;
        }
        //检查左上方是否有皇后冲突
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(board[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
func solveNQueens(n int) [][]string {
    var res [][]string
    //'.'表示空，'Q'表示皇后，初始化空棋盘
    board := make([]string, n)
    for i := 0; i < n; i++ {
        board[i] = strings.Repeat(".", n)
    }
    backtrack(&res, board, 0)
    return res
}

//路径：board中小于row的那些行都已经成功放置了皇后
//选择列表：第row行的所有列都是放置皇后的选择
//结束条件：row超过board的最后一行，说明棋盘放满了
func backtrack(res *[][]string, board []string, row int) {
    //触发结束条件
    if row == len(board) {
        temp := make([]string, len(board))
        copy(temp, board)
        *res = append(*res, temp)
        return
    }
    n := len(board[row])
    for col := 0; col < n; col++ {
        //排除不合法选择
        if !isValid(board, row, col) {
            continue
        }
        // 做选择
        board[row] = board[row][:col] + "Q" + board[row][col+1:]
        //回溯 进行下一行决策
        backtrack(res, board, row+1)
        //撤销选择
        board[row] = board[row][:col] + "." + board[row][col+1:]
    }
}

//是否可以在board[row][col]放置皇后
func isValid(board []string, row int, col int) bool {
    n := len(board)
    //检查列中是否有皇后互相冲突
    for i := 0; i < row; i++ {
        if board[i][col] == 'Q' {
            return false
        }
    }
    //检查右上方是否有皇后互相冲突
    for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
        if board[i][j] == 'Q' {
            return false
        }
    }
    //检查左上方是否有皇后冲突
    for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if board[i][j] == 'Q' {
            return false
        }
    }
    return true
}

93.复原IP地址

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 {
public:
    vector<string> res;
    string temp;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0);
        return res;
    }
    void dfs(string s, int cnt, int index){
        if(cnt==4 && index==s.size()){ // 片段满4段，且耗尽所有字符
            res.push_back(temp.substr(0, temp.size()-1));
            return;
        }
        for(int i=1;i<=3;i++){   // 只能存长度1~3的字符串
            if(index+i>s.size()) return;   //超出范围
            if(s[index]=='0' && i!=1) return;  //0x, 00x非法
            if(i==3 && s.substr(index, i)>"255") return;   //不能大于255

            //做选择
            temp += s.substr(index, i);
            temp.push_back('.');
            //回溯
            dfs(s, cnt+1, index+i);
            //撤销
            temp = temp.substr(0, temp.size()-i-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
func restoreIpAddresses(s string) []string {
    var res []string
    var temp string
    dfs(s, 0, 0, &temp, &res)
    return res
}

func dfs(s string, cnt int, index int, temp *string, res *[]string) {
    if cnt == 4 && index == len(s) { // 片段满4段，且耗尽所有字符
        *res = append(*res, (*temp)[:len(*temp)-1])
        return
    }
    for i := 1; i <= 3; i++ { // 只能存长度1~3的字符串
        if index+i > len(s) {
            return // 超出范围
        }
        if s[index] == '0' && i != 1 {
            return // 0x, 00x非法
        }
        if i == 3 && s[index:index+i] > "255" {
            return // 不能大于255
        }

        //做选择
        *temp += s[index : index+i]
        *temp += "."
        //回溯
        dfs(s, cnt+1, index+i, temp, res)
        //撤销
        *temp = (*temp)[:len(*temp)-i-1]
    }
}

37. 解数独

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:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0, 0);
    }
    bool dfs(vector<vector<char>>& board, int i, int j){
        int m=9;
        int n=9;
        if(i==m){
            return true;
        }
        if(j==n){
            return dfs(board, i+1, 0);   
        }
        if(board[i][j]!='.'){
            return dfs(board, i, j+1);
        }
        for(char ch='1';ch<='9';ch++){
            if(!isValid(board, i, j, ch)) continue;
            //做选择
            board[i][j] = ch;
            if(dfs(board, i, j+1)) return true;
            //撤销选择
            board[i][j] = '.';
        }
        return false;
    }
    bool isValid(vector<vector<char>>& board, int r, int c, char n){
        for(int i=0;i<9;i++){
            //判断行是否存在重复
            if(board[r][i] == n) return false;
            //判断列是否存在重复
            if(board[i][c] == n) return false;
            //判断3*3方框是否存在重复
            if(board[(r/3)*3+i/3][(c/3)*3+i%3]==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
37
38
39
40
41
42
43
44
45
46
47
48
func solveSudoku(board [][]byte) {
    dfs(board, 0, 0)
}

func dfs(board [][]byte, i int, j int) bool {
    m := 9
    n := 9
    if i == m {
        return true
    }
    if j == n {
        return dfs(board, i+1, 0)
    }
    if board[i][j] != '.' {
        return dfs(board, i, j+1)
    }
    for ch := byte('1'); ch <= '9'; ch++ {
        if !isValidSudoku(board, i, j, ch) {
            continue
        }
        //做选择
        board[i][j] = ch
        if dfs(board, i, j+1) {
            return true
        }
        //撤销选择
        board[i][j] = '.'
    }
    return false
}

func isValidSudoku(board [][]byte, r int, c int, n byte) bool {
    for i := 0; i < 9; i++ {
        //判断行是否存在重复
        if board[r][i] == n {
            return false
        }
        //判断列是否存在重复
        if board[i][c] == n {
            return false
        }
        //判断3*3方框是否存在重复
        if board[(r/3)*3+i/3][(c/3)*3+i%3] == n {
            return false
        }
    }
    return true
}
-------------本文结束 感谢阅读-------------
0%