54/59-螺旋矩阵

LeetCode 54. Spiral Matrix

LeetCode-54

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

method

先一圈一圈输出，注意区间左闭右开，最后

• 没有元素剩余，直接返回
• 剩一个，直接赋值
• 剩一行或者一列，循环赋值

(i, j)都是从(sx, sy)开始的，i--和j--的时候不能小于(sx, sy)
最后(n1, m1)会有6种情况(0, 0), (n1, 0), (0, m1)这三种不用管
(1, 1), (n1, 1), (1, m1)这三种要继续赋值

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    vector<int> res(n * m);
    int n1 = n, m1 = m;     // 用来判断还剩几行几列
    int sx = 0, sy = 0;     // 每圈开始的位置
    int offset = 1;         // 完成一圈就加2
    int cnt = 0;            // res的指针
    int i,j;
    while (n1 > 1 && m1 > 1) {
        i = sx, j = sy;
        for (; j < sy + m - offset; j++) res[cnt++] = matrix[i][j];
        for (; i < sx + n - offset; i++) res[cnt++] = matrix[i][j];
        for (; j > sy; j--) res[cnt++] = matrix[i][j];
        for (; i > sx; i--) res[cnt++] = matrix[i][j];
        sx++, sy++;
        offset += 2;
        n1 -= 2;
        m1 -= 2;    // 完成一圈就减2
    }
    i = sx, j = sy;
    if (n1 == 1 && m1 == 1) res[cnt] = matrix[sx][sy];
    else if (n1 == 1 && m1 > 1) {   // 剩一行，直接用m1就不用offset
        for (; j < sy + m1; j++) res[cnt++] = matrix[i][j];
    }
    else if (n1 > 1 && m1 == 1) {   // 剩一列
        for (; i < sx + n1; i++) res[cnt++] = matrix[i][j];
    }
    return res;
}

---

LeetCode 59. Spiral Matrix II

LeetCode-59

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

method: 模拟

一圈一圈地往里填数，每行每列都是固定的左闭右开区间

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n, vector<int>(n, 0));
    int sx = 0, sy = 0; // 每圈的起始点
    int num = n / 2;    // 总共需要填几圈
    int offset = 1;     // 往里一层要减去的固定长度
    int count = 1;
    while (num--) {
        int i = sx;
        int j = sy;
        for (; j < sy + n - offset; ++j)    // 上行
            res[i][j] = count++;
        for (; i < sx + n - offset; ++i)    // 右列
            res[i][j] = count++;
        for (; j > sy; --j)     // 下行
            res[i][j] = count++;
        for (; i > sx; --i)     // 左列
            res[i][j] = count++;
        sx++;
        sy++;
        offset += 2;
    }
    if (n & 1) res[sx][sy] = count; // 奇数还有一个
    return res;
}