LeetCode 热题 100 | 矩阵

目录

1 73. 矩阵置零

2 54. 螺旋矩阵

3 48. 旋转图像

4 240. 搜索二维矩阵 II

---

菜鸟做题第二周，语言是 C++

1 73. 矩阵置零

解题思路：

1. 遍历矩阵，寻找等于 0 的元素，记录对应的行和列

服务器托管网

2. 将被记录的行的元素全部置 0
3. 将被记录的列的元素全部置 0

class Solution {
public:
    void setZeroes(vector>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        unordered_set row, col;

        // 寻找0
        for (int i = 0; i 

2 54. 螺旋矩阵

解题思路：

• 定义 right，down，left，up 来标志四个方向
• 根据不同的方向设置不同的坐标加减策略
• 将被遍历过的元素置为 101，用于指示能否继续前进
• 借助ans.size() 计数，用于指示是否继续循环

为什么将被遍历过的元素置为 101？

如上图所示，101 是矩阵元素绝对不会取到的数值。

如果题目对取值范围没有限制的话，那可能真的需要定义另一个矩阵来记录遍历情况了。

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        int right = 1, down = 0, up = 0, left = 0;
        vector ans;
        int n = matrix.size(), m = matrix[0].size();

        int i = 0, j = 0;
        while (ans.size() != n * m) {
            if (right) {
                while (j = 0 && matrix[i][j] != 101) {
                    ans.push_back(matrix[i][j]);
                    matrix[i][j] = 101;
                    --j;
                }
                ++j;
                --i;
                left = 0;
                up = 1;
            }

            if (up) {
                while (i >= 0 &&a服务器托管网mp; matrix[i][j] != 101) {
                    ans.push_back(matrix[i][j]);
                    matrix[i][j] = 101;
                    --i;
                }
                ++i;
                ++j;
                up = 0;
                right = 1;
            }
        }
        return ans;
    }
};

3 48. 旋转图像

报一丝，还是用了新的矩阵，以后想想其他办法。。。

class Solution {
public:
    void rotate(vector>& matrix) {
        auto temp = matrix;
        int n = matrix.size();
        for (int i = 0; i 

4 240. 搜索二维矩阵 II

笨办法，但意外的是没超时

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {

        int n = matrix.size(), m = matrix[0].size();

        int i = 0, j = 0;
        while (i = 0; --x) {
                    if (matrix[x][y] == target) return true;
                }
            }
        }

        // 针对n>m的情况且找到头的情况
        if (j == m) {
            --j;
            while (i = 0; --y) {
                    if (matrix[x][y] == target) return true;
                }
            }
        }

        for (int x = i; x = 0; --y) {
                if (matrix[x][y] == target) return true;
            }
        }

        for (int y = j; y = 0; --x) {
                if (matrix[x][y] == target) return true;
            }
        }
        
        return false;
    }
};

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net