hot100 | 六、矩阵

1-leetcode73. 矩阵置零

注意：×

1. 注意第一行和第一列如果检查到了0，直接break
2. 也可以使用HashSet方法，直接把0的数字对应的横纵坐标放在两个不同的HashSet当中，最后如果HashSet中Contain了当前数字下标中的一个，就直接给0

    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int firstRowFlag = 0, firstColFlag = 0;
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) {
                firstColFlag = 1;
                break;
            }
        }

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

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

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

        if (firstRowFlag == 1){
            Arrays.fill(matrix[0], 0);
        }
        
        if (firstColFlag == 1){
            for (int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }

    }

2-leetcode54. 螺旋矩阵

注意：×

1. 看了Labuladong的解题思路，确实是一道没写过的不会，写过的很难忘的一道题
2. 注意各个边界的调整即可，思路应该不会再忘的

    public List<Integer> spiralOrder(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int upSide = 0, downSide = n - 1;
        int leftSide = 0, rightSide = m - 1;

        ArrayList<Integer> res = new ArrayList<>();
        while (res.size() < m*n){
            if (upSide <= downSide){
                for (int i = leftSide; i <= rightSide; i++) {
                    res.add(matrix[upSide][i]);
                }
                upSide++;
            }
            
            if (leftSide <= rightSide){
                for (int i = upSide; i <= downSide; i++) {
                    res.add(matrix[i][rightSide]);
                }
                rightSide--;
            }

            if (upSide <= downSide){
                for (int i = rightSide; i >= leftSide; i--) {
                    res.add(matrix[downSide][i]);
                }
                downSide--;
            }

            if (leftSide <= rightSide){
                for (int i = downSide; i >= upSide; i--) {
                    res.add(matrix[i][leftSide]);
                }
                leftSide++;
            }
        }
        return res;
    }

3-leetcode48. 旋转图像

注意：×

1. 注意对角线遍历是for(i = 0) for(j = i)

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

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

        for (int[] ma : matrix) {
            reverse(ma);
        }
    }

    private void reverse(int[] ma) {
        int n = ma.length;
        int left = 0;
        int right = n-1;
        while (left<right){
            int temp = ma[left];
            ma[left] = ma[right];
            ma[right] = temp;
            left++;
            right--;
        }
    }

4-leetcode240. 搜索二维矩阵 II

注意：×

1. 看完解析就会了，主要是思路

    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;

        // 从最右上角开始便利，如果比目标数字大，就往左边走，如果比目标数字小，就往下面走
        int iIndex = 0;
        int jIndex = m - 1;
        while (iIndex < n && jIndex >= 0){
            if (matrix[iIndex][jIndex] == target){
                return true;
            }else if (matrix[iIndex][jIndex] > target){
                jIndex--;
            }else {
                iIndex++;
            }
        }
        return false;
    }