本文共 2330 字,大约阅读时间需要 7 分钟。
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example 1:
Given n = 3, return没有给出。
这道题是一道常规的数组题目,给定一个n,返回对应的螺旋矩阵。我的思路就是从外到里一圈一圈地生成,以n=4为例子:
第一步生成最外面的一圈: [ 1, 2, 3, 4] [12, *, *, 5] [11, *, *, 6] [10, 9, 8,7] 然后是中间的一圈 [ 1, 2, 3, 4] [12, 13, 14, 5] [11, 16, 15, 6] [10, 9, 8, 7] 通过列举1-5的螺旋矩阵,可以发现圈数为 ⌊n+12⌋ ,而对于每一圈,起点是(i, i),与第i圈对应,比如第0圈起点是(0, 0),第1圈的起点是(1,1),每一圈都由四个部分组成,分别是水平向右,垂直向下,水平向左,垂直向上,对于每一个部分都用一个for循环生成,知道n和圈r就很容易知道各部分的边界。由于n是奇数时最里面会有仅含一个数字 n2 的一圈,在我的实现里这一圈没法访问到,所以我直接初始化矩阵时,让所有的位置都为 n2 。完整的实现见下面我的代码。这道题目解题方式目前只发现这一种,秉着参考学习的态度,还是贴一下其他的人的代码作为对比,见参考代码。
class Solution {public: vector> generateMatrix(int n) { vector > mtx(n, vector (n, n * n)); for (int r = 0, count = 1; r < (n + 1) / 2; r++) { int i = r, j = r; // go right for (; j < n - r - 1; j++) mtx[i][j] = count++; // go down for (; i < n - r - 1; i++) mtx[i][j] = count++; // go left for (; j > r; j--) mtx[i][j] = count++; // go up for (; i > r; i--) mtx[i][j] = count++; } return mtx; }};
class Solution {public: vector> generateMatrix(int n) { vector > ret( n, vector (n) ); int k = 1, i = 0; while( k <= n * n ) { int j = i; // four steps while( j < n - i ) // 1. horizonal, left to right ret[i][j++] = k++; j = i + 1; while( j < n - i ) // 2. vertical, top to bottom ret[j++][n-i-1] = k++; j = n - i - 2; while( j > i ) // 3. horizonal, right to left ret[n-i-1][j--] = k++; j = n - i - 1; while( j > i ) // 4. vertical, bottom to top ret[j--][i] = k++; i++; // next loop } return ret; }};
这道题算是简单的吧,毕竟思路就是直接按照螺旋矩阵的性质进行生成,唯一需要注意的就是实现的方式,只要想到一圈一圈地去构造,同时细心注意下标的改变应该就能通过。
接下来两个月实习去了,争取保持每周一道题,为秋招做准备,刻苦前进,虚心学习,加油!