LeetCode算法练习top100：（3）矩阵

雨点打透心脏的1/2处 2024-02-18 11:12 14阅读 0赞

### 矩阵 ###

package top100.top矩阵;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class TOP {
        
        //73. 矩阵置零
        //额外空间将有0的行列存储下来，再置0
        public void setZeroes(int[][] matrix) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            boolean[] row = new boolean[m];
            boolean[] col = new boolean[n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (matrix[i][j] == 0) {
        
                        row[i] = col[j] = true;
                    }
                }
            }
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (row[i] || col[j]) {
        
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    
    
        //54. 螺旋矩阵
        //直接转圈遍历，每遍历行或列，就修改行列的索引
        public List<Integer> spiralOrder(int[][] matrix) {
        
            List<Integer> res = new ArrayList<>();
            int m = matrix.length, n = matrix[0].length;
            int top = 0, bottom = m - 1, left = 0, right = n - 1; //定义四个边界，遍历完边界，更新边界
            int count = m * n; //元素个数
            while (count > 0) {
        
                //遍历top行
                for (int i = left; i <= right && count > 0; i++) {
        
                    res.add(matrix[top][i]);
                    count--;
                }
                top++;
                //遍历right列
                for (int i = top; i <= bottom && count > 0; i++) {
        
                    res.add(matrix[i][right]);
                    count--;
                }
                right--;
                //遍历bottom行
                for (int i = right; i >= left && count > 0; i--) {
        
                    res.add(matrix[bottom][i]);
                    count--;
                }
                bottom--;
                //遍历left列
                for (int i = bottom; i >= top && count > 0; i--) {
        
                    res.add(matrix[i][left]);
                    count--;
                }
                left++;
            }
            return res;
        }
    
        //48. 旋转图像
        //只能靠找规律了
        //先上下交换，再对角线交换
        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 v = matrix[n - i - 1][j];
                    matrix[n - i - 1][j] = matrix[i][j];
                    matrix[i][j] = v;
                }
            }
            //对角线交换
            for (int i = 0; i < n; i++) {
        
                for (int j = i + 1; j < n; j++) {
        
                    int v = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = v;
                }
            }
        }
    
        //240. 搜索二维矩阵 II
        //一看到搜索和排序，就联想到2分法
        public boolean searchMatrix(int[][] matrix, int target) {
        
            int m = matrix.length, n = matrix[0].length;
            int i = m - 1, j = 0; //从左下角开始搜索
            while (i >= 0 && j < n) {
        
                if (matrix[i][j] > target) {
        
                    i--;
                } else if (matrix[i][j] < target) {
        
                    j++;
                } else {
        
                    return true;
                }
            }
            return false;
        }
    }