73. 矩阵置零✅

Solution1：先把零的位置找出来，用二维数组存起来，但这样额外空间是O(mn)

Solution2改进：仅使用常量空间，即O(1)

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

        vector<pair<int, int>> v;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(!matrix[i][j]) {
                    v.push_back(make_pair(i, j));
                }
            }
        }

        for(int i = 0; i < v.size(); i++) {
            // cout << v[i].first << " " << v[i].second << endl;
            for(int k = 0; k < n; k++) matrix[v[i].first][k] = 0;
            for(int k = 0; k < m; k++) matrix[k][v[i].second] = 0;
        }
 
    }
};

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

        bool row_flag = false;
        bool col_flag = false;
        
        //判断第一行是否有零
        for(int j = 0; j < n; j++) {
            if(!matrix[0][j]) {
                row_flag = true;
                break;
            }
        }
        //判断第一列是否有零
        for(int i = 0; i < m; i++) {
            if(matrix[i][0] == 0) {
                col_flag = true;
                break;
            }
        }

 
        //用第一行和第一列作为标志位，表示该行/列是否有零
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(!matrix[i][j]) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // for(const auto &i : matrix) {
        //     for(const auto &j : i) {
        //         cout << j << " ";
        //     }
        //     cout << endl;
        // }

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

        if(row_flag) {
            for(int j = 0; j < n; j++) matrix[0][j] = 0; 
        }
        
        if(col_flag) {
            for(int i = 0; i < m; i++) matrix[i][0] = 0; 
        }
    }
};

54. 螺旋矩阵✅

模拟 控制边界

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) { 
        vector<int> res;
 
        int row = matrix.size(), col = matrix[0].size();
        int pre_row = 0, pre_col = 0;
        int post_row = row - 1, post_col = col - 1;

        while(res.size() < row * col) {
            for(int i = pre_col; i <= post_col; i++) res.push_back(matrix[pre_row][i]); //往右
            pre_row++;
            if(res.size() >= row * col) break;

            for(int i = pre_row; i <= post_row; i++) res.push_back(matrix[i][post_col]); //往下
            post_col--;
            if(res.size() >= row * col) break;

            for(int i = post_col; i >= pre_col; i--) res.push_back(matrix[post_row][i]); //往左
            post_row--;
            if(res.size() >= row * col) break;

            for(int i = post_row; i >= pre_row; i--) res.push_back(matrix[i][pre_col]); //往上
            pre_col++;
        }

        return res;
    }
};

48. 旋转图像❌

原地修改 以四个点扩展

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        for(int i = 0 ; i < n / 2; i++) {
            for(int j = 0; j < (n+1) / 2; j++) {
                int tmp = matrix[i][j]; //暂存元素A
                //旋转元素 A <- D <- C <- B <- tmp
                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] = tmp;
            }
        }
    }
};

240. 搜索二维矩阵 II✅

既然都有序了 直接对每一行二分

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        

        for(int i = 0; i < row; i++) {
            int left = 0, right = col - 1;
            while(left <= right) {
                int mid = (left + right) / 2;
                if(matrix[i][mid] > target) {
                    right = mid - 1;
                } else if(matrix[i][mid] < target) {
                    left = mid + 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }
};