一，有效的数独
36. 有效的数独 - 力扣（LeetCode）
https://leetcode.cn/problems/valid-sudoku/
1，一次遍历（哈希表）
有效的数独满足以下三个条件：
同一个数字在每一行只能出现一次；
同一个数字在每一列只能出现一次；
同一个数字在每一个小九宫格只能出现一次。
可以使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数。只需要遍历数独一次，在遍历的过程中更新哈希表中的计数，并判断是否满足有效的数独的条件即可。
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int rows[9][9]; int columns[9][9]; int subboxes[3][3][9]; memset(rows,0,sizeof(rows)); memset(columns,0,sizeof(columns)); memset(subboxes,0,sizeof(subboxes)); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c != '.') { int index = c - '0' - 1; rows[i][index]++; columns[j][index]++; subboxes[i / 3][j / 3][index]++; if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) { return false; } } } } return true; } };
复杂度分析
时间复杂度：O(1)。数独共有 81 个单元格，只需要对每个单元格遍历一次即可。
空间复杂度：O(1)。由于数独的大小固定，因此哈希表的空间也是固定的。
二，矩阵归零
73. 矩阵置零 - 力扣（LeetCode）
https://leetcode.cn/problems/set-matrix-zeroes/
1，使用标记数组
思路和算法
我们可以用两个标记数组分别记录每一行和每一列是否有零出现。
具体地，我们首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。最后我们再次遍历该数组，用标记数组更新原数组即可。
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector<int> row(m), col(n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!matrix[i][j]) { row[i] = col[j] = true; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (row[i] || col[j]) { matrix[i][j] = 0; } } } } };
复杂度分析
时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。
