[数据结构与算法]【解题报告】《LeetCode零基础指南》(第八讲) 二维数组

?前言?

今天是九日集训第七天，我会记录一下学习内容和题解，争当课代表0.0.
链接：《LeetCode零基础指南》(第八讲) 二维数组

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?全文大约阅读时间： 20min

🎁主要知识点梳理

📝1.矩阵的定义

矩阵A_mxn 定义的是按照长方阵列排列的负数或者实数集合，其中n表示行数，m代表列数。入下图所示为一个4x3的矩阵
$$A_{4x3}=?\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}?$$
在c语言我们可以用二维数组A[n][m]代表一个nxm 矩阵，其中``A[i][j]代表第 i行，第j列元素。

🍭2.矩阵的水平翻转

矩阵的水平翻转就是将矩阵每一行元素逆序。
$$A_{4x3}=?\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}??A_{4x3}^{{}^{\prime }}=?\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\\ 0& 0& 1\end{array}?$$

🍜3.矩阵的垂直翻转

矩阵的垂直翻转就是将矩阵每一列元素逆序。
$$A_{4x3}=?\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}??A_{4x3}^{{}^{\prime \prime }}=?\begin{array}{ccc}1& 0& 0\\ 1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}?$$

🍡4.矩阵的顺时针旋转

矩阵的顺时针旋转 90度，顾名思义就是绕着垂直于屏幕方向进行90旋转。
$$A_{4x3}=?\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}??A_{3x4}^{{}^{\prime \prime \prime }}=?\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}?$$

🍛5.矩阵的逆时针旋转

逆时针转90度就是顺时针转270。

🍣6.矩阵的逆时针转置

就是对矩阵的对角线进行交换操作。
$$A_{4x3}=?\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}??A_{3x4}^T=?\begin{array}{cccc}0& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}?$$

🍢7.二维数组的函数传参

int diagonalSum(int** mat, int matSize, int* matColSize){
}

其中第一个matSize代表行数，而matColSize代表的是每行的元素个数。所以是一个数组matColSize[0]就是第0行有多少个元素。
一般写法：

int diagonalSum(int** mat, int matSize, int* matColSize){
   r = matSize;
   c = matColSize[0];
   // TODO
}

🍗课后习题

1351. 统计有序矩阵中的负数

1351. 统计有序矩阵中的负数

题目描述

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
请你统计并返回 grid 中 负数 的数目。

思路

利用二分去寻找第一个负数元素，同时因为按列也是非递增，所以high的值不用每次去修改，只将low拉低就行了。

int countNegatives(int** grid, int gridSize, int* gridColSize){
    int low = 0,high = gridColSize[0],ans=  0;
    for(int i = 0;i < gridSize;i++){
        low = 0;
        while(low<high){
            int mid = (low + high) /2;
            if(grid[i][mid] >= 0) low = mid + 1;
            else high = mid;
        }
        ans += gridColSize[i] - high;
    }
    return ans;
}

1572. 矩阵对角线元素的和

1572. 矩阵对角线元素的和

题目描述

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

思路

从第一行开始往下扫描就好了。但是注意长度为奇数的时候中间会多加，但是偶数不会！

int diagonalSum(int** mat, int matSize, int* matColSize){
    int ans = 0;
    for(int i = 0;i < matSize;i++)
        ans += mat[i][i] + mat[i][matSize - 1 - i];
    if(matSize & 1) ans -= mat[matSize/2][matSize/2];
    return ans;
}

1672. 最富有客户的资产总量

1672. 最富有客户的资产总量

题目描述

给你一个 m x n的整数网格accounts ，其中accounts[i][j]是第 i???????????? 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

思路

直接扫描记录最大值就好了呗？

int maximumWealth(int** accounts, int accountsSize, int* accountsColSize){
    int maxn = 0,temp;
    for(int i = 0;i < accountsSize; ++i){
        temp = 0;
        for(int j = 0;j < *accountsColSize; ++j) temp += accounts[i][j];
        if(temp > maxn) maxn = temp;
    }
    return maxn;
}

1672. 766. 托普利茨矩阵

766. 托普利茨矩阵

题目描述

给你一个m x n的矩阵matrix。如果这个矩阵是托普利茨矩阵，返回 true；否则，返回false。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

思路

提示给了我个信息，每次只能读入一行，那么就是每次扫描一行，然后和上一行元素对比就好了。

bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize){
    for(int i = 1;i < matrixSize;i++)
        for(int j = 1;j<matrixColSize[0];j++)
            if(matrix[i][j] != matrix[i-1][j-1])    return false;
    return true;
}

1380. 矩阵中的幸运数

1380. 矩阵中的幸运数

题目描述

给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
幸运数是指矩阵中满足同时下列两个条件的元素：

• 在同一行的所有元素中最小
• 在同一列的所有元素中最大

思路

根据每行元素元素的最大值去看是否是一列的最大值就好了？

int* luckyNumbers (int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
    int *ans = malloc(sizeof(int)*matrixSize),ansnum = 0;
    for(int i = 0;i < matrixSize;i++){
        int min = matrix[i][0],minj = 0;
        for(int j = 1;j < matrixColSize[0];j++)
            if(matrix[i][j] < min)  min = matrix[i][j],minj = j;
        int k = 0;
        for(;k < matrixSize;k++)
            if(matrix[k][minj] > min)   break;
        if(k == matrixSize)
            ans[ansnum++] = min;
    }
    *returnSize = ansnum;
    return ans;
}

1582. 二进制矩阵中的特殊位置

1582. 二进制矩阵中的特殊位置

题目描述

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

思路

扫描每一个格子。如果四周没有块就是4条边，如果有一个就是3条。依次减少。

int numSpecial(int** mat, int matSize, int* matColSize){
    int ans = 0;
    int hash[*matColSize];
    for(int j = 0; j < *matColSize; ++j){
        hash[j] = 0;
        for(int i = 0;i <matSize;i++)
            if(mat[i][j] == 1)  hash[j] ++;
    }
    for(int i = 0;i < matSize; ++i){
        int temp = 0,tempi = -1;
        for(int j = 0; j < *matColSize; ++j)
            if(mat[i][j] == 1)  temp++,tempi = j;
        if(temp == 1)
            if(hash[tempi] == 1)    ans++;
    }
    return ans;
}

463. 岛屿的周长

463. 岛屿的周长

题目描述

给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。

特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。

思路

提示给了我个信息，每次只能读入一行，那么就是每次扫描一行，然后和上一行元素对比就好了。

int islandPerimeter(int** grid, int gridSize, int* gridColSize){
    int ans = 0;
    for(int i = 0;i < gridSize;i++)
        for(int j = 0;j < gridColSize[0];j++)
            if(grid[i][j] == 1){
                int temp = 4;
                if(i > 0 && grid[i-1][j])   temp--;
                if(i < (gridSize - 1) && grid[i+1][j])  temp--;
                if(j > 0 && grid[i][j-1])   temp--;
                if(j < (gridColSize[0] - 1) && grid[i][j+1])    temp--;
                ans+=temp;
            }
    return ans;
}

📑写在最后
今天完成了第七天的打卡，最近被六级支配，我要鸽几天，没意见吧。只有必要的会更新，自定义打卡每天需要至少四小时，太久了，考完六级我肯定更新-.-