LeetCode-数组-矩阵问题-中等难度

2023-12-18 10:44:52
@[toc]

矩阵

矩阵是二维数组相关的应用题型,常见的有矩阵水平翻转、矩阵对角线翻转、矩阵遍历等。

1. 重塑矩阵

1.1 题目描述

在这里插入图片描述
leetcode跳转:566. 重塑矩阵

1.2 方法一:简单模拟

借助一个一维数组用来保持按行列遍历的结果,然后再按照新的行列遍历生成即可。

public int[][] matrixReshape(int[][] mat, int r, int c) {
    int m = mat.length;
    int n = mat[0].length;
    if (r * c != m * n) {
        return mat;
    }

    // 按原行列遍历
    int[] temp = new int[r * c];
    int idx = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            temp[idx++] = mat[i][j];
        }
    }

    // 按新行列遍历
    int[][] ans = new int[r][c];
    idx = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            ans[i][j] = temp[idx++];
        }
    }
    return ans;
}

1.3 方法二:原地遍历

方法一的在空间上需要额外开辟一个行×列大小的数组,实际上我们只需要根据行列遍历的一个公式即可完成。

假设有一个4×5的二维数组:
在这里插入图片描述
很明显,每一行的起始位置也就是:0、5、10、15 ,如果我们从下标0开始遍历,一直遍历到第19位的话,那么每一行的起始位置实际上就是:i / 5,而每一列就是i % 5

所以,我们只需要完成的遍历一次数组的长度即可完成矩阵的重塑。

public int[][] matrixReshape(int[][] mat, int r, int c) {
    int m = mat.length;
    int n = mat[0].length;
    if (r * c != m * n) {
        return mat;
    }
    int[][] ans = new int[r][c];
    for (int i = 0; i < r * c; i++) {
        ans[i / c][i % c] = mat[i / n][i % n];
    }
    return ans;
}

2. 转置矩阵

2.1 题目描述

在这里插入图片描述
leetcode跳转:867. 转置矩阵

2.2 方法:模拟

按题意模拟即可,其实就是按行输出,变成按列输出而已。

class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] ans = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[j][i] = matrix[i][j];
            }
        }
        return ans;
    }
}

3. 矩阵置零

3.1 题目描述

在这里插入图片描述

3.2 方法一:辅助标记

比较容易想到的方式就是,额外借助两个数组,用来标记哪些行、哪些列应该为零。

public void setZeroes(int[][] matrix) {
    int[] row = new int[matrix.length];
    int[] col = new int[matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            // 原数组下标为0,则表示下标所在行、列都需要置为0
            if (matrix[i][j] == 0) {
                row[i] = 1;
                col[j] = 1;
            }
        }
    }
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            // 如果行或列为0,则置为0
            if (row[i] == 1 || col[j] == 1) {
                matrix[i][j] = 0;
            }
        }
    }
}

3.3 方法二:原地算法

本题的难点就在于,算法要求你在不使用额外空间的条件下完成,所以很明显你必须直接在原数组上完成置零。
我们可以借助矩阵本身来实现标记。

比如有如下矩阵:

在这里插入图片描述
我们如果就用第一行和第一列作为标记项,当遍历到坐标(1,1)0时,就可以标记(0,1)和(1,0)为0

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (matrix[i][j] == 0) {
            matrix[0][j] = matrix[i][0] = 0;
        }
    }
}

在这里插入图片描述

这样一次遍历结束后,我们再重新遍历一次,只要下标所属的第一行或者第一列为0,则直接置为0

在这里插入图片描述

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (matrix[0][j] == 0 || matrix[i][0] == 0) {
            matrix[i][j] = 0;
        }
    }
}

当然,还需要解决一个问题,就是第一行、第一列本身也有0的情况,比如像下面这样:

在这里插入图片描述
为了区分到底是本身就含有0,还是被其他坐标标记为0的情况,我们还需要预先记录一下第一行、第一列是否含有0

boolean m0_flag = false;
boolean n0_flag = false;
for (int i = 0; i < m; i++) {
    if (matrix[i][0] == 0) {
        n0_flag = true;
        break;
    }
}
for (int i = 0; i < n; i++) {
    if (matrix[0][i] == 0) {
        m0_flag = true;
        break;
    }
}

