一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1395|回复: 44
收起左侧

[CareerCup] 【第三轮】6.16-6.22 CareerCup 1.6

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-15 23:21:32 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。

habina 发表于 2014-6-16 16:21:15 | 显示全部楼层
【解题思路】
  One time transpose + one time horizontally flip = one time clockwise rotate
【时间复杂度】
  O(N^2)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/489a964e110b4e0e254b

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zhenzhenanan 发表于 2014-6-17 23:19:59 | 显示全部楼层
本帖最后由 zhenzhenanan 于 2014-6-17 23:30 编辑

【解题思路】
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】
回复 支持 1 反对 0

使用道具 举报

qianhuang 发表于 2014-6-16 10:16:26 | 显示全部楼层
【解题思路】
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
回复 支持 1 反对 0

使用道具 举报

白萝卜 发表于 2014-6-15 23:38:21 | 显示全部楼层
被LZ的帖子刷屏....
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 23:26:44 | 显示全部楼层
【解题思路】
same to the one on book
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/gaoyike/cd4f357ded2de159372d
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-17 08:27:24 | 显示全部楼层
【解题思路】
和书上思路一样,即 leetcode 的 Rotate Image 一题
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/34ca83e5fb06ba183fe2
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-18 00:40:44 | 显示全部楼层
【解题思路】
从图像最外圈往最里圈操作,比如[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
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-18 05:00:27 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-18 21:37:49 | 显示全部楼层
【解题思路】
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/3c4ba6084f62f4f56c4d.git
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-18 22:50:24 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

asdw3276 发表于 2014-6-19 01:57:07 | 显示全部楼层
【解题思路】 leetcode原题,通过观察我们可以发现旋转是4个一组进行旋转,所以只需要循环1/4个矩阵就可以了,每次把4个元素顺时针置换一下。
【时间复杂度】O(n^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/a4f9223bb5f678e50cbb
感谢给我code review的小伙伴~
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-19 06:56:45 | 显示全部楼层
【解题思路】
same to the one on book
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/ed4f00a6b57be514e9a6
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-19 08:34:31 | 显示全部楼层
【解题思路】
implement layer by layer
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/jyhjuzi/0fb0c4ae211667a73cc9
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-21 05:35:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

pud 发表于 2014-6-21 06:18:45 | 显示全部楼层
【解题思路】
和书上一样,一层一层循环
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/yokiy/082210d39d5254f540f6
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-21 08:48:59 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-21 21:47:32 | 显示全部楼层
本帖最后由 aloncgo 于 2014-6-21 21:48 编辑

【解题思路】没思路。。把旋转过程写在记事本上找规律 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        


回复 支持 反对

使用道具 举报

Tsien 发表于 2014-6-21 23:10:22 | 显示全部楼层

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

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

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-22 01:09:24 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 21:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表