Leetcode每日一题 —— 1914. 循环轮转矩阵

1914. 循环轮转矩阵 - 力扣（LeetCode）

1914. 循环轮转矩阵 - 给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。 矩阵由若干层组成，如下图所示，每种颜色代表一层： [https://assets.leetcode.com/uploads/2021/06/10/ringofgrid.png] 矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针...

思路

看上去就是模拟题了，可以写个 helper 函数来对每一层进行处理。

咱的思路是对于每一层，计算出其周长 perimeter，然后 k 对周长取模得到实际要轮转的次数 realK。

从右上角 (i, j) 开始，找到在周长上距离 (i, j) realK 个格子的位置 (targetI, targetJ)，接着螺旋扫描矩阵，同时推进位置 (i, j) 和 (targetI, targetJ)，把 (targetI, targetJ) 的值不断赋给 (i, j) 即可。

直接在矩阵上写这套模拟真的挺麻烦的，如果把一层铺平后再处理似乎要好写很多。

代码

咱是直接在矩阵上模拟的，有点屎山了，不过时间复杂度上还算挺快的。

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> res(m,vector<int>(n));
        // 通过坐标可以判断目前这个数字在哪一个层级
        // 每一个层级的周长也可以求一下，因为是循环操作，k 可以取模
        // 对于每一层，我们可以从左上角开始，用偏移量定位当前位置在轮转后是哪个元素，然后顺着往下填
        auto rotateLayer=[&](int layer) -> void {
            int i=layer,j=layer; // 这一层的左上角坐标
            int layerM=m-(i<<1),layerN=n-(j<<1);
            // 计算本层周长
            int perimeter=((layerM+layerN)<<1)-4;
            int realK=k%perimeter;
            // 定位，找到周长上距离 (i, j) 有 realK 距离的地方
            int secondDir=0; // 确定后面的方向
            int targetI=i,targetJ=j;
            if(realK<=layerN-1){
                targetJ=j+realK;
            }else if(realK<=(layerN-1)+(layerM-1)){
                targetJ=j+layerN-1;
                targetI=i+realK-(layerN-1);
                secondDir=1;
            }else if(realK<=(layerN-1)+(layerM-1)+(layerN-1)){
                targetI=i+layerM-1;
                targetJ=j+layerN-1-(realK-(layerM-1)-(layerN-1));
                secondDir=2;
            }else{
                targetJ=j;
                targetI=i+layerM-1-(realK-((layerN-1)<<1)-(layerM-1));
                secondDir=3;
            }
            // 现在 (i, j) 位置旋转后的值就是 (targetI, targetJ) 位置的值
            res[i][j]=grid[targetI][targetJ];
            // 接下来就沿着周长顺时针转一圈逐个填上
            int iPos=i,jPos=j;
            int drcts[][2]={
                {0,1},
                {1,0},
                {0,-1},
                {-1,0},
            };
            int firstDir=0;
            perimeter--; // 首个位置已经处理
            while(perimeter>0){
                int newI=iPos+drcts[firstDir][0],newJ=jPos+drcts[firstDir][1];
                if(newI<i||newI>=i+layerM||newJ<j||newJ>=j+layerN){
                    // 越界，换方向
                    firstDir=(firstDir+1)%4;
                    newI=iPos+drcts[firstDir][0];
                    newJ=jPos+drcts[firstDir][1];
                }
                int newTargetI=targetI+drcts[secondDir][0],newTargetJ=targetJ+drcts[secondDir][1];
                if(newTargetI<i||newTargetI>=i+layerM||newTargetJ<j||newTargetJ>=j+layerN){
                    // 越界，换方向
                    secondDir=(secondDir+1)%4;
                    newTargetI=targetI+drcts[secondDir][0];
                    newTargetJ=targetJ+drcts[secondDir][1];
                }
                res[newI][newJ]=grid[newTargetI][newTargetJ];
                iPos=newI;
                jPos=newJ;
                targetI=newTargetI;
                targetJ=newTargetJ;
                perimeter--;
            }
        };
        // 取较短边的一半作为层数
        int numLayers=(min(m,n)>>1);
        for(int i=0;i<numLayers;i++){
            rotateLayer(i);
        }
        return res;
    }
};

2 个帖子 - 2 位参与者

阅读完整话题