0

「算法刷题」数组之二维矩阵专项汇总(力扣版)

 1 year ago
source link: https://magicdeveloperdrl.github.io/2022/06/11/%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98-%E6%95%B0%E7%BB%84%E4%B9%8B%E4%BA%8C%E7%BB%B4%E7%9F%A9%E9%98%B5%E4%B8%93%E9%A1%B9%E6%B1%87%E6%80%BB-%E5%8A%9B%E6%89%A3%E7%89%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

本文记录作者刷题过程中与二维矩阵相关的题目。

一、蛇形遍历矩阵

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;
    }
};

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK