题解 | #暮光数独验证# 哈希表 模拟

知识点

哈希表 模拟

思路

这道题的宫格的规则是说在那个范围内的数字只能出现一次，其他数字不管

实际上思路很简单，就是遍历每一行，每一列看是否满足要求；如果满足的话可以遍历每一个位置，计算出所属的宫格，之后依照对应的要求进行判断。判断是否存在可以开哈希表，但没啥必要，常数比较大。可以开一个大小为10的布尔数组记录一下是否出现过即可。

只遍历整个数组若干次，时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return bool布尔型
     */
    const int n = 9;
    using PCC = pair<char, char>;
    bool isValidTwilightSudoku(vector<vector<char> >& board) {
        for (int i = 0; i < n; i ++) {
            if (!checkRow(board, i)) return false;
            if (!checkCol(board, i)) return false;
        }
        vector<PCC> lim(9);
        lim[0] = lim[4] = lim[8] = {'1', '3'};
        lim[1] = lim[5] = {'4', '6'};
        lim[2] = lim[6] = {'7', '9'};
        lim[3] = lim[7] = {'1', '9'};
        vector<vector<bool>> st(9, vector<bool>(10, false));
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                if (board[i][j] == '.') continue;
                auto c = board[i][j];
                int t = i / 3 * 3 + j / 3;
                if (c < lim[t].first or c > lim[t].second) continue;
                if (st[t][c - '0']) return false;
                st[t][c - '0'] = true;
            }
        }
        return true;
    }
    bool checkRow(vector<vector<char>>& g, int x) {
        vector<bool> st(10, false);
        for (int i = 0; i < n; i ++) {
            if (g[x][i] == '.') continue;
            int u = g[x][i] - '0';
            if (st[u]) return false;
            st[u] = true; 
        }
        return true;
    }
    bool checkCol(vector<vector<char>>& g, int x) {
        vector<bool> st(10, false);
        for (int i = 0; i < n; i ++) {
            if (g[i][x] == '.') continue;
            int u = g[i][x] - '0';
            if (st[u]) return false;
            st[u] = true; 
        }
        return true;
    }
};