🍗课后习题
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，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
思路
从第一行开始往下扫描就好了。但是注意长度为奇数的时候中间会多加，但是偶数不会！
i
nt 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; }
