【第三轮】6.16-6.22 CareerCup 1.6

【解题思路】assume rotate the matrix counterclockwise by 90 degree, do this by first taking the transpose and then flip the matrix horizontally
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/a00d007735cb93527de4

【解题思路】 leetcode原题，通过观察我们可以发现旋转是4个一组进行旋转，所以只需要循环1/4个矩阵就可以了，每次把4个元素顺时针置换一下。
【时间复杂度】O(n^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/a4f9223bb5f678e50cbb
感谢给我code review的小伙伴~

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

【解题思路】
implement layer by layer
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/jyhjuzi/0fb0c4ae211667a73cc9

【解题思路】
和书上一样，一层一层循环
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/yokiy/082210d39d5254f540f6

【解题思路】
Rotating from outer layer to inner layer, like peeling the onion.

【时间复杂度】
O(N^2) since all element(N^2) in martrix will be moved.

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/2722328bce613265cf19

【test case】
create random-generated matrix for test, print out for verification

【解题思路】没思路。。把旋转过程写在记事本上找规律 Orz。。。。 笨死了
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/2d632a5aa056cd0ae7b5

Test 1

Original:

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        

Rotated:

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        

Test 2

Original

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        26        27        28        29        30        

31        32        33        34        35        36        

Rotated:

31        25        19        13        7        1        

32        26        20        14        8        2        

33        27        21        15        9        3        

34        28        22        16        10        4        

35        29        23        17        11        5        

36        30        24        18        12        6        

Test 3

Original

1        

Rotated:

1        

【解题思路】
// [i, j] --> [j, N - i - 1]

【时间复杂度】
O(N^2)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329

【解题思路】Assume the rotate is clockwise, then for each layer, implement left to top, bottom to left, right to bottom and top to right
【时间复杂度】O(N^2) all emements need to be moved
【空间复杂度】O(1)
【gist link】https://gist.github.com/bitcpf/99fafb2eca0cce561a09