36题.有效的数独
此类问题特点是给出行列的多种限定条件,数独限制每行每列每个小九宫格元素范围为1-9且不可重复 。解决此类问题最简单的想法就是使用哈希set,记录每行,每列,每个小九宫格已经出现的元素。在遍历矩阵时提前做出是否重复的判断,若重复一次则直接退出遍历返回假。
作为哈希set的优化可以使用多维数组存储已经遍历过的元素的数量,只要对应位置上的计数小于等于一则继续遍历,否则直接退出。本质是将遍历到的元素根据其值大小转换到一个对应的位置上,例如值为1,则将值为1的所有数据位置固定在0。建立多个多维数组跟踪行、列、小九宫格的元素重复情况。
Note:对于小九宫格的定位为题是一个常见的套路,因为9乘9矩阵被划分为3乘3的九宫格,所以可以使用[i / 3][j / 3]去定位九宫格。
多维数组做法:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int colum[9][9], row[9][9], box[3][3][9];
memset(colum, 0, sizeof(colum));
memset(row, 0, sizeof(row));
memset(box, 0, sizeof(box));
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
char board_ij = board[i][j];
if(board_ij != '.'){
int tmp = board_ij - '0' - 1;
++colum[j][tmp];
++row[i][tmp];
++box[i / 3][j / 3][tmp];
if(colum[j][tmp] > 1 || row[i][tmp] > 1 || box[i / 3][j / 3][tmp] > 1)
return false;
}
}
}
return true;
}
};
哈希set:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<unordered_set<char>> row(9, unordered_set<char>());
vector<unordered_set<char>> colum(9, unordered_set<char>());
vector<vector<unordered_set<char>>> box(3, vector<unordered_set<char>>(3, unordered_set<char>()));
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
char tmp = board[i][j];
if(tmp != '.'){
if(row[i].count(tmp) == 0 && colum[j].count(tmp) == 0 && box[i / 3][j / 3].count(tmp) == 0){
row[i].insert(tmp);
colum[j].insert(tmp);
box[i / 3][j / 3].insert(tmp);
}
else
return false;
}
}
}
return true;
}
};
54.螺旋矩阵
此类问题在实际场景中使用较多,例如旋转图片等。通常为顺时针或者逆时针旋转矩阵,做法很简单。定义上下左右四个边界,在模拟的过程中更新边界即可。即保障先从左到右然后从上到下再者从右到左,最后从下到上。定义u(up) d(down) l(left) r(right)为其上下左右边界,在模拟的过程中更新边界即可。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int u = 0, d = m - 1, l = 0, r = n - 1;
vector<int> res;
while (true) {
for (int i = l; i <= r; ++i)
res.emplace_back(matrix[u][i]);
if(++u > d) break;
for (int i = u; i <= d; ++i)
res.emplace_back(matrix[i][r]);
if(--r < l) break;
for (int i = r; i >= l; --i)
res.emplace_back(matrix[d][i]);
if(--d < u) break;
for (int i = d; i >= u; --i)
res.emplace_back(matrix[i][l]);
if(++l > r) break;
}
return res;
}
};
48.旋转图像问题
此类问题需求是把一个矩阵旋转某角度,需要进行坐标转换即可轻松解决。也可以设计原地旋转的算法。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> help(matrix);
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
matrix[j][n - 1 -i] = help[i][j];
}
}
}
};