力扣36. 有效的数独

发布时间:2024年01月20日

模拟

  • 思路:
    • 使用三个哈希表来存储数字个数
      • row[r][val] 用于存储第 r 行 val + 1 的个数;
      • column[c][val] 用于存储第 c 列 val + 1 的个数;
      • subboxes[i][j][val] 用于存储第 i 行、第 j 列个小九宫格 val + 1 的个数,其中:

        • i = r / 3,j = c / 3

    • ???????遍历每个小格子,统计数字的个数,分别计入对应的哈希表里,如果个数超过了 1 ,则数独无效

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9][9];
        int columns[9][9];
        int subboxes[3][3][9];

        memset(rows, 0, sizeof(rows));
        memset(columns, 0, sizeof(columns));
        memset(subboxes, 0, sizeof(subboxes));

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 ||
                        columns[j][index] > 1 ||
                        subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
};

——————————————————————————————————

文章来源:https://blog.csdn.net/N_BenBird/article/details/135708101
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。