矩阵

线性代数学得怎么样?

没想到矩阵也是一种数据结构?

ai主战场

数学还是很智慧的…

插眼…

慢慢写…

73.矩阵置零

解:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool firstRowZero = false;
        bool firstColZero = false;
        // 判断第一行是否需要清零
        for(int i = 0; i < n; i++) {
            if(matrix[0][i] == 0) {
                firstRowZero = true;
            }
        }
        // 判断第一列是否需要清零
        for(int j = 0; j < m; j++) {
            if(matrix[j][0] == 0) {
                firstColZero = true;
            }
        }
        // 用第一行、第一列作为标记
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        // 根据标记清零内部矩阵
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 处理第一行
        for(int i = 0; i < n; i++) {
            if(firstRowZero) {
                matrix[0][i] = 0;
            }
        }
        // 处理第一列
        for(int j = 0; j < m; j++) {
            if(firstColZero) {
                matrix[j][0] = 0;
            }
        }
    }
};

54.螺旋矩阵

解:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<int> res;
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        while(top <= bottom && left <= right) {
            // 左 -> 右
            for(int j = left; j <= right; j++) {
                res.push_back(matrix[top][j]);
            }
            top++;
            // 上 -> 下
            for(int i = top; i <= bottom; i++) {
                res.push_back(matrix[i][right]);
            }
            right--;
            // 边界已经发生变化，不一定仍然有效
            // if 防止越界或重复访问
            // 右 -> 左
            if(top <= bottom) {
                for(int j = right; j >= left; j--) {
                    res.push_back(matrix[bottom][j]);
                }
                bottom--;
            }
            // 下 -> 上
            if(left <= right) {
                for(int i = bottom; i >= top; i--) {
                    res.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        return res;
    }
};

48.旋转图像

解:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 转置
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // reverse
        for(int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

240.搜索二维矩阵 II

解法:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int i = 0;
        int j = n - 1;
        while(i < m && j >= 0) {
            if(matrix[i][j] == target) {
                return true;
            }else if(matrix[i][j] < target) {
                i++;
            }else {
                j--;
            }
        }
        return false;
    }
};