LeetCode题解--回溯算法(四)

本是古典何须时尚 2023-06-23 04:53 27阅读 0赞

### 文章目录 ###

*   *  131. 分割回文串
     *   *  回溯算法
     *  37. 解数独
     *   *  回溯算法
     *  51. N皇后
     *   *  回溯算法

## 131. 分割回文串 ##

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: “aab”  
输出:  
\[  
\[“aa”,“b”\],  
\[“a”,“a”,“b”\]  
\]

### 回溯算法 ###

class Solution {
        
        private boolean checkPalindrome(String s, int begin, int end) {
        
            while (begin < end) {
        
                if (s.charAt(begin++) != s.charAt(end--)) {
        
                    return false;
                }
            }
            return true;
        }
        private void backtracking(String s, List<List<String>> result, List<String> temp) {
        
            if (s.length() == 0) {
        
                result.add(new ArrayList<>(temp));
                return;
            }
            for (int i = 0; i < s.length(); ++i) {
        
                if (checkPalindrome(s, 0, i)) {
        
                    temp.add(s.substring(0, i + 1));
                    backtracking(s.substring(i + 1), result, temp);
                    temp.remove(temp.size() - 1);
                }
            }
        }
        public List<List<String>> partition(String s) {
        
            List<List<String>> result = new ArrayList<>();
            backtracking(s, result, new ArrayList<>());
            return result;
        }
    }

## 37. 解数独 ##

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。  
数字 1-9 在每一列只能出现一次。  
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。  
空白格用 ‘.’ 表示。  
![format_png][]  
Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。  
你可以假设给定的数独只有唯一解。  
给定数独永远是 9x9 形式的。

### 回溯算法 ###

详细题解见[https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/][https_leetcode-cn.com_problems_sudoku-solver_solution_jie-shu-du-by-leetcode]

class Solution {
        
        private int n = 3;
        private int N = n * n;
        private int[][] rows = new int[N][N+1];
        private int[][] cols = new int[N][N+1];
        private int[][] boxes = new int[N][N+1];
        private char[][] board;
        private boolean solved = false;
        private boolean checkPlace(int d, int row, int col) {
        
            int index = (row / n) * n + col / n;
            return rows[row][d] + cols[col][d] + boxes[index][d] == 0;
        }
        private void placeNumber(int d, int row, int col) {
        
            int index = (row / n) * n + col / n;
            rows[row][d]++;
            cols[col][d]++;
            boxes[index][d]++;
            board[row][col] = (char)(d + '0');
        }
        private void removeNumber(int d, int row, int col) {
        
            int index = (row / n) * n + col / n;
            rows[row][d]--;
            cols[col][d]--;
            boxes[index][d]--;
            board[row][col] = '.';
        }
        private void placeNextNumber(int row, int col) {
        
            if (row == N - 1 && col == N - 1) {
        
                solved = true;
            } else {
        
                if (col == N - 1) {
        
                    backtrack(row + 1, 0);
                } else {
        
                    backtrack(row, col + 1);
                }
            }
        }
        private void backtrack(int row, int col) {
        
            if (board[row][col] == '.') {
        
                for (int d = 1; d <= N; d++) {
        
                    if (checkPlace(d, row, col)) {
        
                        placeNumber(d, row, col);
                        placeNextNumber(row, col);
                        if (!solved) {
        
                            removeNumber(d, row, col);
                        }
                    }
                }
            } else {
        
                placeNextNumber(row, col);
            }
        }
        public void solveSudoku(char[][] board) {
        
            this.board = board;
            for (int i = 0; i < N; ++i) {
        
                for (int j = 0; j < N; ++j) {
        
                    char num = board[i][j];
                    if (num != '.') {
        
                        int d = Character.getNumericValue(num);
                        placeNumber(d, i, j);
                    }
                } 
            }
            backtrack(0, 0);
        }
    }

还有一种效率更高的方法，选择的格子（’.’）在一行、一列和一个九宫格中可选数字最少的格子开始填数字。这样能更快找到结果。

