@LeetCode刷题

文章目录

• 题目
• 一、实现思路
• 二、总体代码

---

题目

题目链接：https://leetcode-cn.com/problems/valid-sudoku/

一、实现思路

1. 创建三个hashmap来装每行、每列和每个小宫格内的数字及个数

        HashMap<Integer, Integer> rows[] = new HashMap[9];
        HashMap<Integer, Integer> columns[] = new HashMap[9];
        HashMap<Integer, Integer> boxs[] = new HashMap[9];

        for( int i=0; i<9; ++i ){
            rows[i] = new HashMap<>();
            columns[i] = new HashMap<>();
            boxs[i] = new HashMap<>();
        }

2. 确认当前数字处于哪一宫格：想象为一个mn的二维数组变成一个一维数组，那么原来的[i, j] = [jn+i]；

int box_index = (j/3)*3+(i/3);

3. 当每一行rows的当前的num的value小于等于1、每一列columns的当前num的value小于等于1、每一个小宫格boxs的当前的num的value小于等于1时，才能继续运行，否则就要返回false。

                if( rows[i].get(n)>1 || columns[j].get(n)>1 || boxs[box_index].get(n)>1 ){
                    return false;
                }

二、总体代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Integer, Integer> rows[] = new HashMap[9];
        HashMap<Integer, Integer> columns[] = new HashMap[9];
        HashMap<Integer, Integer> boxs[] = new HashMap[9];

        for( int i=0; i<9; ++i ){
            rows[i] = new HashMap<>();
            columns[i] = new HashMap<>();
            boxs[i] = new HashMap<>();
        }
        for( int i=0; i<9; ++i ){
            for( int j=0; j<9; ++j ){
                if( board[i][j]=='.' ){
                    continue;
                }
                int n = board[i][j]-'0';
                int box_index = (j/3)*3+(i/3);
                rows[i].put(n, rows[i].getOrDefault(n, 0)+1);
                columns[j].put(n, columns[j].getOrDefault(n, 0)+1);
                boxs[box_index].put(n, boxs[box_index].getOrDefault(n, 0)+1);
                if( rows[i].get(n)>1 || columns[j].get(n)>1 || boxs[box_index].get(n)>1 ){
                    return false;
                }
            }
        }
        return true;
    }
}