Site Overlay

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

问题说明

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

4b5ea3149d76bd5feb11a3b6d9d08df4.png

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

首先,以 $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)$。可以发现结果是正确的。

我们回溯这个算式,得到:

$$
i = (n / 3) + 3(m / 3) \\
j = (n \mod 3) + 3(m \mod 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;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注