二维数组的取模技巧 & 用位图代替哈希表的碰撞检测

问题说明

有六个九宫格的大柜子，大柜子编号 0~5，大柜子的格子（以黑色为单元格）编号 0~8。如下图堆放在一起。现在请给出一个公式，输入柜号 $m$、格号 $n$，输出格子所在的行列位置 $(i, j)$。$m,n,i,j$ 从 $0$ 计数。

这个公式应该怎么推导呢？

首先，以 $m = 4$ 号柜，也就是中下方的红色柜为例，取格号 $n = 6$，也即左下角的小黑格。

对格号 $n$ 模以 $3$，即可得到格子在其柜子的小列号 6 % 3 = 0。
对格号 $n$ 除以 $3$，即可得到格子在其柜子的小行号 6 / 3 = 2。

对柜号 $m$ 模以 $3$ ，可以得到柜子在整体（以红色为单元格）的大列号 4 % 3 = 1。
对柜号 $m$ 除以 $3$ ，可以得到柜子在整体（以红色为单元格）的大行号 4 / 3 = 1。

格子在整体的小行号，等于格子在柜子的小行号，加上三倍的柜子的大行号。$i = 2 + 3 = 5$。
格子在整体的小列号，等于格子在柜子的小列号，加上三倍的柜子的大列号。$j =0 + 3 = 3$。

所以得到坐标：$(i, j)=(5, 3)$。可以发现结果是正确的。

我们回溯这个算式，得到：

这就是计算坐标的公式。实际上，你会发现这其实就是用一维数组存放二维数组的公式。

同时，可以总结一个规律：

当以先行后列的顺序遍历时，模可得行号，除可得列号。（其中，行、列号都是相对于其“容器”而言的）

应用：

有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

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

我的答案：

class Solution
{
public:
    bool isValidSudoku(vector<vector<char>> &board)
    {
        for (short i = 0; i < 9; i++)
        {
            unordered_map<int, bool> mapOfRow;
            unordered_map<int, bool> mapOfCol;
            unordered_map<int, bool> mapOfBox;
            for (short j = 0; j < 9; j++)
            {                
                if (mapOfRow.find(board[i][j]) != mapOfRow.end())
                {
                    return false;
                }
                if (mapOfCol.find(board[j][i]) != mapOfCol.end())
                {
                    return false;
                }
                if (board[i][j] != '.')
                    mapOfRow[board[i][j]] = true;
                if (board[j][i] != '.')
                    mapOfCol[board[j][i]] = true;

                short m = j / 3 + 3 * (i / 3);
                short n = j % 3 + 3 * (i % 3);
                if (mapOfBox.find(board[m][n]) != mapOfBox.end())
                {
                    return false;
                }

                if (board[m][n] != '.')
                    mapOfBox[board[m][n]] = true;
            }
        }
        return true;
    }
};

当然，考虑到性能，虽然是哈希表检查重复，但是不一定非要用哈希表结构，用位图也是可以的：

class Solution
{
public:
    bool isValidSudoku(vector<vector<char>> &board)
    {
        bool bitmap[27] = {};
        for (short i = 0; i < 9; i++)
        {
            for (short j = 0; j < 9; j++)
            {
                short m = j / 3 + 3 * (i / 3);
                short n = j % 3 + 3 * (i % 3);

                if (board[i][j] != 46 && bitmap[board[i][j] - 49]) return false;
                if (board[j][i] != 46 && bitmap[board[j][i] - 40]) return false;
                if (board[m][n] != 46 && bitmap[board[m][n] - 31]) return false;

                if (board[i][j] != 46) bitmap[board[i][j] - 49] = 1;
                if (board[j][i] != 46) bitmap[board[j][i] - 40] = 1;
                if (board[m][n] != 46) bitmap[board[m][n] - 31] = 1;
            }
            memset(bitmap, 0, 27);
        }
        return true;
    }
};