6.5-模拟

M:59.螺旋矩阵II

题意描述

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 20

思路

这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

要如何画出这个螺旋排列的正方形矩阵呢？

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

由外向内一圈一圈这么画下去。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

那么我按照左闭右开的原则，来画一圈，大家看一下：

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

这也是坚持了每条边左闭右开的原则。

AC代码：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

法二：偏移量法

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n , vector<int>(n , 0));
     
        //顺序依次为左上右下，一开始向右，因此d=1, 列+1
        int dx[4] = {-1 , 0 , 1 , 0}, dy[4] = {0 , 1 , 0 , -1};
      //注意这里循环是以填的数cnt：1~n*n来循环n^2次
        for(int cnt = 1 , x = 0 , y = 0 , d = 1 ;cnt <= n * n ; cnt++){
          res[x][y] = cnt;
          int a = x + dx[d] , b = y + dy[d];
          if(a < 0 || a >= n || b < 0 || b >= n || res[a][b]){
            d = (d + 1) % 4;
            a = x + dx[d] , b = y + dy[d];
          }
          x = a , y = b;
        }

        return res;
    }
};

---

ACwing756.蛇形矩阵

题目描述：

输入两个整数 𝑛 和 𝑚，输出一个 𝑛 行 𝑚 列的矩阵，将数字 1 到 𝑛×𝑚 按照回字蛇形填充至矩阵中。

具体矩阵形式可参考样例。

输入格式

输入共一行，包含两个整数 𝑛 和 𝑚。

输出格式

输出满足要求的矩阵。

矩阵占 𝑛 行，每行包含 𝑚 个空格隔开的整数。

数据范围

1≤𝑛,𝑚≤100

输入样例：

3 3

输出样例：

1 2 3
8 9 4
7 6 5

思路：

设当前位置坐标为(x,y)，上、下、左、右方向分别为dr=0 dr=2 dr=3 dr=1
则该位置上、下、左、右的位置所对应的偏移量分别为(x-1,y) (x+1,y) (x,y-1) (x,y+1)
将方向与偏移量的对应关系初始化为两个数组便于引用

每次执行循环后，判断下一个位置是否到达数组边界，或数组中已经存在元素
若满足上述情况，则改变方向。

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn=110;

int a[maxn][maxn];  //定义空的二维数组数组
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};  //初始化方向所对应的偏移量的数组

int main()
{
    int n,m;
    cin>>n>>m;
    int dr=1,x=0,y=0;  //初始化开始方向为右，初始化开始的位置
    for(int i=1;i<=n*m;i++){
        a[x][y]=i;  //存入答案
        int h=x+dx[dr],l=y+dy[dr];  //定义临时变量存放(x,y)的下一个位置的坐标
        if(h<0||l<0||h>=n||l>=m||a[h][l]){  //判断
            dr=(dr+1)%4;
            h=x+dx[dr],l=y+dy[dr];
        } 
        x=h,y=l;  //更新(x,y)
    }
    for(int i=0;i<n;i++){  //循环打印输出
        for(int j=0;j<m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

---

类似题目：ACwing3208.Z字形扫描

题意描述：

在图像编码的算法中，需要将一个给定的方形矩阵进行 𝑍 字形扫描(Zigzag Scan)。

给定一个𝑛×𝑛 的矩阵，𝑍 字形扫描的过程如下图所示：

对于下面的 4×4 的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行 𝑍 字形扫描后得到长度为 16 的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 𝑍 字形扫描的程序，给定一个𝑛×𝑛 的矩阵，输出对这个矩阵进行 𝑍 字形扫描的结果。

输入格式

输入的第一行包含一个整数 𝑛，表示矩阵的大小。

输入的第二行到第 𝑛+1 行每行包含 𝑛 个正整数，由空格分隔，表示给定的矩阵。

输出格式

输出一行，包含 𝑛×𝑛 个整数，由空格分隔，表示输入的矩阵经过 𝑍 字形扫描后的结果。

数据范围

1≤𝑛≤500，
矩阵元素为不超过 1000 的正整数。

输入样例：

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出样例：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

分析：

该题以Z字形遍历数组，对于奇数和偶数情况下，边界转向复杂
扩大原二维数组，使边界转向统一

观察旋转方向，设初始方向dr = 0
扩大二维数组，遍历满足在原数组范围内时输出

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=505;

int a[2*N][2*N];  //定义时直接扩大

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){  //初始化二维数组
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int dr=0,dx[]={0,1,1,-1},dy[]={1,-1,0,1};  //定义(0,1)的方向dr=0  定义偏移量数组
    printf("%d ",a[0][0]);  //先将(0,0)位置的数输出
    int x=0,y=1;  //初始化位置为(0,1)
    for(int i=0;i<(2*n+1)*n;i++){  //循环遍历扩大后的数组
        if(x<n&&y<n){
            printf("%d ",a[x][y]);  //满足在原始数组范围内输出
        }
        int l=x+dx[dr],r=y+dy[dr];  //临时变量判断下一个要遍历的格子坐标(l,r)
        if(dr==0||dr==2||r<0||l<0||r>=n||l>=n){  //如果dr=0或dr=2或(l,r)出界时改变方向
            dr=(dr+1)%4;
            l=x+dx[dr],r=y+dy[dr];
        }
        x=l,y=r;  //更新(x,y)
    }
    return 0;
}

---

LCR 146. 螺旋遍历二维数组

题目描述：

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

示例 1：

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

示例 2：

输入：array  = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

限制：

• 0 <= array.length <= 100
• 0 <= array[i].length <= 100

注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/

思路1：模拟

AC代码：

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array)
    {
        if (array.empty()) return {};
        int l = 0, r = array[0].size() - 1, t = 0, b = array.size() - 1;
        vector<int> res;
        while(true)
        {
            for (int i = l; i <= r; i++) res.push_back(array[t][i]); // left to right
            if (++t > b) break;
            for (int i = t; i <= b; i++) res.push_back(array[i][r]); // top to bottom
            if (l > --r) break;
            for (int i = r; i >= l; i--) res.push_back(array[b][i]); // right to left
            if (t > --b) break;
            for (int i = b; i >= t; i--) res.push_back(array[i][l]); // bottom to top
            if (++l > r) break;
        }
        return res;
    }
};

思路2：偏移量法

判断路径是否进入之前访问过的位置需要使用一个与输入二维数组大小相同的辅助二维数组==visited==，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 ==visited== 中的对应位置的元素设为已访问。

如何判断路径是否结束？由于二维数组中的每个元素都被访问一次，因此路径的长度即为二维数组中的元素数量，当路径的长度达到二维数组中的元素数量时即为完整路径，将该路径返回。

AC代码：

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        if(array.size() == 0  || array[0].size() == 0)  return {};
        
        int r = array.size(),c = array[0].size();
        vector<vector<bool>> visited(r , vector<bool>(c));
        int t = r * c;
    
        vector<int> res(t);
        int dx[] = {-1 , 0 , 1, 0}, dy[] = {0 , 1 , 0, -1};
        for(int i =0 ,a = 0 , b = 0 , d = 1; i < t ; i++ ){
            res[i] = array[a][b];
            visited[a][b] = true;
            int na = a + dx[d] , nb = b + dy[d];
            if(na< 0 || na >= r || nb < 0 || nb >= c || visited[na][nb]){
                d = (d + 1) % 4;
                na = a + dx[d] , nb = b + dy[d];
            }
            a = na , b = nb;  
        }
        return res;
    }
};