数组：二维数组

0048. 旋转图像 (opens new window)

题目

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

解析

通过两次翻转，完成顺时针旋转，分别是按主对角线翻转，然后再左右翻转即可。

代码

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                swap(matrix[i][j], matrix[i][n - j - 1]);
            }
        }
    }
};

0054. 螺旋矩阵 (opens new window)

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

解析

维护未遍历数据的上下左右的边界，每次循环获取最外侧一圈边界上的数据，遍历结束后将边界向中心移动，直至边界相交结束循环。

代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int up = 0, down = m - 1, left = 0, right = n - 1;
        vector<int> ans;
        while (true) {
            for (int i = left; i <= right; i++) ans.push_back(matrix[up][i]);
            if (++up > down) break;

            for (int i = up; i <= down; i++) ans.push_back(matrix[i][right]);
            if (--right < left) break;

            for (int i = right; i >= left; i--) ans.push_back(matrix[down][i]);
            if (--down < up) break;

            for (int i = down; i >= up; i--) ans.push_back(matrix[i][left]);
            if (++left > right) break;
        }
        return ans;
    }
};

0059. 螺旋矩阵 II (opens new window)

题目

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

解析

本题与 0054. 螺旋矩阵 解法相同，只需将读取操作变为赋值操作即可。

代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int up = 0, down = n - 1, left = 0, right = n - 1;
        int num = 1;
        vector<vector<int>> ans(n, vector<int>(n));
        while (true) {
            for (int i = left; i <= right; i++) ans[up][i] = num++;
            if (++up > down) break;

            for (int i = up; i <= down; i++) ans[i][right] = num++;
            if (--right < left) break;

            for (int i = right; i >= left; i--) ans[down][i] = num++;
            if (--down < up) break;

            for (int i = down; i >= up; i--) ans[i][left] = num++;
            if (++left > right) break;
        }
        return ans;
    }
};

0073. 矩阵置零 (opens new window)

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

解析

使用矩阵的第一行和第一列标记对应行列是否置零。

代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool rowZero = false, colZero = false;

        // 需要置零的位置记录在首行、首列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = matrix[i][0] = 0;
                    if (i == 0) rowZero = true;
                    if (j == 0) colZero = true;
                }
            }
        }

        // 对非首行、首列元素置零
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 处理首行、首列
        for (int i = 0; colZero && i < m; i++) matrix[i][0] = 0;
        for (int j = 0; rowZero && j < n; j++) matrix[0][j] = 0;
    }
};

0498. 对角线遍历 (opens new window)

题目

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素。

解析

实现题，定义向斜上方和斜下方的坐标变换，遍历时需要注意边界判断。

代码

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> ans;
        
        int m = mat.size();
        int n = mat[0].size();
        
        int row = 0, col = 0, d = 0;
        int dirs[2][2] = {{-1, 1}, {1, -1}};

        for (int i = 0; i < m * n; i ++) {
            ans.push_back(mat[row][col]);
            row += dirs[d][0];
            col += dirs[d][1];

            if (row >= m) {
                row = m - 1; col += 2; d = 1 - d;
            }
            if (col >= n) {
                col = n - 1; row += 2; d = 1 - d;
            }
            if (row < 0) {
                row = 0; d = 1 - d;
            }
            if (col < 0) {
                col = 0; d = 1 - d;
            }
        }
        return ans;
    }
};

0531. 孤独像素 I (opens new window)

题目

给定一幅黑白像素组成的图像, 计算黑色孤独像素的数量。

图像由一个由‘B’和‘W’组成二维字符数组表示, ‘B’和‘W’分别代表黑色像素和白色像素。

黑色孤独像素指的是在同一行和同一列不存在其他黑色像素的黑色像素。

解析

使用两个数组，分别记录每行和每列出现的黑色像素个数，之后遍历图像，统计所有行列黑色像素个数都为 1 的位置，即为黑色孤独像素数量。

代码

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

        vector<int> row(m), col(n);
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (picture[i][j] == 'B') {
                    row[i] ++;
                    col[j] ++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (picture[i][j] == 'B') {
                    ans += (row[i] == 1 && col[j] == 1);
                }
            }
        }
        return ans;
    }
};

0566. 重塑矩阵 (opens new window)

题目

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

解析

新老位置转换关系：ans[idx / c][idx % c] = nums[i][j]，其中 idx 为原矩阵按行遍历的下标。

代码

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int m = nums.size();
        int n = nums[0].size();
        if (m * n != r * c) {
            return nums;
        }        
        vector<vector<int>> ans(r, vector<int>(c));

        int idx = 0;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                ans[idx / c][idx % c] = nums[i][j];
                idx ++;
            }
        }
        return ans;
    }
};