59. 螺旋矩陣 II

給你一個(gè)正整數(shù) n ，生成一個(gè)包含 1 到 n² 所有元素，且元素按順時(shí)針順序螺旋排列的 n x n 正方形矩陣 matrix 。

示例 1：

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

示例 2：

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

提示：

1 <= n <= 20

思路：

本類型題目其實(shí)都不涉及什么算法，就是模擬螺旋順序打印的過程，下面我們來模擬一下

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

但是我們可以看出，這樣一圈一圈的模擬下去，邊界條件非常多，很容易出錯(cuò)，這時(shí)候我們第一節(jié)學(xué)的二分法中用的循環(huán)不變量規(guī)則就非常重要了

矩陣的四條邊要么一致遵循左閉右開，要么左開右閉

class Solution {
public:
    vector<vector<int>> generateMatrix(int n)
    {
        vector<vector<int>> res(n,vector<int>(n,0));
        int startx=0,starty=0;  //定義每循環(huán)一個(gè)圈的起始位置
        int loop=n/2; //每個(gè)圈循環(huán)幾次，如果n為奇數(shù)3，那么loop=1，只循環(huán)一圈
        int mid=n/2;  //矩陣中間位置，例如n為3，中間的位置為【1,1】
        int count=1;  //用來給矩陣元素賦值的
        int offset=1; //用來控制循環(huán)遍歷長(zhǎng)度
        int i,j;
        while(loop--)
        {
            i=startx,j=starty;
            //左閉右開
            for(j=starty;j<starty+n-offset;j++) res[startx][j]=count++;
            for(i=startx;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++;
            //第二圈開始，起始位置要各自加一
            startx++,starty++;
            offset+=2;
        }
        //如果n為奇數(shù)，則需要單獨(dú)給矩陣之間的位置賦值
        if(n%2) res[mid][mid]=count;
        return res;
    }
   
};

上面代碼中已經(jīng)把模擬過程詳細(xì)講解了一遍，這里再對(duì)以下兩點(diǎn)特別說明一下：

• starty+n-offset:為什么這里要加上起始位置，因?yàn)榈诙﹂_始起始坐標(biāo)不為0
• offset+=2：為什么要加2，因?yàn)槊孔咭蝗蜕倭藘啥说脑?，賦初值為1是因?yàn)樽裱箝]右開的原則
• 上邊有3 * 3和4 * 4的模擬圖

54. 螺旋矩陣

給你一個(gè) m 行 n 列的矩陣 matrix ，請(qǐng)按照 順時(shí)針螺旋順序 ，返回矩陣中的所有元素。

示例 1：

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

示例 2：

輸入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m ==matrix[i].length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

做這道題目我們也是在遵循循環(huán)不變量規(guī)則，看下面的代碼中我們用的前置++，而不是后置++，細(xì)品（左開右閉），這里判斷循環(huán)結(jié)束的方法也非常巧妙，判斷4個(gè)邊界是否有沖突，有沖突就退出循環(huán)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        
        vector<int> ans;
        if(!matrix.size()) return ans;
        int up=0,down=matrix.size()-1,left=0,right=matrix[0].size()-1;
        while(true)
        {
            for(int i=left;i<=right;++i) ans.push_back(matrix[up][i]);
            if(++up>down) break;
            for(int j=up;j<=down;++j) ans.push_back(matrix[j][right]);
            if(--right<left) break;
            for(int k=right;k>=left;--k) ans.push_back(matrix[down][k]);
            if(--down<up) break;
            for(int L=down;L>=up;--L) ans.push_back(matrix[L][left]);
            if(++left>right) break;
        }
        return ans;
    }
};

總結(jié)

?做這種類型的題目就是要多畫圖模擬，思路清晰就好辦了，還有就是注意邊界條件（遵循循環(huán)不變量規(guī)則）文章來源地址http://www.zghlxwxcb.cn/news/detail-568503.html

到了這里，關(guān)于【代碼隨想錄 | Leetcode | 第四天】數(shù)組 | 螺旋矩陣 | 59-54的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！