文章目錄

• • 1. 題目信息
  • 2. 解題
  • • 2.1 暴力3次遍歷查找
    • 2.2 一次遍歷查找

1. 題目信息

判斷一個 9x9 的數(shù)獨是否有效。只需要根據(jù)以下規(guī)則，驗證已經填入的數(shù)字是否有效即可。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現(xiàn)一次。

上圖是一個部分填充的有效的數(shù)獨。

數(shù)獨部分空格內已填入了數(shù)字，空白格用 ‘.’ 表示。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-sudoku
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

2.1 暴力3次遍歷查找

對每行，每列，每個小塊分別進行hash查重即可。

class Solution { public:bool isValidSudoku(vector<vector<char>>& board){int i, j, x, y;unordered_map<int, int> m;for(i = 0; i < 9; ++i){m.clear();for(j = 0; j < 9; ++j){if(board[i][j] != '.'){if(m.find(board[i][j]-'0') != m.end())return false;elsem[board[i][j]-'0'] = 1;}}}for(j = 0; j < 9; ++j){m.clear();for(i = 0; i < 9; ++i){if(board[i][j] != '.'){if(m.find(board[i][j]-'0') != m.end())return false;elsem[board[i][j]-'0'] = 1;}}}for(i = 0; i < 9; i += 3){for(j = 0; j < 9; j += 3){m.clear();for(x = i; x < i+3; ++x){for(y = j; y < j+3; ++y){if(board[x][y] != '.'){if(m.find(board[x][y]-'0') != m.end())return false;elsem[board[x][y]-'0'] = 1;}}}}}return true;} };

2.2 一次遍歷查找

9個小9宮格的序號 idx = (i/3)*3+j/3
分別為行和列和宮格建立27個hash表，進行查重

class Solution { public:bool isValidSudoku(vector<vector<char>> &board) {unordered_map<int, int> row[9];unordered_map<int, int> column[9];unordered_map<int, int> box[9];int i, j, box_idx, num;for(i = 0; i < 9; ++i){for(j = 0; j < 9; ++j){box_idx = (i/3)*3 + j/3;num = board[i][j] - '0';if(board[i][j] != '.'){if(row[i].find(num) != row[i].end() ||column[j].find(num) != column[j].end() ||box[box_idx].find(num) != box[box_idx].end())return false;else{row[i][num] = 1;column[j][num] = 1;box[box_idx][num] = 1;}}}}return true;} };

總結

以上是生活随笔為你收集整理的LeetCode 36. 有效的数独（哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。