【第三轮】6.16-6.22 CareerCup 1.6

1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
LeetCode原题。这道题的思路没有什么特别的，就是直接旋转image。难点在于对index的处理。
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_6-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
  One time transpose + one time horizontally flip = one time clockwise rotate
【时间复杂度】
  O(N^2)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/489a964e110b4e0e254b

【解题思路】
assume the matrix is rotated clockwise. Since flipping a matrix doesn't need additional space, we can use several flip to do rotation.
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qianhuang/373888abc7fa892cd949

被LZ的帖子刷屏....

【解题思路】
same to the one on book
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/gaoyike/cd4f357ded2de159372d

【解题思路】
和书上思路一样，即 leetcode 的 Rotate Image 一题
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/34ca83e5fb06ba183fe2

【解题思路】
从图像最外圈往最里圈操作，比如[1,2,3;4,5,6;7,8,9], clockwise的话，1和3交换，3和9交换，9和7交换；然后2和6交换，6和8交换，8和4交换；最外圈完成。
一共要进行～3/4×N^2次交换
【时间复杂度】O(n^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/chouclee/38071b3c986338e9ee0c
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
***********TEST**************
1

ClockWise:
1

CounterClockWise:
1
***********TEST**************
1 2
3 4

ClockWise:
3 1
4 2

CounterClockWise:
1 2
3 4
***********TEST**************
1 2 3
4 5 6
7 8 9

ClockWise:
7 4 1
8 5 2
9 6 3

CounterClockWise:
1 2 3
4 5 6
7 8 9
***********TEST**************
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

ClockWise:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

CounterClockWise:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
***********TEST**************
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

ClockWise:
21 16 11 6 1
22 17 12 7 2
23 18 13 8 3
24 19 14 9 4
25 20 15 10 5

CounterClockWise:
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

【解题思路】
Imaging the matrix is layered by layers of numbers in a square loop, we start from outer layer and going inside. We only look at one edge of the square loop start from the left-top corner, and calculate the relative indices for position of the rest edges. swap the four numbers with the corresponding indices. If N is odd, the inner most number does not need to be rotated, since it is the only one number in the layer.
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/3a97e8dc2ec528a15602

【解题思路】
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/3c4ba6084f62f4f56c4d.git