HOT100与剑指Offer

---

前言

一个本硕双非的小菜鸡，备战24年秋招，计划刷完hot100和剑指Offer的刷题计划，加油！
根据要求，每一道题都要写出两种以上的解题技巧。

一、73. 矩阵置零（HOT100）

73. 矩阵置零
Note：使用两个标记变量
需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 000。
在实际代码中，首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.size() == 0) return;
        const int m = matrix.size();
        const int n = matrix[0].size();
        bool firstRow = false;
        bool firstCol = false;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int item = matrix[i][j];
                if (item == 0) {
                    if (i == 0)
                        firstRow = true;
                    if (j == 0)
                        firstCol = true;

                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

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

        if (firstRow) {
            for (int i = 0; i < n; i++)
                matrix[0][i] = 0;
        }

        if (firstCol) {
            for (int i = 0; i < m; i++)
                matrix[i][0] = 0;
        }
    }
};

Note：使用标记数组
用两个标记数组分别记录每一行和每一列是否有零出现

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m), col(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!matrix[i][j]) {
                    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;
                }
            }
        }
    }
};

二、29. 顺时针打印矩阵（剑指Offer）

顺时针打印矩阵

Note：根据四个边界条件，每种条件分别处理

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        int startx = 0, starty = 0;
        int m = matrix.size();
        int n = matrix[0].size();
        int middle = min(m, n); //中间值处理
        int loop = middle / 2; //循环的圈数
        int length = 1; //每次遍历的长度
        int i, j;
        
        if (matrix.empty()) return res;
        
        while (loop--) {
            i = startx;
            j = starty;
            
            //从左到右
            for (j = starty; j < n - length; j++) {
                res.push_back(matrix[startx][j]);
            }
            
            //从上到下
            for (i = startx; i < m - length; i++) {
                res.push_back(matrix[i][j]);
            }
            
            //从右到左
            for (; j > starty; j--) {
                res.push_back(matrix[i][j]);
            }
            
            //从下到上
            for (; i > startx; i--) {
                res.push_back(matrix[i][j]);
            }
            
            startx++;
            starty++;
            length++;
        }
        
        //奇数情况未遍历一行或一列
        if (middle % 2 == 1) {
            i = startx;
            j = starty;
            if (middle == m) {
                for (; j < n - length + 1; j++) {
                    res.push_back(matrix[startx][j]);
                }
            } else {
                for (; i < m - length + 1; i++) {
                    res.push_back(matrix[i][j]);
                }
            }
        }
        return res;
    }
};

Note：我们顺时针定义四个方向：上右下左。
从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历 𝑛2个格子后停止。

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if (matrix.empty()) return res;
        int m = matrix.size();
        int n = matrix[0].size();
        
        vector<vector<bool>> st(m, vector<bool>(n, false));
         int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        for (int k = 0; k < m * n; k ++ )
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= m || b < 0 || b >= n || st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

总结

祝大家都能学有所成，找到一份好工作！