LeetCode:Spiral Matrix I II

简介:
Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, 
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

 

打印螺旋矩阵

逐个环的打印, 对于m *n的矩阵,环的个数是 (min(n,m)+1) / 2。对于每个环顺时针打印四条边。

注意的是:最后一个环可能只包含一行或者一列数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class  Solution {
public :
     vector< int > spiralOrder(vector<vector< int > > &matrix) {
         int  m = matrix.size(), n;
         if (m != 0)n = matrix[0].size();
         int  cycle = m > n ? (n+1)/2 : (m+1)/2; //环的数目
         vector< int >res;
         
         int  a = n, b = m; //a,b分别为当前环的宽度、高度
         for ( int  i = 0; i < cycle; i++, a -= 2, b -= 2)
         {
             //每个环的左上角起点是matrix[i][i],下面顺时针依次打印环的四条边
             for ( int  column = i; column < i+a; column++)
                 res.push_back(matrix[i][column]);
             for ( int  row = i+1; row < i+b; row++)
                 res.push_back(matrix[row][i+a-1]);
             if (a == 1 || b == 1) break ; //最后一个环只有一行或者一列
             for ( int  column = i+a-2; column >= i; column--)
                 res.push_back(matrix[i+b-1][column]);
             for ( int  row = i+b-2; row > i; row--)
                 res.push_back(matrix[row][i]);
         }
         return  res;
     }
};

 


Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example, 
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

本质上和上一题是一样的,这里我们要用数字螺旋的去填充矩阵。同理,我们也是逐个环的填充,每个环顺时针逐条边填充                 本文地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class  Solution {
public :
     vector<vector< int > > generateMatrix( int  n) {
         vector<vector< int > > matrix(n, vector< int >(n));
         int  a = n; //a为当前环的边长
         int  val = 1;
         for ( int  i = 0; i < n/2; i++, a -= 2)
         {
             //每个环的左上角起点是matrix[i][i],下面顺时针依次填充环的四条边
             for ( int  column = i; column < i+a; column++)
                 matrix[i][column] = val++;
             for ( int  row = i+1; row < i+a; row++)
                 matrix[row][i+a-1] = val++;
             for ( int  column = i+a-2; column >= i; column--)
                 matrix[i+a-1][column] = val++;
             for ( int  row = i+a-2; row > i; row--)
                 matrix[row][i] = val++;
         }
         if (n % 2)matrix[n/2][n/2] = val; //n是奇数时,最后一个环只有一个数字
         return  matrix;
     }
};

 






本文转自tenos博客园博客,原文链接:http://www.cnblogs.com/TenosDoIt/p/3774747.html,如需转载请自行联系原作者

目录
相关文章
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
86 1
Leetcode 240. Search a 2D Matrix II
具体思路就是每一行倒着扫,扫到第一个比target小的数就跳到下行,如果等于当然是直接返回true了,如果下一行还比target小就继续跳下一行,直到最后一行。 为啥这么做是可行的? 可能我比较笨,想了半天才想到。 因为每一列都是增序的,举个例子,假设matrix[0][5] > target,那么[0][5]位置右下(包含右和下)所有元素不可能比target小。
48 0
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。
108 0
LeetCode 378. Kth S Element in a Sorted Matrix
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
75 0
LeetCode 329. Longest Increasing Path in a Matrix
|
算法
LeetCode 240. Search a 2D Matrix II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
82 0
LeetCode 240. Search a 2D Matrix II
|
算法
LeetCode 74. Search a 2D Matrix
编写一个有效的算法,搜索m×n矩阵中的值。 此矩阵具有以下属性: 每行中的整数从左到右排序. 每行的第一个整数大于前一行的最后一个整数.
81 0
LeetCode 74. Search a 2D Matrix
|
存储 索引
LeetCode 73. Set Matrix Zeroes
给定一个m * n 的矩阵,如果当前元是0,则把此元素所在的行,列全部置为0. 额外要求:是否可以做到空间复杂度O(1)?
103 0
LeetCode 73. Set Matrix Zeroes
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 59. Spiral Matrix II
给定正整数n,以螺旋顺序生成填充有从1到n2的元素的方阵。
93 0