本文记录作者刷题过程中与二维矩阵相关的题目。
一、蛇形遍历矩阵
HJ35 蛇形矩阵
#include <bits/stdc++.h>
using namespace std;
int main(){
// 获取输入
int n;
cin>>n;
// 间隔变，计算各个数字
int beg=1;// 每行的开始数字
for(int i=1;i<=n;i++)// 每次增加的间隔越来越大
{
cout<<beg;
int tmp = beg;// 每行中的数
for(int j=i+1;j<=n;j++)// 每次增加的间隔越来越大
{
tmp+=j;
cout<<" "<<tmp;
}
cout<<endl;
beg+=i;
}
}
二、旋转矩阵
48. 旋转图像（中等难度）
class Solution {
public:
/*
123 147 741
456 ->(转置) 258 -> (水平翻转）852
789 369 963 */
void rotate(vector<vector<int>>& matrix) {
int m = matrix.size();//题目保证m>=1
//int n = matrix[0].size();// 题目保证m==n
// 转置
for(int i=0;i<m;i++){
for(int j=0;j<i;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
// 水平翻转
for(int i=0;i<m;i++){
for(int j=0;j<m/2;j++){
swap(matrix[i][j],matrix[i][m-1-j]);
}
}
}
};
三、矩阵匹配字符串
79. 单词搜索（中等难度）
剑指 Offer 12. 矩阵中的路径（中等难度）
class Solution {
public:
// 判断board[i][j]==word[k]
bool dfs(vector<vector<char>>& board, string word,int i,int j,int k){
if(i<0||i>=board.size()) return false;// 检查行边界
if(j<0||j>=board[0].size()) return false;// 检查列边界
if(board[i][j]!=word[k]) return false;// 检查当前矩阵元素==字符
if(k==word.length()-1) return true;// 检查k是否是最后一个元素
board[i][j]='#';// 此时和word[k]相等，设为特殊字符，代表已访问过
// 检查当前矩阵元素的上左下右共计四个方向是否存在下一个匹配
bool res=dfs(board, word, i, j-1, k+1)
|| dfs(board, word, i-1, j, k+1)
|| dfs(board, word, i, j+1, k+1)
|| dfs(board, word, i+1, j, k+1);
board[i][j]=word[k];// 回溯，修复为原来的元素
return res;
}
bool exist(vector<vector<char>>& board, string word) {
// 双重循环，覆盖所有情况
for(int i=0;i<board.size();++i){
for(int j=0;j<board[0].size();++j){
if(dfs(board,word,i,j,0)) return true;
}
}
return false;
}
};
四、检查矩阵元素
剑指 Offer 13. 机器人的运动范围（中等难度）
class Solution {
public:
bool isEnter(int i,int j,int k){
int sum=0;
while(i){
sum+=i%10;
i/=10;
}
while(j){
sum+=j%10;
j/=10;
}
return sum<=k;
}
int dfs(int m,int n,int i,int j,int k,vector<vector<bool>> & visited){
int res=0;
if(i<0||i>=m) return res;//行超界
if(j<0||j>=n) return res;//列超界
if(!isEnter(i, j, k)) return res;//当前格子不可进入
if(visited[i][j]) return res;//当前格子已经访问过
visited[i][j]=true;//标记当前格子已访问
res+=1;//当前格子可进入
res+=dfs(m, n, i+1, j, k,visited);//右一格是否可进入
res+=dfs(m, n, i, j+1, k,visited);//下一格是否可进入
return res;
}
int movingCount(int m, int n, int k) {
vector<vector<bool>> visited(m,vector(n,false));//二维bool数组
return dfs(m,n,0,0,k,visited);
}
};
五、查找有序矩阵
剑指 Offer 04. 二维数组中的查找
240. 搜索二维矩阵 II（中等难度）
方法一：深度优先遍历
class Solution {
public:
bool dfs(vector<vector<int>> & matrix,int target,int i,int j){
if(i<0||i>=matrix.size()) return false;//行超界
if(j<0||j>=matrix[0].size()) return false;//列超界
if(matrix[i][j]==target) return true;//当前元素就是目标值
bool res=false;
// 如果当前元素大，说明应该左移
if(matrix[i][j]>target){
res=dfs(matrix, target, i, j-1);//左一格
}
// 如果当前元素小，说明应该下移
else{
res=dfs(matrix, target,i+1, j);//下一格
}
return res;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0) return false;
return dfs(matrix,target,0,matrix[0].size()-1);//从右上角遍历到左下角
}
};
五、螺旋遍历矩阵
54. 螺旋矩阵（中等难度）
剑指 Offer 29. 顺时针打印矩阵（简单难度）
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res; // 结果数组
int m=matrix.size();
if(m==0) return res;
int n=matrix[0].size();
// 定义界限
int numEle = m*n; //矩阵中的元素个数
int left = 0,top = 0;
int right = n - 1,bottom = m - 1;
// 按照元素个数进行4个方向的遍历
while(numEle){
// 上行从左到右，固定top行，遍历[left,right]
for(int i=left;i<=right&&numEle>0;i++){
res.push_back(matrix[top][i]);
numEle--;
}
top++;
// 右列从上到下，固定right列,遍历[top,bottom]
for(int i=top;i<=bottom&&numEle>0;i++){
res.push_back(matrix[i][right]);
numEle--;
}
right--;
// 下行从右到左，固定bottom行,遍历[right,left]
for(int i=right;i>=left&&numEle>0;i--){
res.push_back(matrix[bottom][i]);
numEle--;
}
bottom--;
// 左列从下到上，固定left列,遍历[bottom,top]
for(int i=bottom;i>=top&&numEle>0;i--){
res.push_back(matrix[i][left]);
numEle--;
}
left++;
}
return res;
}
};
59. 螺旋矩阵 II（中等难度）
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n,vector<int>(n,0));// 使用vector定义一个固定长度的二维数组
int count =1; // 用来给矩阵中每一个空格赋值
int numEle = n*n; //矩阵中的元素个数
int left = 0,top = 0;
int right = n - 1, bottom = n - 1;
while(numEle>0){
// 上行从左到右，固定top行，遍历left-right
for(int i=left;i<=right&&numEle>0;i++){
res[top][i]=count++;
numEle--;
}
top++;
// 右列从上到下，固定right列
for(int i=top;i<=bottom&&numEle>0;i++){
res[i][right]=count++;
numEle--;
}
right--;
// 下行从右到左，固定bottom行
for(int i=right;i>=left&&numEle>0;i--){
res[bottom][i]=count++;
numEle--;
}
bottom--;
// 左列从下到上，固定left列
for(int i=bottom;i>=top&&numEle>0;i--){
res[i][left]=count++;
numEle--;
}
left++;
}
return res;
}
};