目录
一、最富有客户的资产数量
1.题目
给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
返回最富有客户所拥有的 资产总量 。
m == accounts.length
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100
2.分析
这道题简单来说就是返回二维数组中，各个子数组所有数之和的最大值。
- 二维数组的行数（数组个数）：accounts.length
- 二维数组的列数（对应子数组的长度）：accounts[i].length
3.代码
public int maximumWealth(int[][] accounts) {
int max = 0;
for (int i = 0;i < accounts.length;i++){
int sum = 0;
for (int j = 0;j < accounts[i].length;j++){
sum += accounts[i][j];
}
if (sum > max){
max = sum;
}
}
return max;
}
二、二进制矩阵中的特殊位置
1.题目
给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从0 开始 ），则位置 (i, j) 被称为特殊位置。
rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] 是 0 或 1
2.分析
这道题首先想到的思路就是：
- 遍历所有的位置，当有一个位置为1，则再分别遍历该位置对应行和对应列，如果都不为1，则计数加1。接着遍历下一个点。
然而，再仔细想一下，发现了一些规律：
- 根据给出的特殊位置的定义，每行最多只能有1个特殊位置，且每列也最多只能有1个特殊位置。
所以只要判定某个为1的位置不是特殊位置，该行该列的其他位置在遍历时都可以直接跳过，以减少遍历次数。
3.代码
public int numSpecial(int[][] mat) {
//定义遍历的下标
int j,i = 0;
//矩阵行数
int rows = mat.length;
//矩阵列数
int cols = mat[i].length;
//特殊位置个数
int count = 0;
for (i = 0;i < rows;i++){
inner:
for (j = 0;j < cols;j++){
if (mat[i][j] == 1){
//遍历i行的所有列，除特殊位置外还有位置为1，则直接跳出当前行循环
for (int col = 0;col < cols;col++){
if (col == j){
continue;
} else if (mat[i][col] == 1){
break inner;
}
}
//遍历j列的所有行，除特殊位置外还有位置为1，则直接跳出当前行循环
for (int row = 0;row < rows;row++){
if (row == i){
continue;
} else if (mat[row][j] == 1){
break inner;
}
}
//如果为特殊位置，计数加1
count++;
}
}
}
return count;
}
三、翻转图像
1.题目
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
2.分析
以其中一个子数组水平翻转并翻转图像为例：
- 定义两个变量 j = 0 和 k = image[ i ].length - 1，分别为数组的首尾下标。
- 水平翻转：其实就是数组的首尾交换，交换后首下标加1，尾下标减1，直到 j < k 为止。
- 反转图像：因为数组中的数只有 0 和 1，所以可以通过水平翻转后，用 （1 - 水平翻转后的值） 来实现。
3.代码
public int[][] flipAndInvertImage(int[][] image) {
for (int i = 0;i < image.length;i++){
int j = 0;
int k = image[i].length - 1;
while (j <= k){
int t = image[i][j];
image[i][j] = 1- image[i][k];
image[i][k] = 1 - t;
j++;
k--;
}
}
return image;
}
四、旋转图像
1.题目
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
2.分析
这道题自己想得有些复杂，参考了力扣大佬的思路：
- 顺时针旋转90° = 转置矩阵的元素以左右对称的形式互换
3.代码
public void rotate(int[][] matrix) {
int n = matrix.length;
//先变成转置矩阵
for (int i = 0;i < n;i++){
for (int j = 0;j < i;j++){
int t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
}
//转置矩阵左右对称交换元素得到旋转90度后的矩阵
for (int i = 0;i < n;i++){
for (int j = 0;j < n / 2;j++){
int t = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = t;
}
}
}
五、转置矩阵
1.题目
给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。
矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
-109 <= matrix[i][j] <= 109
2.分析
转置矩阵放到二维数组中，实际上就是行列下标的互换：
- 定义二维数组，用来存放转置矩阵的元素。
- 原矩阵的行下标作为转置矩阵的列下标，原矩阵的列下标作为转置矩阵的行下标，将元素存到转置矩阵的二维数组中。（行变列，列变行）
3.代码
public int[][] transpose(int[][] matrix) {
int j,i = 0;
//原矩阵行数
int rows = matrix.length;
//原矩阵列数
int cols = matrix[i].length;
//转置矩阵
int[][] trans = new int[cols][rows];
for (i = 0;i < rows;i++){
for (j = 0;j < cols;j++){
trans[j][i] = matrix[i][j];
}
}
return trans;
}
六、将一维数组变成二维数组
1.题目
给你一个下标从 0 开始的一维整数数组 original 和两个整数 m 和 n 。你需要使用 original 中 所有 元素创建一个 m 行 n 列的二维数组。
original 中下标从 0 到 n - 1 （都 包含 ）的元素构成二维数组的第一行，下标从 n 到 2 * n - 1（都包含）的元素构成二维数组的第二行，依此类推。
请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。
1 <= original.length <= 5 * 104
1 <= original[i] <= 105
1 <= m, n <= 4 * 104
2.分析
- 在遍历一维数组前，先判断该数组是否能构成m 行 n 列的二维数组。能将一维数组构成二维数组，必定符合：一维数组长度 original.length = m * n
- 定义二维数组以及初始行和列下标 row，col
- 遍历一维数组，将该数组的元素存放到二维数组中，每次存放完一个元素，col 加1。
- 当 col = n 时，说明当前行已经放满，则换到下一行的起始位置，即 row加1，col = 0，直到遍历结束。
3.代码
public int[][] construct2DArray(int[] original, int m, int n) {
if (m * n != original.length){
return new int[][]{};
}
//定义一个二维数组
int[][] result = new int[m][n];
//二维数组的起始行和列下标
int row = 0;
int col = 0;
for (int i = 0;i < original.length;i++){
result[row][col] = original[i];
col++;
if (col == n){
row++;
col = 0;
}
}
return result;
}
七、判断矩阵经轮转后是否一致
1.题目
给你两个大小为 n x n 的二进制矩阵 mat 和 target 。
现以90度顺时针轮转矩阵 mat中的元素若干次，如果能够使mat与target一致，返回 true；否则，返回 false 。
n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] 和 target[i][j] 不是 0 就是 1
2.分析
这道题我只能做出来，但是更优的方法实在是想不到了。
思路：
- 每次旋转90°，所以最多旋转3次。
- 判断两个矩阵是否一样的方法：通过将2个矩阵的同一行元素以字符串形式判断是否相同（每一行就是一个数组，即将同一行的数组元素变成字符串来比较，用 Arrays.toString(int[] a) 方法实现）。
- 判断两个矩阵是否一样（逐行判断数组元素的字符串是否相同）：
如果判断有其中一行不相同，则旋转90°，并跳到下一循环。
如果旋转了3次还有不同，则返回false。
只要判断其中有一次全部相同，则返回true。
3.代码
public boolean findRotation(int[][] mat, int[][] target) {
int rows = mat.length;
//最多90°旋转3次
outer:
for(int n = 0;n <= 3;n++){
for (int i = 0;i < rows;i++){
//如果有一行不相等，旋转90°
if (!Arrays.toString(mat[i]).equals(Arrays.toString(target[i]))){
for (int j = 0;j < rows;j++){
for (int k = 0;k < j;k++){
int t = mat[j][k];
mat[j][k] = mat[k][j];
mat[k][j] = t;
}
}
for (int j = 0;j < rows;j++){
for (int k = 0;k < rows / 2;k++){
int t = mat[j][k];
mat[j][k] = mat[j][rows - k - 1];
mat[j][rows - k - 1] = t;
}
}
continue outer;
}
}
//循环结束也没有break，说明每行数据都一致，则返回true
return true;
}
//经过三次循环也没有一次元素全部相同，返回false
return false;
}
八、二维网格迁移
1.题目
给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
每次「迁移」操作将会引发下述活动：
位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。
m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
2.分析
方法一：每次遍历往后迁移一步，直到迁移k步
- 一开始我就是用的这种比较简单的方法。但是，虽然通过了，执行效率却不高。
- 我知道应该想办法在迁移的时候就一次迁移到k步的位置，但是迟迟找不到规律所在，后来总算让我想到了~
方法二：将迁移后的二维数组元素存到定义的一维数组中
- 定义一维数组，遍历的时候，将二维数组的元素赋值到一维数组迁移k步后的位置（迁移前：二维数组的(0,0)对应一维数组的下标0位置）
- 一维数组长度为 ：行数 * 列数（m * n）
- 防止 k 大于一维数组长度出现数组越界，当 k 大于等于一维数组长度，k需要再从下标0开始数：所以 k %= (行数 * 列数)
- 遍历一维数组存入集合List时，可以模仿遍历二维数组的方式，但取值是取一维数组的值
3.代码
方法一：每次遍历往后迁移一步，直到迁移k步
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int a = 0;
int m = grid.length;
int n = grid[a].length;
for (int i = 1;i <= k;i++){
//将二维网格最后一个数取出暂存
int tem = grid[m - 1][n - 1];
for (a = 0;a < m;a++){
for (int b = 0;b < n;b++){
//遍历位置的数和暂存tem的数交换
int t = grid[a][b];
grid[a][b] = tem;
tem = t;
}
}
}
//存到List集合
List<Integer> list = null;
List<List<Integer>> list2 = new ArrayList<>();
for (int i = 0; i < m; i++) {
list = new ArrayList<>();
for (int j = 0; j < n; j++) {
list.add(grid[i][j]);
}
list2.add(list);
}
return list2;
}
方法二：将迁移后的二维数组元素存到定义的一维数组中
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int a = 0;
int m = grid.length;
int n = grid[a].length;
//把二维数组转换成一维数组
int[] g = new int[m * n];
for (int i = 0;i < m;i++){
for (int j = 0;j < n;j++){
//防止迁移大于 m * n步
if (k >= g.length){
k %= g.length;
}
g[k] = grid[i][j];
k++;
}
}
//存到List集合
List<Integer> list = null;
List<List<Integer>> list2 = new ArrayList<>();
for (int i = 0; i < m; i++) {
list = new ArrayList<>();
for (int j = 0; j < n; j++) {
list.add(g[j + i * n]);
}
list2.add(list);
}
return list2;
}