LeetCode Hot100 矩阵

Posted on Edited on

矩阵置零

Problem

https://leetcode.cn/problems/set-matrix-zeroes/?envType=study-plan-v2&envId=top-100-liked

Solution

行标记数组记录此行是否有0，列标记数组记录此列是否有0，根据标记数组重写矩阵。

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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> rowFlag(m, false);
        vector<bool> colFlag(n, false);

        for (int i = 0; i < m; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (!matrix[i][j])
                {
                    rowFlag[i] = true;
                    colFlag[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (rowFlag[i] || colFlag[j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

螺旋矩阵

Problem

https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked

Solution

left, right, top, bottom,一层层遍历

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        int left = 0, right = n-1, top = 0, bottom = m-1;
        vector<int> ans(m * n, 0);
        int idx = 0;
        while (left <= right && top <= bottom)
        {
            for (int i = left; i <= right; i ++)
            {
                ans[idx++] = matrix[top][i];
            }

            for (int i = top+1; i <= bottom; i ++)
            {
                ans[idx++] = matrix[i][right];
            }

            if (top < bottom)
            {
                for (int i = right-1; i >= left; i --)
                {
                    ans[idx++] = matrix[bottom][i];
                }
            }

            if (left < right)
            {
                for (int i = bottom-1; i > top; i --)
                {
                    ans[idx++] = matrix[i][left];
                }
            }

            left ++;
            right --;
            top ++;
            bottom --;
        }
        return ans;
    }
};

旋转图像

Problem

https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-100-liked

Solution

一层一层遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int start = 0, end = n - 1;
        while (start <= end)
        {
            for (int i = start; i < end; i ++)
            {
                int temp = matrix[start][i];
                matrix[start][i] = matrix[n - i - 1][start];
                matrix[n - i - 1][start] = matrix[end][n - i - 1];
                matrix[end][n - i - 1] = matrix[i][end];
                matrix[i][end] = temp;
            }
            start ++;
            end --;
        }
    }
};

搜索二维矩阵II

Problem

https://leetcode.cn/problems/search-a-2d-matrix-ii/?envType=study-plan-v2&envId=top-100-liked

Solution

矩阵某元素大于当前行左边的所有元素，小于当前列下边的所有元素，从矩阵的右上角开始二分搜索

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
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int i = 0, j = n - 1;

        while (i < m && j >= 0)
        {
            if (matrix[i][j] < target)
            {
                i ++;
            }
            else if (matrix[i][j] > target)
            {
                j --;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};