36 有效的数独

https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2f9gg/

https://leetcode.cn/problems/valid-sudoku/description/

cost: 22m8s

如何将 (i, j) 一一映射成小九宫格呢？

for (x++) {
    for (y++) {
        baseX = i / 3 * 3;
        baseY = i % 3 * 3;
        x = baseX + y % 3;
        y = baseY + y / 3;
    }
}

但是这样很难想。更简单的方式是不追求顺序映射，(i, j) 都在编号为 (i/3, j/3) 的九宫格内。提前创建好 9 个集合，按照按照编号往对应集合中放就行了。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> s;
        for (int i = 0; i < board.size(); i++) {
            s.clear();
            for (int j = 0; j < board.size(); j++) {
                char ch = board[i][j];
                if (ch == '.') {
                    continue;
                }
                if (s.count(ch)) {
                    return false;
                }
                s.insert(ch);
            }

            s.clear();
            for (int j = 0; j < board.size(); j++) {
                char ch = board[j][i];
                if (ch == '.') {
                    continue;
                }
                if (s.count(ch)) {
                    return false;
                }
                s.insert(ch);
            }

            s.clear();
            int x = i / 3 * 3;
            int y = i % 3 * 3;
            for (int j = 0; j < board.size(); j++) {
                char ch = board[x + j % 3][y + j / 3];
                if (ch == '.') {
                    continue;
                }
                if (s.count(ch)) {
                    return false;
                }
                s.insert(ch);
            }
        }
        return true;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)