###48. Rotate Image
题目: https://leetcode.com/problems/rotate-image/
难度:
Medium
思路一：
rotate之前： 之后：
1 2 3 4 13 9 5 1
5 6 7 8 14 10 6 2
9 10 11 12 15 11 7 3
13 14 15 16 16 12 8 4
看网上的hint，是先沿着对角线变换一次，再验证水平中线变换一次
16 12 8 4 13 9 5 1
15 11 7 3 14 10 6 2
14 10 6 2 15 11 7 3
13 9 5 1 16 12 8 4
对角线变换的规律是 (i,j), (n-1-j,n-1-i)
上下变换规律 (i,j),(n-1-i,j)
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n):
for j in range(n):
if j < n-1-i:
matrix[i][j],matrix[n-1-j][n-1-i] = matrix[n-1-j][n-1-i],matrix[i][j]
for i in range(n/2):
for j in range(n):
matrix[i][j],matrix[n-1-i][j] = matrix[n-1-i][j],matrix[i][j]
思路二：
参考这里
http://www.lifeincode.net/programming/leetcode-rotate-image-java/
找规律，一次完成四个数的该有的变换
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
观察一下，第一个数开始的变换是 (0,0)->(0,4)->(4,4)->(4,0) 第二个数的变换是 (0,1)->(1,4)->(4,3)->(3,0)
变换是 (x,y) -> (y, n-1-x) -> (n-1-x,n-1-y)->(n-1-y,x)
然后处理第一行是从(0,0)->(0,n-2)，第二列是(1,1)->(1,n-3).
第i行(i, i)(i, n – 2 – i).终止条件也有了。
虽然都是O(N^2)，但是这个比上面的稍快
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# row, col
for i in range(n):
for j in range(i,n-1-i):
matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j],matrix[n-1-j][i] = \
matrix[n-1-j][i],matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j]
这里的问题是矩阵都是方形，如果不是方形，貌似难很多。