LeetCode 解答 #36. Valid Sudoku プログラミング練習
問題:
難易度: medium
入力: character型array
目的: 入力された数独パズルの盤面が有効か判断せよ
出力: boolean
皆さんお馴染みの数独ゲームの問題です。
解らない人もいると思うのでルールとしては:
9*9の盤面をもらい、縦が1-9、横も1-9、更に9個のsub-box(3*3)もすべて1-9の重複なしの数字で埋めるゲームです。
なので一列、一行、一箱に同じ数字が存在してはなりません。
この問題は、数独を実際に解くのではなく、入力された問題が有効かを判断する問題です。
つまり、入力の時点で縦、横、3*3ブロックの中に重複した数字があるかどうかを判断すればいいのです。
注意すべき事:
- 最終的に数独としての解があるかどうかは判断しなくてよい。(現時点での有効か否かだけ判断する)
- 未入力部分は'.'で表されている。
以下回答です。
class Solution { class Solution { public boolean isValidSudoku(char[][] board) { for (int i=0; i<9; i++) { HashSet<Character> row = new HashSet<Character>(); HashSet<Character> col = new HashSet<Character>(); HashSet<Character> cube = new HashSet<Character>(); for (int j=0; j<9; j++) { if (board[i][j] != '.' && !row.add(board[i][j])) return false; if (board[j][i] != '.' && !col.add(board[j][i])) return false; int m = 3 * (i / 3) + j / 3; int n = j % 3 + 3 * (i % 3); if (board[m][n] != '.' && !cube.add(board[m][n])) return false; } } return true; } }
iを行とし、jを列とする。
for文で一列、一行ずつ見て判断する。
真ん中のm, nは現在のi, jから3*3ブロックに変換しています。
HashSetを使い、重複があったらfalseを返します。
最後まで実行出来たら有効判断をします。
今日は以上。
よいプログラミング生活を!