★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9900296.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the 9
3x3sub-boxes of the grid must contain the digits1-9without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character \'.\'.
Example 1:
Input: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] Output: true
Example 2:
Input:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8\'s in the top left 3x3 sub-box, it is invalid.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
- The given board contain only digits
1-9and the character\'.\'. - The given board size is always
9x9.
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 \'.\' 表示。
示例 1:
输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字
1-9和字符\'.\'。 - 给定数独永远是
9x9形式的。
48ms
1 class Solution { 2 func isValidSudoku(_ board: [[Character]]) -> Bool { 3 var rowSet = Set<Character>() 4 var colSet = Set<Character>() 5 var cube = Set<Character>() 6 7 8 for i in 0..<9 { 9 rowSet.removeAll() 10 colSet.removeAll() 11 for j in 0..<9 { 12 let rowval = board[i][j] 13 let colval = board[j][i] 14 if rowval != "." { 15 if rowSet.contains(rowval) {return false} 16 rowSet.insert(rowval) 17 } 18 if colval != "." { 19 if colSet.contains(colval) {return false} 20 colSet.insert(colval) 21 } 22 } 23 24 } 25 print("here") 26 for i in 0..<3 { 27 for j in 0..<3 { 28 cube.removeAll() 29 let row = i * 3 30 let col = j * 3 31 for x in row..<(row + 3) { 32 for y in col..<(col + 3) { 33 let val = board[x][y] 34 if val != "." { 35 if cube.contains(val) {return false} 36 cube.insert(val) 37 } 38 } 39 } 40 } 41 } 42 43 return true 44 } 45 }
52ms
1 class Solution { 2 func isValidSudoku(_ board: [[Character]]) -> Bool { 3 guard board.count == 9, board[0].count == 9 else { return false } 4 5 var rowSet = Set<Character>() 6 var columnSet = Set<Character>() 7 for i in 0..<board.count { 8 9 for j in 0..<board[0].count { 10 if board[i][j] != "." { 11 if !rowSet.insert(board[i][j]).inserted { return false } 12 } 13 if board[j][i] != "." { 14 if !columnSet.insert(board[j][i]).inserted { return false } 15 } 16 } 17 rowSet.removeAll() 18 columnSet.removeAll() 19 } 20 21 for i in 0..<3 { 22 for j in 0..<3 { 23 for m in i * 3..<i * 3 + 3 { 24 for n in j * 3..<j * 3 + 3 { 25 if board[m][n] != "." { 26 if !rowSet.insert(board[m][n]).inserted { return false } 27 } 28 } 29 } 30 rowSet.removeAll() 31 } 32 } 33 34 return true 35 } 36 }
52ms
1 class Solution { 2 func isValidSudoku(_ board: [[Character]]) -> Bool { 3 //check row 4 for i in 0..<board.count { 5 let row = board[i] 6 var nums = [Character]() 7 8 for j in 0..<row.count { 9 if row[j] != "." { 10 if nums.contains(row[j]) == false { 11 nums.append(row[j]) 12 } else { 13 return false 14 } 15 } 16 } 17 } 18 19 //check col 20 for i in 0..<board.count { 21 var cols = [Character]() 22 let row = board[i] 23 for j in 0..<row.count { 24 if board[j][i] != "." { 25 if cols.contains(board[j][i]) == false { 26 cols.append(board[j][i]) 27 } else { 28 return false 29 } 30 } 31 } 32 } 33 34 //check sub board 35 for i in stride(from: 0, to: board.count, by: 3) { 36 for j in stride(from: 0, to: board.count, by: 3) { 37 var subBoard = [Character]() 38 for n in 0..<3 { 39 for m in 0..<3 { 40 if board[i + n][j + m] != "." { 41 if subBoard.contains(board[i + n][j + m]) == false { 42 subBoard.append(board[i + n][j + m]) 43 } else { 44 return false 45 } 46 } 47 } 48 } 49 } 50 } 51 return true 52 } 53 }
56ms
1 class Solution { 2 func isValidSudoku(_ board: [[Character]]) -> Bool { 3 func isValid(_ board: [[Character]],_ row: Int,_ col: Int,_ c: Character) -> Bool { 4 func isExistInRow(_ board: [[Character]],_ row: Int,_ col: Int, _ c: Character) -> Bool { 5 for i in 0..<board.count { 6 if board[row][i] == c && i != col{ 7 return true 8 } 9 } 10 return false 11 } 12 func isExistInCol(_ board: [[Character]],_ row: Int,_ col: Int, _ c: Character) -> Bool { 13 for i in 0..<board.count { 14 if board[i][col] == c && i != row{ 15 return true 16 } 17 } 18 return false 19 } 20 func isExistInSmallGird(_ board: [[Character]],_ startRow: Int, _ startCol: Int,_ row: Int,_ col: Int,_ c: Character) -> Bool { 21 for i in 0..<3 { 22 for j in 0..<3 { 23 if board[i + startRow][j + startCol] == c && i + startRow != row && j + startCol != col { 24 return true 25 } 26 } 27 } 28 return false 29 } 30 let startRow = row - row % 3 31 let startCol = col - col % 3 32 return !isExistInCol(board, row, col, c) && !isExistInRow(board, row, col, c) && !isExistInSmallGird(board, startRow, startCol, row, col, c) 33 } 34 for i in 0..<9 { 35 for j in 0..<9 { 36 if board[i][j] != Character.init(".") { 37 if isValid(board, i, j, board[i][j]) == false { 38 return false 39 } 40 } 41 } 42 } 43 return true 44 } 45 }
56ms
1 class Solution { 2 func isValidSudoku(_ board: [[Character]]) -> Bool { 3 guard board.count > 0 && board[0].count > 0 else { 4 return false 5 } 6 let rowCount = board.count 7 let colCount = board[0].count 8 var rowFlag = Array<[Bool]>(repeating: Array<Bool>(repeating: false, count: colCount), count: rowCount) 9 var colFlag = Array<[Bool]>(repeating: Array<Bool>(repeating: false, count: colCount), count: rowCount) 10 var cellFlag = Array<[Bool]>(repeating: Array<Bool>(repeating: false, count: colCount), count: rowCount) 11 12 13 for i in 0..<rowCount { 14 for j in 0..<colCount { 15 let num = Int(board[i][j].unicodeScalars.first!.value) 16 if num >= 49 && num <= 57 { 17 let c = num - 49 18 if rowFlag[i][c] || colFlag[c][j] || cellFlag[3 * (i / 3) + j / 3][c] { 19 return false 20 } 21 rowFlag[i][c] = true 22 colFlag[c][j] = true 23 cellFlag[3 * (i / 3) + j / 3][c] = true 24 } 25 26 } 27 } 28 return true 29 } 30 }
60ms
1 class Solution { 2 3 enum BoardType { 4 case colon 5 case row 6 case subSquare 7 } 8 9 func isValidSudoku(_ board: [[Character]]) -> Bool { 10 11 func doesContains(index: (row: Int, col: Int), boardType: BoardType) -> Bool{ 12 switch boardType { 13 case .colon: 14 for i in index.row+1..<9 { 15 if board[index.row][index.col] == board[i][index.col] { return true } 16 } 17 case .row: 18 let array = board[index.row][index.col + 1..<9] 19 if array.contains(board[index.row][index.col]) { return true} 20 21 case .subSquare: 22 for squareRow in 0..<3 { 23 for squareCol in 0..<3 { 24 let x = index.row / 3 * 3 + squareRow 25 let y = index.col / 3 * 3 + squareCol 26 if board[index.row][index.col] == board[x][y] && index.row != x && index.col != y { 27 return true 28 29 } 30 } 31 32 } 33 34 } 35 return false 36 } 37 38 // check horizontal 39 for row in 0..<9 { 40 for col in 0..<9 { 41 let character = board[row][col] 42 if let number = Int(String(character)) { 43 // Check horizontal 44 if doesContains(index: (row,col), boardType: .row) { return false } 45 46 // Check vertical 47 if doesContains(index: (row,col), boardType: .colon) { return false } 48 49 // Check sub-square 50 if doesContains(index: (row,col), boardType: .subSquare) { return false } 51 } 52 53 } 54 } 55 56 return true 57 } 58 }
60ms
1 class Solution { 2 func valid(_ board:[[Character]]) -> Bool { 3 //行 4 var lineList = [Character]() 5 //列 6 var columnList = [Character]() 7 8 for i in 0..<9 { 9 for j in 0..<9 { 10 11 //扫描行 12 var lineNum = board[i][j] 13 if(!(lineNum==".")){ 14 if(lineList.contains(lineNum)){ 15 return false 16 }else{ 17 lineList.append(lineNum) 18 } 19 } 20 21 //扫描列 22 var columnNum = board[j][i] 23 if(!(columnNum==".")){ 24 if(columnList.contains(columnNum)){ 25 return false 26 }else{ 27 columnList.append(columnNum) 28 } 29 } 30 } 31 lineList.removeAll() 32 columnList.removeAll() 33 } 34 35 return true 36 } 37 38 func isValidSudoku(_ board: [[Character]]) -> Bool { 39 var valid = true 40 valid = self.valid(board) 41 if(!valid){ 42 return false 43 } 44 45 var smallBoard = [[Character]]() 46 47 //stride正向跳跃遍历 48 for i in stride(from: 0, to: 9, by: 3) { 49 for j in stride(from: 0, to: 9, by: 3) { 50 51 var line0 = [board[i][j],board[i][j+1],board[i][j+2]] 52 var line1 = [board[i+1][j],board[i+1][j+1],board[i+1][j+2]] 53 var line2 = [board[i+2][j],board[i+2][j+1],board[i+2][j+2]] 54 smallBoard.append(line0) 55 smallBoard.append(line1) 56 smallBoard.append(line2) 57 58 //检查 3*3 重复 59 var checkList = [Character]() 60 for list in smallBoard { 61
请发表评论