螺旋矩阵

59. 螺旋矩阵 II（Medium）

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

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]
 

提示：

• 1 <= n <= 20

思路

螺旋矩阵没生成一行或一列，对应的边界就会+1或-1。

对于边界遍历的处理不同会影响到代码复杂程度。

冗余版

vector<vector<int>> generateMatrix(int n)
{
    vector<vector<int>> matrix(n, vector<int>(n,0));
    int value = 1;
    // 左右边界
    int l = 0, r = n - 1;
    // 上下边界
    int t = 0, d = n - 1;
    int i = 0, j = 0;

    while (value <= n * n)
    {
        for (; j <= r; j++)
            matrix[i][j] = value++;
        j--;
        i++;
        t++;

        for (; i <= d; i++)
            matrix[i][j] = value++;
        i--;
        j--;
        r--;

        for (; j >= l; j--)
            matrix[i][j] = value++;
        j++;
        i--;
        d--;

        for (; i >= t; i--)
            matrix[i][j] = value++;
        i++;
        j++;
        l++;
    }
    return matrix;
}

简洁版

vector<vector<int>> generateMatrix(int n)
{
    vector<vector<int>> matrix(n, vector<int>(n,0));
    int value = 1;
    int l = 0, r = n - 1;
    int t = 0, d = n - 1;
    int i = 0, j = 0;
    
    // n为奇数时，无法遍历到中心，所以<=无法跳出循环
    while (value < n * n)
    {
        for (; j < r; j++)
            matrix[i][j] = value++;
        t++;

        for (; i < d; i++)
            matrix[i][j] = value++;
        r--;

        for (; j > l; j--)
            matrix[i][j] = value++;
        d--;

        for (; i > t; i--)
            matrix[i][j] = value++;
        l++;
    }
    
    // 补上最后一个数
    matrix[i][j] = value;
  
    return matrix;
}

源码

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> generateMatrix(int n);

int main()
{
    int n;
    cin >> n;

    vector<vector<int>> matrix = generateMatrix(n);

    for (const vector<int>& row: matrix)
    {
        for(int num: row)
            cout << num << " ";

        cout << "\b\n";
    }

    return 0;
}

vector<vector<int>> generateMatrix(int n)
{
    vector<vector<int>> matrix(n, vector<int>(n,0));
    int value = 1;
    // 左右边界
    int l = 0, r = n - 1;
    // 上下边界
    int t = 0, d = n - 1;
    int i = 0, j = 0;

    while (value < n * n)
    {
        for (; j < r; j++)
            matrix[i][j] = value++;
        t++;

        for (; i < d; i++)
            matrix[i][j] = value++;
        r--;

        for (; j > l; j--)
            matrix[i][j] = value++;
        d--;

        for (; i > t; i--)
            matrix[i][j] = value++;
        l++;
    }

    matrix[i][j] = value;

    return matrix;
}

54. 螺旋矩阵（Medium）

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

思路

同59. 螺旋矩阵 II，螺旋遍历到倒数第二个数，最后一个数在循环外补上，以解决奇数方阵的问题。

两题不同处在于，m不一定等于n，使用size不会像59. 螺旋矩阵 II的value多计数一个。

所以while条件变为了while (nums.size() < m * n - 1) ，

同时for循环额外添加条件nums.size() < m * n - 1 防止在while判断前，提前添加把最后一个数。

vector<int> spiralOrder(vetor<vector<int>>& matrix)
{
    vector<int> nums;

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

    int t = 0, d = m - 1;
    int l = 0, r = n - 1;
    int i = 0, j = 0;
    
    // 这里用的size而非cnt，所以 m * n得减去1
    while (nums.size() < m * n - 1)
    {
        // for中 nums.size() < m * n - 1 防止遍历到最后一个
        for (; j < r && nums.size() < m * n - 1; j++)
            nums.push_back(matrix[i][j]);
        t++;

        for (; i < d && nums.size() < m * n - 1; i++)
            nums.push_back(matrix[i][j]);
        r--;

        for (; j > l && nums.size() < m * n - 1; j--)
            nums.push_back(matrix[i][j]);
        d--;

        for (; i > t && nums.size() < m * n - 1; i--)
            nums.push_back(matrix[i][j]);
        l++;
    }
    // 补上最后一个
    nums.push_back(matrix[i][j]);

    return nums;
}

源码

#include <iostream>
#include <vector>

using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix);

int main()
{
    int m, n;
    cin >> m >> n;

    vector<vector<int>> matrix(m, vector<int>(n));

    for (vector<int>& row: matrix)
        for (int& num: row)
            cin >> num;

    vector<int> nums = spiralOrder(matrix);

    for (int num: nums) cout << num << " ";
    cout << "\b\n";

    return 0;
}

vector<int> spiralOrder(vector<vector<int>>& matrix)
{
    vector<int> nums;

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

    int t = 0, d = m - 1;
    int l = 0, r = n - 1;
    int i = 0, j = 0;

    while (nums.size() < m * n - 1)
    {
        for (; j < r && nums.size() < m * n - 1; j++)
            nums.push_back(matrix[i][j]);
        t++;

        for (; i < d && nums.size() < m * n - 1; i++)
            nums.push_back(matrix[i][j]);
        r--;

        for (; j > l && nums.size() < m * n - 1; j--)
            nums.push_back(matrix[i][j]);
        d--;

        for (; i > t && nums.size() < m * n - 1; i--)
            nums.push_back(matrix[i][j]);
        l++;
    }

    nums.push_back(matrix[i][j]);

    return nums;
}