本次作业完成了力扣《面试经典 150 题》「矩阵」部分的全部题目。
力扣 面试经典 150 题 - 矩阵
LeetCode 36. 有效的数独
思路
对数独内的数字依次统计出现次数即可。
实现上来说，需要注意对空白字符 . 的处理。
代码
提交记录：12 ms (95.29%) / 17.46 MB (69.66%)
#define check(i, j, k) (board[i][j] != '.' && x[board[i][j] - 46 + k * 12])
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
for (int i = 0, x[36] = {0}; i < 9; ++i, memset(x, 0, sizeof(x)))
for (int j = 0; j < 9; ++j)
if (check(i, j, 0) || check(j, i, 1) || check(i / 3 * 3 + j / 3, i % 3 * 3 + j % 3, 2)) return false;
else x[board[i][j] - 46] = x[board[j][i] - 34] = x[board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - 22] = 1;
return true;
}
};
LeetCode 54. 螺旋矩阵
思路
从 $(0,0)$ 开始，遇到曾经遍历过的数字或遇到边界则向右调整方向。因为每个数字只会被遍历一次，所以时间复杂度为 $\mathrm O(n\times m)$。
代码
提交记录：0 ms (100.00%) / 7.06 MB (18.35%)
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans = {matrix[0][0]}, x = {0, 1, 0, -1, 0};
auto check = [&](int t, int i, int j) { return j + x[t + 1] < matrix[0].size() && i + x[t] < matrix.size() && i + x[t] >= 0 && matrix[i + x[t]][j + x[t + 1]] > -101; };
auto next = [&](int t, int i, int j) { return check(t, i, j) ? t : (t + 1) % 4; };
for (int i = 0, j = 0, t = matrix[0].size() == 1; check(t, i, j); t = next(t, i, j)) matrix[i][j] = -101, ans.push_back(matrix[i += x[t]][j += x[t + 1]]);
return ans;
}
};
LeetCode 48. 旋转图像
思路
不难发现，旋转遵循 $(i, j) \rightarrow (j, sz - i)$ 的规则，其中 $sz$ 为矩阵的边长。此外，因为对应位置旋转四次即可回到原来的位置，所以可以先将最后一个位置的数存起来，然后对数字进行旋转交换，这样就实现了图像的旋转。因为每个像素都旋转四次，因此只有 $1\over 4$ 的像素需要旋转。这样因为每个位置的数只被交换了一次，因此时间复杂度为 $\mathrm O(n ^ 2)$，空间复杂度为 $\mathrm O(1)$。
代码
提交记录：0 ms (100.00%) / 6.99 MB (83.17%)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
for (int i = 0, ed = matrix[0].size() + 1 >> 1; i < ed; ++i)
for (int j = 0, sz = matrix[0].size() - 1, ed = matrix[0].size() >> 1; j < ed; ++j)
for (int k = 0, lst = matrix[sz - j][i]; k < 4; swap(i, j), j = sz - j, ++k)
swap(matrix[i][j], lst);
}
};
LeetCode 73. 矩阵置零
思路
我们可以开两个数组来存储每列和每行是否需要全部置 $0$，然后再执行置 $0$ 的操作。在最后的结果中我们可以发现，如果第一行和第一列如果不被全部置 $0$，则其值是否为 $0$ 刚好对应、也应该对应每个位置所在列和行是否全部置 $0$。
那么我们只要使用变量将第一行和第一列是否全部置 $0$ 单独存起来即可。时间复杂度 $\mathrm O(n ^ 2)$，空间复杂度 $\mathrm O(1)$。
代码
提交记录：8 ms (96.87%) / 13.28 MB (31.10%)
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int row = 1;
for (int j = 0; j < matrix[0].size(); ++j) if (!matrix[0][j]) row = 0;
for (int i = 1; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
if (!matrix[i][j]) matrix[i][0] = 0, matrix[0][j] = 0;
for (int i = 1; i < matrix.size(); ++i)
for (int j = 1; j < matrix[0].size(); ++j)
if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
if (!matrix[0][0]) for (int i = 0; i < matrix.size(); ++i) matrix[i][0] = 0;
if (!row) for (int j = 0; j < matrix[0].size(); ++j) matrix[0][j] = 0;
}
};
LeetCode 289. 生命游戏
思路
为了原地解决这道题，如果我们直接将细胞的状态设置为最终结果会影响后续其他位置的状态更新，因此我们可以考虑使用其他数字来代表不同的状态，如使用 $2$ 表示下个状态中死细胞即将复活，使用 $3$ 来表示活细胞将在下个状态死亡，这样先将所有细胞的下个状态全部计算出来，再遍历一次将 $2$ 和 $3$ 映射到答案的值域 ${0, 1}$ 中，即可原地解决此题。时间复杂度 $\mathrm O(n \times m)$。
代码
提交记录：0 ms (100.00%) / 6.95 MB (54.50%)
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
auto get = [&](int x, int y) {
int ans = 0;
for (int i = -1; i < 2; ++i)
for (int j = -1; j < 2; ++j)
if ((i || j) && x + i >= 0 && x + i < board.size() && y + j >= 0 && y + j < board[0].size() && board[x + i][y + j] & 1) ++ans;
return ans;
};
for (int i = 0; i < board.size(); ++i)
for (int j = 0, x = get(i, j); j < board[0].size(); x = get(i, ++j))
board[i][j] += (board[i][j] ? (x < 2 || x > 3) : (x == 3)) << 1;
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j) board[i][j] = board[i][j] == 1 || board[i][j] == 2;
}
};
