问题说明
有六个九宫格的大柜子,大柜子编号 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)$。可以发现结果是正确的。
我们回溯这个算式,得到:
i = (n / 3) + 3(m / 3) \\
j = (n \mod 3) + 3(m \mod 3)
$$
这就是计算坐标的公式。实际上,你会发现这其实就是用一维数组存放二维数组的公式。
同时,可以总结一个规律:
当以先行后列的顺序遍历时,模可得行号,除可得列号。(其中,行、列号都是相对于其“容器”而言的)
应用:
有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
我的答案:
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;
}
};