20200407
Plan
leetcode每日一题 面试题 01.07. 旋转矩阵
Notes
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例 :
给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ],
原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
方法：
1.暴力法 遍历每一行，用格外的一个数组去保存。 时间复杂度：O（n^2） 空间复杂度：O（n^2）
2.翻转法 观察顺时针旋转90度，其实就是将矩阵先上下翻转后，再主对角线翻转。
5 1 9 11 15 14 12 16 2 4 8 10 13 3 6 7 ------------ =上下翻转=> ------------ 13 3 6 7 2 4 8 10 15 14 12 16 5 1 9 11
15 14 12 16 15 13 2 5 13 3 6 7 =主对角线翻转=> 14 3 4 1 2 4 8 10 12 6 8 9 5 1 9 11 16 7 10 11
上下翻转即：swap(matrix[i][j],matrix[n-i-1][j]) 注意i只需要遍历一半即可，否则又翻转回来了。 主对角线翻转：swap(matrix[i][j],matrix[j][i]) 注意j起始位置=i+1