剪枝条件:我们应该选择的格子（'.'）在一行、一列和一个九宫格中可选数字最少的格子开始填数字。
    
    对于每行、每列和每个9宫格都可以用一个9位的2进制数字来标识该行（列，9宫格）那些数字可以填。
        用1表示可填0表示不可填
        如例题中第一行 ：["5","3",".",".","7",".",".",".","."]
        第一行中 有数字 5 3 7
                        下标    8  7  6  5  4  3  2  1  0
                    二进制数    1  1  0  1  0  1  0  1  1
        因为5 3 7 已经有了，所以第一行1 2 4 6 8 9可填
        一共有9行所以用9个int表示行row[9],同理9列col[9],9个9宫格cell[3][3]
    
    class Solution {
        
        final int N = 9;
        int[] row = new int [N], col = new int [N];
        //ones数组表示0~2^9 - 1的整数中二进制表示中1的个数:如ones[7] = 3 ones[8] = 1
        //map数组表示2的整数次幂中二进制1所在位置（从0开始） 如 map[1] = 0,map[2] = 1, map[4] = 2
        int[] ones = new int[1 << N], map = new int[1 << N];
        int[][] cell = new int[3][3]; 
        public void solveSudoku(char[][] board) {
        
            init();
            int cnt = fill_state(board);
            dfs(cnt, board);
        }
        void init(){
        
            for(int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1; 
            for(int i = 0; i < 3; i++)
                for(int j = 0; j < 3; j++)
                    cell[i][j] = (1 << N) - 1;
            //以上2个循环把数组的数初始化为二进制表示8个1，即一开始所以格子都可填
            for(int i = 0; i < N; i++) map[1 << i] = i;
            //统计0~2^9 - 1的整数中二进制表示中1的个数
            for(int i = 0; i < 1 << N; i++){
        
                int n = 0;
                for(int j = i; j != 0; j ^= lowBit(j)) n++;
                ones[i] = n;
            }
        }
        int fill_state(char[][] board){
        
            int cnt = 0;    //统计board数组空格('.')的个数
            for(int i = 0; i < N; i++){
        
                for(int j = 0; j < N; j++){
        
                    if(board[i][j] != '.'){
        
                        int t = board[i][j] - '1';
                        //数独中 i,j位置为数组下标，修改row col cell数组中状态
                        change_state(i, j, t);  
                    }else cnt++;
                }
            }
            return cnt;
        }
        boolean dfs(int cnt, char[][] board){
        
            if(cnt == 0) return true;
            int min = 10, x = 0, y = 0;
            //剪枝，即找出当前所以空格可填数字个数最少的位置 记为x y
            for(int i = 0; i < N; i++){
        
                for(int j = 0; j < N; j++){
        
                    if(board[i][j] == '.'){
        
                        int k = ones[get(i, j)];
                        if(k < min){
        
                            min = k;
                            x = i;
                            y = j;
                        }
                    }
                }
            }
            //遍历当前 x y所有可选数字
            for(int i = get(x, y); i != 0; i ^= lowBit(i)){
        
                int t = map[lowBit(i)];
                
                change_state(x, y, t);
                board[x][y] = (char)('1' + t);
                
                if(dfs(cnt - 1, board)) return true;
                
                //恢复现场
                change_state(x, y, t);
                board[x][y] = '.';
            }
            return false;
        }
        void change_state(int x, int y, int t){
        
            row[x] ^= 1 << t;
            col[y] ^= 1 << t;
            cell[x / 3][y / 3] ^= 1 << t;
        }
        //对维护数组x行,y列的3个集合(行、列、九宫格)进行&运算
        //就可以获得可选数字的集合(因为我们用1标识可填数字)
        int get(int x, int y){
        
            return row[x] & col[y] & cell[x / 3][y / 3];
        }
        int lowBit(int x){
        
            return -x & x;
        }
    }
    //作者：ri-mu-tu-yuan-12

## 51. N皇后 ##

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  
上图为 8 皇后问题的一种解法。  
![format_png 1][]

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

输入: 4  
输出: \[  
\[".Q…", // 解法 1  
“…Q”,  
“Q…”,  
“…Q.”\],

\["…Q.", // 解法 2  
“Q…”,  
“…Q”,  
“.Q…”\]  
\]  
解释: 4 皇后问题存在两个不同的解法。

### 回溯算法 ###

在 n\*n 的矩阵中摆放 n 个皇后，并且每个皇后不能在同一行，同一列，同一对角线上，求所有的 n 皇后的解。

一行一行地摆放，在确定一行中的那个皇后应该摆在哪一列时，需要用三个标记数组来确定某一列是否合法，这三个标记数组分别为：列标记数组、45 度对角线标记数组和 135 度对角线标记数组。

45 度对角线标记数组的长度为 2 \* n - 1，通过下图可以明确 (r, c) 的位置所在的数组下标为 r + c。  
![format_png 2][]  
135 度对角线标记数组的长度也是 2 \* n - 1，(r, c) 的位置所在的数组下标为 n - 1 - (r - c)。  
![format_png 3][]

class Solution {
        
        private List<List<String>> result;
        private char[][] nQueens;
        private boolean[] colUsed;
        private boolean[] diagonal1; //45度对角线
        private boolean[] diagonal2; //135度对角线
        private int n;
        private void backtrack(int row) {
        
            if (row == n) {
        
                List<String> temp = new ArrayList<>();
                for (char[] chars : nQueens) {
        
                    temp.add(new String(chars));
                }
                result.add(temp);
                return;
            }
            for (int col = 0; col < n; col++) {
        
                int index1 = col + row; //45度对角线索引
                int index2 = n - 1 - (row - col); //135度对角线索引
                if (colUsed[col] || diagonal1[index1] || diagonal2[index2]) {
        
                    continue;
                }
                nQueens[row][col] = 'Q';
                colUsed[col] = diagonal1[index1] = diagonal2[index2] = true;
                backtrack(row + 1);
                colUsed[col] = diagonal1[index1] = diagonal2[index2] = false;
                nQueens[row][col] = '.';
            }
        }
        public List<List<String>> solveNQueens(int n) {
        
            result = new ArrayList<>();
            nQueens = new char[n][n];
            for (int i = 0; i < n; ++i) {
        
                Arrays.fill(nQueens[i], '.');
            }
            colUsed = new boolean[n];
            diagonal1 = new boolean[2 * n - 1];
            diagonal2 = new boolean[2 * n - 1];
            this.n = n;
            backtrack(0);
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GdFJWam8zckJVcFR3T1pzdUMzZlJjNk5OT2hB?x-oss-process=image/format,png
[https_leetcode-cn.com_problems_sudoku-solver_solution_jie-shu-du-by-leetcode]: https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GcnNobVRuRDFjSVZlenExYTdHX3hseExhcHl3?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GdWhFN3V5SzMzZDZ3ZUt5MHk2RXoxdWE4MjVm?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GanBVWEVXdTZoWExKNTFWN0xVUi1GRHY3WUo2?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191217151020798.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI=,size_16,color_FFFFFF,t_70