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

矩阵

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107