16/17,螺旋矩阵Ⅰ/Ⅱ/数组与字符串

螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

思路：保存四个方向，然后维护一个表示当前节点是否走过的矩阵，每次循环到角落不能继续时就试着找出唯一能走的方向，然后保存继续走，直到输出完成。
时间复杂度：O(n)每个数只循环一次
空间复杂度：O(n)需要保存维护一个于matrix相同大小的01矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> fin;
        if(matrix.size() == 0)return fin;
        vector<vector<int>> bushu;
        for(int i=0;i<matrix.size();i++){
            vector<int> tmp(matrix[0].size(), 0);
            bushu.push_back(tmp);
        }
        bushu[0][0] = 1;

        vector<int> a1 = { 0,1 };//→
        vector<int> a2 = { 1,0 };//↑
        vector<int> a3 = { -1,0 };//↓
        vector<int> a4 = { 0,-1 };//←
        vector<vector<int>> s;
        s.push_back(a1);
        s.push_back(a2);
        s.push_back(a3);
        s.push_back(a4);

        int count = matrix.size()*matrix[0].size()-1;
        int f = 0;
        int x = 0, y = 0;
        
        fin.push_back(matrix[0][0]);
        while (count >0) {
            if (x+s[f][0] < matrix.size() && y+s[f][1] < matrix[0].size()&& bushu[x + s[f][0]][y + s[f][1]] != 1) {

                x += s[f][0];
                y += s[f][1];
                fin.push_back(matrix[x][y]);
                bushu[x][y] = 1;
                count--;


            }
            else{
                for (int i = 0; i < 4; i++) {
                    if (x + s[i][0] < matrix.size() && y + s[i][1] < matrix[0].size()&& bushu[x + s[i][0]][y + s[i][1]] != 1) {

                        f = i;
                        break;


                    }
                }

            }
        }


        return fin;
    }
};

螺旋矩阵Ⅱ

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

示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

思路：其实比上题更简单，只需要维护一个结果矩阵，没走过的都是0，走过的都是当前数。切换逻辑与上题相同。
时间复杂度：O(n)每个数只循环一次
空间复杂度：O(n²)需要保存维护一个n*n大小的结果矩阵

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        
        vector<vector<int>> bushu;
        if(n <=0)return bushu;
        for(int i=0;i<n;i++){
            vector<int> tmp(n, 0);
            bushu.push_back(tmp);
        }
        bushu[0][0] = 1;

        vector<int> a1 = { 0,1 };//→
        vector<int> a2 = { 1,0 };//↑
        vector<int> a3 = { -1,0 };//↓
        vector<int> a4 = { 0,-1 };//←
        vector<vector<int>> s;
        s.push_back(a1);
        s.push_back(a2);
        s.push_back(a3);
        s.push_back(a4);

        int count = n*n;
        int f = 0;
        int x = 0, y = 0;
        while (count >1) {
            if (x + s[f][0] >=0 && y + s[f][1] >=0&& x+s[f][0] < n && y+s[f][1] < n&& bushu[x + s[f][0]][y + s[f][1]] == 0 ) {

                x += s[f][0];
                y += s[f][1];
                bushu[x][y] = n*n-count+2;
                count--;


            }
            else{
                for (int i = 0; i < 4; i++) {
                    if (x + s[i][0] >= 0 && y + s[i][1] >= 0 && x + s[i][0] < n && y + s[i][1] < n&& bushu[x + s[i][0]][y + s[i][1]] == 0) {

                        f = i;
                        break;


                    }
                }

            }
        }


    return bushu;
    }
};