矩阵

顺时针旋转矩阵90度

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example

Given input matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

算法以及代码

算法查看注释

逆时针旋转矩阵90度

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (anti clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example

Given input matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [3,6,9],
  [2,5,8],
  [1,4,7]
]

算法以及代码

算法查看注释

矩阵以螺旋序排列

将一个m x n的矩阵以螺旋序排列并返回。

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

举例

输入：

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

输出：

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

算法以及代码

I traverse right and increment rowBegin, then traverse down and decrement colEnd, then I traverse left and decrement rowEnd, and finally I traverse up and increment colBegin.

when traverse left or up it has to check whether the row or col still exists to prevent duplicates.

查看算法

以螺旋序生成矩阵

给一个数字n，返回一个n x n的矩阵，矩阵以螺旋序生成。

举例

输入：

3

输出：

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

算法以及代码

本题与矩阵以螺旋序排列有异曲同工之妙。所以解法思路也一样。

从1到n*n依次找到在矩阵中对应的下标。很容易看出来矩阵下标的增长共有4个方向，我们以[rowInc, colInc] 分别来表示一维和二维下标的增量。可知四个取值分别为：

[0, 1], [1, 0], [0, -1], [-1, 0]

我们以rowBegin, rowEnd, colBegin, colEnd分别来表示下标增长的四个边界。每次下标越过边界时，需要重置 边界值和下标值。分析可得如下四种情况：

1. row > rowEnd，此时向右增长到边界，需要向下增长，同时重置下标值。colEnd–;row, col = rowEnd, colEnd; rowInc, colInc = 0, -1。
2. 同上分析，分别可得出其他三种情况的取值。具体见代码。

查看算法