关于java:LeetCode036有效的数独

42次阅读

共计 1993 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：请你判断一个 9×9 的数独是否无效。只须要依据以下规定，验证曾经填入的数字是否无效即可。

数字 1-9 在每一行只能呈现一次。
数字 1-9 在每一列只能呈现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。（请参考示例图）
数独局部空格内已填入了数字，空白格用 ‘.’ 示意。

留神：

一个无效的数独（局部已被填充）不肯定是可解的。

只须要依据以上规定，验证曾经填入的数字是否无效即可。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：数组遍历

分为 3 种状况判断，别离是行判断、列判断、3* 3 宫内判断，判断逻辑是利用 Set 判重，如果在同一行（或同一列、同一宫内）有反复的数字，则返回 false；如果都合乎，最初返回 true。

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeetCode_036 {public static List<Pair<Integer, Integer>> all = new ArrayList<>();

    static {all.add(new Pair<>(0, 0));
        all.add(new Pair<>(0, 3));
        all.add(new Pair<>(0, 6));
        all.add(new Pair<>(3, 0));
        all.add(new Pair<>(3, 3));
        all.add(new Pair<>(3, 6));
        all.add(new Pair<>(6, 0));
        all.add(new Pair<>(6, 3));
        all.add(new Pair<>(6, 6));
    }

    public static boolean isValidSudoku(char[][] board) {
        // 行判断
        for (int i = 0; i < board.length; i++) {Set<Character> nums = new HashSet<>();
            for (int j = 0; j < board[i].length; j++) {if (board[i][j] != '.' && !nums.add(board[i][j])) {return false;}
            }
        }
        // 列判断
        for (int i = 0; i < board.length; i++) {Set<Character> nums = new HashSet<>();
            for (int j = 0; j < board.length; j++) {if (board[j][i] != '.' && !nums.add(board[j][i])) {return false;}
            }
        }
        // 宫内判断
        for (Pair<Integer, Integer> integerIntegerPair : all) {Set<Character> nums = new HashSet<>();
            for (int x = integerIntegerPair.getKey(); x < integerIntegerPair.getKey() + 3; x++) {for (int y = integerIntegerPair.getValue(); y < integerIntegerPair.getValue() + 3; y++) {if (board[x][y] != '.' && !nums.add(board[x][y])) {return false;}
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {char[][] board = new char[][]{{'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'}};
        System.out.println(isValidSudoku(board));
    }
}