矩阵置0

把第一行第一列拿来当标记数组，这样就可以做到O(1)空间复杂度，注意一开始特判下第一行和第一列有没有有0的数，有0的数字就flag记录下。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 记录第一行是否包含 0
        boolean firstRowHasZero = false; 
        for (int x : matrix[0]) {
            if (x == 0) {
                firstRowHasZero = true;
                break;
            }
        }
        // 记录第一列是否包含 0
        boolean firstColHasZero = false; 
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
        // 用第一列 matrix[i][0] 保存 rowHasZero[i]
        // 用第一行 matrix[0][j] 保存 colHasZero[j]
        for (int i = 1; i < m; i++) { // 无需遍历第一行，如果 matrix[0][j] 本身是 0，那么相当于 colHasZero[j] 已经是 true
            for (int j = 1; j < n; j++) { // 无需遍历第一列，如果 matrix[i][0] 本身是 0，那么相当于 rowHasZero[i] 已经是 true
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // 相当于 rowHasZero[i] = true
                    matrix[0][j] = 0; // 相当于 colHasZero[j] = true
                }
            }
        }
        for (int i = 1; i < m; i++) { // 跳过第一行，留到最后修改
            for (int j = 1; j < n; j++) { // 跳过第一列，留到最后修改
                if (matrix[i][0] == 0 || matrix[0][j] == 0) { // i 行或 j 列有 0
                    matrix[i][j] = 0;
                }
            }
        }
        // 如果第一列一开始就包含 0，那么把第一列全变成 0
        if (firstColHasZero) {
            for (int[] row : matrix) {
                row[0] = 0;
            }
        }
        // 如果第一行一开始就包含 0，那么把第一行全变成 0
        if (firstRowHasZero) {
            Arrays.fill(matrix[0], 0);
        }
    }
}

螺旋矩阵

模拟题，模拟四个方向遍历

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new ArrayList<Integer>();
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> list = new ArrayList<>();
        list.add(matrix[0][0]);
        matrix[0][0] = -1000;
        int cnt = m * n;
        System.out.println(cnt);
        int count = 0;
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};
        //右下左上顺序遍历
        int tx = 0;
        int ty = 0;
        int k = 0;
        while( count < cnt){
            //先沿着当前的方向走试试
            int tempx = tx + dx[k];
            int tempy = ty + dy[k];
            if(tempx >= 0 && tempx < m && tempy >= 0 && tempy < n && matrix[tempx][tempy] != -1000){//如果能走得通
                    tx = tempx;
                    ty = tempy;
            }else{//当前这个方向走不通，遍历一下
                for(k = 0; k<4; k++){//遍历4个方向
                    tempx = tx + dx[k];
                    tempy = ty + dy[k];
                    if(tempx >= 0 && tempx < m && tempy >= 0 && tempy < n && matrix[tempx][tempy] != -1000){
                        tx = tempx;
                        ty = tempy;
                        break;
                    }
                    else if(k == 3){
                        return list;
                    }
                }
            }
            list.add(matrix[tx][ty]);
            matrix[tx][ty] = -1000;
            count++;
        }
        return list;
    }
}

旋转图像

思路题，四个位置交换，m[i][j] <- m[n-1-j][i] <- m[n-1-i][n-1-j] <- m[j][n-1-i]

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 + 1)/2; j++){
                int tmep = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = tmep;
            }
        }
    }
}

搜索二维矩阵 II

思路题，从左下到右上遍历即可。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = rows - 1;
        int j = 0;
        while(i >=0 && j <cols){
            int t = matrix[i][j];
            if(t == target) return true;
            else if(t > target){
                //往上走
                i--;
            }else{
                //往左走
                j++;
            }
        }
        return false;
    }
}