一亩三分地论坛

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

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

[CareerCup] 【第四轮】3.30 - 4.5 Career Cup 1.6

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-3-30 10:33:24 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去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]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)


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


iker01 发表于 2015-4-1 12:37:36 | 显示全部楼层
【解题思路】
transpose the image by the topRight - bottomLeft diagonal, then reverse the rows, it will lead to the 90 degree right rotation of the image
PS: if we try to transpose the image by the primary diagonal, then reverse the rows, we will make it 90 degree left rotation.
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/zhangjiang2013/c5b2f333714271792f9c
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-2 00:14:24 | 显示全部楼层
【解题思路】
Algorithm
1, the cubic has N/2 layers and rotate layer by layer
2.every layer star with layer (0<=layer<=N/2) end with n-layer-1
3. save the top then rotate from right to top, bottom to right ,left to bottom and top to left
the key is the offset is i-first (first<=i<last-1) ;

【时间复杂度】
O(n^2)
【空间复杂度】
O(1)  
【gist link]
https://gist.github.com/michaelniu/794220068601115e0fa7

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-2 03:37:32 | 显示全部楼层
【解题思路】
将矩阵分解成 N/2层,每一层分别旋转,旋转的过程就是对应的矩阵下标的操作了
【时间复杂度】
O(n^2)
【空间复杂度】
因为是in place,所以空间复杂度是O(1)
【gist link】
https://gist.github.com/JamesJi9277/02244a6b64ba80ea9e5b


【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-3 10:58:01 | 显示全部楼层
本帖最后由 alikewmk 于 2015-4-3 11:24 编辑

【解题思路】
把这个问题看成一个类矩阵转置问题,也就是说将列转成行,行转成列,但是注意某些行或列需要倒序排列,实现了向左转和向右转两种方法
【时间复杂度】
O(n^2)
【空间复杂度】
O(n^2)
【gist link】
https://gist.github.com/alikewmk ... -1-6-rotateimg-java
【test case】
Input:
abcd
efgh
ijkl
mnop

Output:
dhlp
cgko
bfjn
aeim


miea
njfb
okgc
plhd

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

chongtianzs 发表于 2015-4-3 12:19:36 | 显示全部楼层
【解题思路】
先沿副对角线对折,再沿水平中线对折。
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/chongtianzs/1f5108b60af0c48c6631


【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jonczbean 发表于 2015-4-4 13:00:12 | 显示全部楼层

【解题思路】
1. Transpose.
2. Flip along the middle of the matrix.
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/Jonbean/b28c1c4275d6dd0749e5

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Godbless 发表于 2015-4-5 03:39:03 | 显示全部楼层
【解题思路】Rotate the image from outermost layer to inner layers. For each layer, extract the top edge with a temporary array, then replace the top edge with the left edge, then replace the left edge with the bottom edge, then replace the bottom edge with the right edge, then replace the right edge with the temporary array.
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link]
https://github.com/StephenWeiXu/ ... blob/master/1_6.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/StephenWeiXu/ ... blob/master/1_6.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-5 05:58:14 | 显示全部楼层
【解题思路】
* Rotate 90 degree does NOT equals to transpose.
*
* An example is
*  1, 2, 3, 4;
*  5, 6, 7, 8;
*  9,10,11,12;
* 13,14,15,16;
*
* Transpose is
*  1, 5, 9,13
*  2, 6,10,14
*  3, 7,11,15
*  4, 8,12,16
*
* Wherease rotation is
*  13, 9, 5, 1
*  14,10, 6, 2
*  15,11, 7, 3
*  16,12, 8, 4
*
*  First lets mark the matrtix by its index
*
*  0,0 0,1 0,2 0,3
*  1,0 1,1 1,2 1,3
*  2,0 2,1 2,2 2,3
*        3,0 3,1 3,2 3,3
*
*        The rotation of 0,0 is
*        0,0 -> 0,3
*        0,3 -> 3,3
*        3,3 -> 3,0
*        3,0 -> 0,0
*
*        And the rotation of 0,1 is
*        0,1 -> 1,3
*        1,3 -> 3,2
*        3,2 -> 2,0
*        2,0 -> 0,1
*
*  As we can see, row 0 becomes column n, column n becomes
*  row n, row n converts to column 0, and column now is row 0.
*
*  Therefore, the rotation of row 0,n column 0, is:
*
*  (0,i) -> (i,n)
*  (i,n) -> (n, n-i)
*  (n, n-i) -> (n-i, 0)
*  (n-i, 0) -> (0,i)
*  
*  And for row i, n-i, colum i, n-i, the definition of transform is:
*  
*  (i,j) => (j, n-i) => (n-i,n-j) => (n-j,i) => (i,j)
*
*  REMEMBER, `n` here is the maximum index, NOT THE SIZE
【时间复杂度】Time complexity: O(m) m is the number of elements in matrix
【空间复杂度】Space complexity: O(1) in place algorithm
【gist link] https://github.com/bxshi/intervi ... matrix_rotation.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/bxshi/intervi ... c/test/1_6_test.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-6 04:52:19 | 显示全部楼层
【solution】
transpose the image and then reverse the rows
【time】
O(N^2)
【space】
O(1)
【gist link]
https://gist.github.com/kelly-us/e8b7a6a04c1261a541ad

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2015-4-6 07:00:45 | 显示全部楼层
【解题思路】
* It would be easier to think if you can write down an example first.
* input:
* 1  2  3  4
* 5  6  7  8
* 9  10 11 12
* 13 14 15 16
* output:
* 13 9 5 1  
* 14 10 6 2  
* 15 11 7 3  
* 16 12 8 4
*
* The core idea is that for we need to assign matrix[j][n-1-i] = matrix[j] for every element
* we can use some temp varialbe to store variables.
* Note: actually we can only use one temp varialbe, if we assgin the values from the end.

【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/leonw007/cfe872307fa7c1a691b6
【test case】included in the link above

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-6 11:01:58 | 显示全部楼层
【解题思路】
1. 先转置,然后交换i and n-i-1行

【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/songpu2015617/c82218dbda465a6575bb

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

beer 发表于 2015-4-6 23:30:19 | 显示全部楼层
【解题思路】
Tips:
* for row = i, column = j (0 <= i < N, 0 <= j < N),
* (i , j) -> (j, N - 1 - i) -> (N - 1 - i, N - 1 - j) -> (N - 1 - j, i) -> (i, j)
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://github.com/drinkbeer/Cod ... /src/CC150_1_6.java
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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