螺旋矩阵问题模板

何言 2021年08月18日 111次浏览

螺旋矩阵代码模板。这种问题没有什么算法,但是很考验功力。

转自 代码随想录 (programmercarl.com)

螺旋矩阵

例题:Loading Question... - 力扣(LeetCode) (leetcode-cn.com)

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

image20210818095654186.png

循环不变量

这里要按圈来分析,对于每一圈,需要遍历四条边:

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

这里要遵循左闭右开原则,如下图:

image20210818095823819.png

代码模板

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        
        // 循环次数
        // 圈数,对于 n = 3 ,则需要循环 n / 2 = 1 圈
        // 对于 n 为奇数时 中心点 最后单独填充
        int loop = n/2; 
        
        // 每次循环起始位置
        int startX = 0;
        int startY = 0;
        
        // 偏移量
        int offset = 1;
        
        // 填充数字
        int count = 1;
        
        // 定义中间位置
        int mid = n/2;
        
        while (loop > 0) {
            int i = startX;
            int j = startY;
            
            // 上行从左到右
            for(; j < startY + n - offset; ++ j){
                res[i][j] = count ++;
            }
            
            // 右列从上到下
            for(; i < startX + n - offset; ++ i){
                res[i][j] = count ++;
            }
            
            // 下行从右到左
            for(; j > startY ; --j){
                res[i][j] = count ++;
            }
            
            // 左侧从下到上
            for(; i > startX ; --i){
                res[i][j] = count ++;
            }
            
            loop --;
            
            startX += 1;
            startY += 1;
            
            offset += 2;
        }
        
        if(n % 2 == 1){
            res[mid][mid] = count;
        }
        
        return res;
    }
}