Java-数据结构-矩阵专题

一. 矩阵简单介绍

        矩阵其实就是一个二维的表格，那么数据结构中的矩阵其实也是一样的，计算机中可以用矩阵这种形式来存储数据。使用二维数组可来存储矩阵。

二. leetcode实战

1. leetcode48 旋转图像

        给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0, k = n-1; j < n/2; j++,k--){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][k];
                matrix[i][k] = temp;
            }
        }
    }
}

2. leetcode54 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

class Solution {
    public List spiralOrder(int[][] matrix) {
        List list = new ArrayList<>();
        int i1 = 0;
        int j1 = 0;
        int i2 = matrix.length-1;
        int j2 = matrix[0].length-1;
        while(i1 <= i2 && j1 <= j2){
            if(i1 == i2){
                while(j1 <= j2) list.add(matrix[i1][j1++]);
            }
            if(j1 == j2){
                while(i1 <= i2) list.add(matrix[i1++][j1]);
            }
            //水平向右
            for(int j = j1; j < j2; j++){
                list.add(matrix[i1][j]);
            }
            //垂直向下
            for(int i = i1; i < i2; i++){
                list.add(matrix[i][j2]);
            }
            //水平向右
            for(int j = j2; j > j1; j--){
                list.add(matrix[i2][j]);
            }
            //垂直向上
            for(int i = i2; i > i1; i--){
                list.add(matrix[i][j1]);
            }
            i1++;
            i2--;
            j1++;
            j2--;
        }
        return list;
    }
}

3. leetcode59 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int i1 = 0;
        int j1 = 0;
        int i2 = n-1;
        int j2 = n-1;
        int cur = 1;
        while(i1<=i2&&j1<=j2){
        //处理只剩一行的情况
        if(i1==i2){
            while(j1<=j2){
                matrix[i1][j1++] = cur++;
            }
        }
        //处理只剩一列的情况
        if(j1==j2){
            while(i1<=i2){
                matrix[i1++][j1] = cur++;
            }
        }
        //从左向右遍历
        for(int j=j1;j
            matrix[i1][j] = cur;
            cur++;
        }
        //从上向下遍历
        for(int i=i1;i
            matrix[i][j2] = cur;
            cur++;
        }
        //从右向左遍历
        for(int j=j2;j>j1;j--){
            matrix[i2][j] = cur;
            cur++;
        }
        //从下向上遍历
        for(int i=i2;i>i1;i--){
            matrix[i][j1] = cur;
            cur++;
        }
        //缩小圈的边界
        i1++;
        j1++;
        i2--;
        j2--;
    }
    return matrix;
    }
}

4. leetcode74 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
 

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int start = 0;
        int end = matrix.length-1;
        while(start < end){
            int mid = (start + end +1)>>1;
            if(matrix[mid][0] <= target){
                start = mid;
            }
            else {
                end = mid-1;
            }
        }
        if(matrix[start][0] == target){
            return true;
        }
        int temp = start;
        start = 0;
        end = matrix[0].length-1;
        while(start <= end){
            int mid = (start + end)>>1;
            if(matrix[temp][mid] > target){
                end = mid - 1;
            }
            else if(matrix[temp][mid] < target){
                start = mid+1;
            }
            else{
                return true;
            }
        }
        return false;
    }
}

5. leetcode498 对角线遍历

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int col = mat.length;
        int row = mat[0].length;
        int[] arr = new int[col*row];
        int cur = 0;
        int i = 0;
        int j = 0;
        boolean flag = true;
        while(cur < col * row){
            if(flag){
                while(i >= 0 && i < col  && j >= 0 && j < row){
                    arr[cur++] = mat[i][j];
                    j++;
                    i--;
                }
            }
            if(!flag){
                while(i >= 0 && i < col  && j >= 0 && j < row){
                    arr[cur++] = mat[i][j];
                    i++;
                    j--;
                }
            }
            if(i < 0){
                if(j >= 0 && j 
                    i++;
                    flag = false;
                }
                else{
                    i += 2;
                    j -= 1;
                    flag = false;
                }
 
            }
            if(j < 0) {
                if (i >= 0 && i < col) {
                    j++;
                    flag = true;
                } else {
                    i--;
                    j += 2;
                    flag = true;
                }
            }
            if(i >= 0 && j == row){
                j--;
                i +=2;
                flag = false;
            }
            if(j >= 0 && i == col){
                i--;
                j +=2;
                flag = true;
            }
        }
        return arr;
    }
}