最后完成其他坐标置0后,再处理第一行和第一列有零的情况即可。

if (m0_flag) {
    for (int i = 0; i < n; i++) {
        matrix[0][i] = 0;
    }
}
if (n0_flag) {
    for (int i = 0; i < m; i++) {
        matrix[i][0] = 0;
    }
}

完整代码实现如下:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean m0_flag = false;
        boolean n0_flag = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                n0_flag = true;
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                m0_flag = true;
                break;
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (m0_flag) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
        if (n0_flag) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

4. 旋转图像

4.1 题目描述

在这里插入图片描述

4.2 方法一:模拟一

先从最后一行开始,按行遍历:7,8,9,4,5,6,1,2,3,再从第一列开始,按列写入即可。

class Solution {
	public void rotate(int[][] matrix) {
		int n = matrix.length;
		int[][] helper = new int[n][n];
		for(int i = n - 1; i >= 0; i--){
			for(int j = 0; j < n; j++){
				helper[j][n - 1 - i] = matrix[i][j];
			}
		}

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				matrix[i][j] = helper[i][j];
			}
		}
	}
}

4.3 方法二:模拟二

我们还可以只用一个一维数组来模拟这样的输出方式。

class Solution {
	public void rotate(int[][] matrix) {
		int n = matrix.length;
		int[] helper = new int[n * n];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				helper[n * i + j] = matrix[i][j];
			}
		}
		// helper:1 2 3 4 5 6 7 8 9
		// 从最后一行开始,按列遍历
		// 7 4 1
		// 8 5 2
		// 9 6 3
		int idx = helper.length - 1;
		for(int i = 0; i < n; i++){
			for(int j =  n - 1; j >= 0; j--){
				matrix[j][i] = helper[idx--];
			}
		}
	}
}

4.4 方法三:原地算法

按照本题要求,请你尝试在不占用额外内存空间的情况下完成旋转。

步骤一:我们可以先完成一次水平翻转,也就上下行交换。

在这里插入图片描述
步骤二:然后再按照对角线进行翻转即可。
在这里插入图片描述
代码实现如下:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < n; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        
        // 对角线翻转
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

5. 螺旋矩阵

5.1 题目描述

在这里插入图片描述
本题主要考察的还是编码和思维能力,按题意模拟即可,没有什么技巧可言。

我们采用按前进方向进行模拟,分别定义上下左右四个方向,那么前进路线以此就为:左→右、上→下、右→左、下→上

在这里插入图片描述
按照四个方向来模拟这个思路非常容易想到,关键在于能不能想的清楚四个方向分别表示的含义是什么?

下面给出四个方向的定义:
在这里插入图片描述
所以,从left走到right的方式如下所示:

for (int i = left; i <= right; i++) {
	ans.add(matrix[top][i]);
}

top走到bottom的方式如下所示:

for (int i = top + 1; i <= bottom; i++) {
	ans.add(matrix[i][right]);
}

right走到left的方式如下所示:

for (int i = right - 1; i > left; i--) {
	ans.add(matrix[bottom][i]);
}

最后,从bottom走到top的方式如下所示:

for (int i = bottom; i > top; i--) {
	ans.add(matrix[i][left]);
}

5.2 方法:模拟

public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = m - 1;
        // 用来记录已经走的步数
        int step = 0;
        List<Integer> ans = new ArrayList<>();
        while (step < m * n) {
            for (int i = left; i <= right; i++) {
                if (step < m * n) {
                    ans.add(matrix[top][i]);
                    step++;
                }
            }
            for (int i = top + 1; i <= bottom; i++) {
                if (step < m * n) {
                    ans.add(matrix[i][right]);
                    step++;
                }
            }
            for (int i = right - 1; i > left; i--) {
                if (step < m * n) {
                    ans.add(matrix[bottom][i]);
                    step++;
                }
            }
            for (int i = bottom; i > top; i--) {
                if (step < m * n) {
                    ans.add(matrix[i][left]);
                    step++;
                }
            }
            // 一圈走完以后,更新每个方向
            left++;
            right--;
            top++;
            bottom--;
        }
        return ans;
    }

文章来源:https://blog.csdn.net/CSDN_WYL2016/article/details/135043273
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。