牛客网刷题(四)

数独

解法一：

解法一的思路较为直接：对数独中的每个位置，若其不为.，即没有被数字所填，则从数字1至9遍历，分别填写该位置，并检验此时数独是否有效。若成功填满最后一个位置，即是该数独的解，否则将填写的位置重置，继续遍历。
在「检验数独」是否有效时，需要如下3个步骤：

检验数独的每一行是否有效，因此需要对「刚才所填写的数字」所在的「行」进行遍历；
检验数独的每一列是否有效，因此需要对「刚才所填写的数字」所在的「列」进行遍历；
检验每一个3x3的方块是否有效，对于位置(i, j)，其所在的方块区域为：
行：从i / 3 * 3到 i / 3 * 3 + 1;
列：从j / 3 * 3到 j / 3 * 3 + 1;
注意：在未找到解法、从而回溯的时候，需要进行重置操作，即置为.

注意：int + '0’可以将int类型转换为char类型。

class Solution {
    
public:
    void solveSudoku(vector<vector<char> > &board) {
    
        if (!board.size() || !board[0].size()) 
            return; 
        helper(board); 
        return; 
    }
    bool judgeValid(vector<vector<char> > &board, int target, int row, int col) {
    
        char ch = target + '0'; 
        // 判断每一行是否有效
        for (int i = 0; i < board[0].size(); i ++) {
    
            if (board[row][i] == ch) 
                return false; 
        }
        // 判断每一列是否有效
        for (int i = 0; i < board.size(); i ++) {
    
            if (board[i][col] == ch) 
                return false; 
        }
        // 判断每一个方块是否有效
        for (int i = (row / 3) * 3; i < (row / 3) * 3 + 3; i ++) {
    
            for (int j = (col / 3) * 3; j < (col / 3) * 3 + 3; j ++) {
    
                if (board[i][j] == ch) 
                    return false; 
            } 
        }
        return true; 
    }
    bool helper(vector<vector<char> > &board) {
    
        for (int i = 0; i < board.size(); i ++) {
    
            for (int j = 0; j < board[0].size(); j ++) {
    
                // 如果已经被填写，则跳过
                if (board[i][j] != '.') 
                    continue; 
                // 从1至9进行遍历
                for (int k = 1; k <= 9; k ++) {
    
                    if (judgeValid(board, k, i, j)) {
     // 如果是有效的
                        board[i][j] = (k + '0'); 
                        if (helper(board)) // 继续求解，并找到一个解
                            return true; 
                        else
                            board[i][j] = '.';  // 没能找到答案，重置
                    } 
                }
                return false; 
            }
        }
        return true; 
    }
};

该方法需要对每一个空位置进行从1至9的遍历，因此总时间复杂度为O(9^N)；此外，对每个空位置需要调用递归函数，因此空间复杂度为O(N)，其中N为空位置数目。
在判断数独是否有效时，解法一分别进行了三个for循环来判断行、列、方块是否有效，然而，当这三者有其一无效时，整个数独便可认为是无效的，无需进行后续的判断。

因此，可以对judgeValid函数进行如下优化：

    bool judgeValid(vector<vector<char> > &board, int target, int row, int col) {
    
        char ch = target + '0'; 
        int blockRow = (row / 3) * 3, blockCol = (col / 3) * 3; 
        for(int i = 0; i < 9; i ++) {
    
            // 判断每行、每列
            if (board[i][col] == ch || board[row][i] == ch) 
                return false; 
            // 判断方块
            if (board[blockRow + i / 3][blockCol + i % 3] == ch) 
                return false; 
        }
        return true; 
    }

解法二：

解法一在每次调用helper函数时，都从最开始的位置（0，0）开始遍历。解法二的思路如下：在填写数独时，每次按照行从左至右填写，若当前行被填满了则继续填写下一行，因此数独的求解成功条件为：已经填写完最后一行。

在对每一个位置进行填写时，从1至9遍历，并利用「解法一优化」中所述的思路进行判断行、列、方块都是否满足要求。

解法二的剪枝思路如下：在填写完一个格子后，调用下一层递归helper(board, row, col + 1)并存储其返回结果，若为true，说明在后续递归中找到了一个解，则不必再尝试其他数字，直接返回true。

 class Solution {
    
public:
    void solveSudoku(vector<vector<char> > &board) {
    
        if (!board.size() || !board[0].size()) 
            return; 
        helper(board, 0, 0); 
        return; 
    }
    bool helper(vector<vector<char> > &board, int row, int col) {
    
        if (row == 9) {
     // 如果当前行都被填满了，则说明到当前行为止是成功的
            return true;  
        }
        if (col == 9) {
     // 若达到；1最后一列，则从下一行的第一列重新开始填
            return helper(board, row + 1, 0); 
        }
        if (board[row][col] != '.') // 如果没有被填
            return helper(board, row, col + 1); 
        for (int i = 1; i <= 9; i ++) {
     // 遍历1到9
            if (judgeValid(board, row, col, i)) {
     // 如果填的当前数字不冲突
                board[row][col] = (i + '0'); // 填写
                if (helper(board, row, col + 1)) // 剪枝
                    return true; 
                else 
                    board[row][col] = '.'; // 重置
            }
        }
        return false; // 遍历1到9后仍未得到结果，返回false
    }
    bool judgeValid(vector<vector<char> > &board, int row, int col, int target) {
    
        char ch = target + '0';
        int blockRow = (row / 3) * 3, blockCol = (col / 3) * 3; 
        for (int i = 0; i < 9; i ++) {
     // 判断行、列
            if (board[row][i] == ch || board[i][col] == ch) 
                return false; 
            // 判断方块
            if (board[blockRow + i / 3][blockCol + i % 3] == ch)
                return false; 
        }
        return true; 
    }
};

该方法需要对每一个空位置进行从1至9的遍历，因此总时间复杂度为O(9^N)；此外，对每个空位置需要调用递归函数，因此空间复杂度为O(N)，其中N为空位置数目。