楼主: wrj5518
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
bearkino 2014-6-22 05:37:28 | 只看该作者
全局:
本帖最后由 bearkino 于 2014-6-22 05:40 编辑

【解题思路】
寻找到规律,[j][length - i - 1] = [i][j], 然后新建一个二维数组存储得到结果。
或者,对整个正方形进行切割,对角线斜切,然后循环访问顶上三角形的每一个元素,然后把四个三角形中对应的元素一个个移动,最终整体移动四个三角形。

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

【空间复杂度】
O(n)/O(1)

【gist link】
https://gist.github.com/UncleGarden/be270eb06826b3d1eb8a
回复

使用道具 举报

🔗
bearkino 2014-6-22 05:40:59 | 只看该作者
全局:
本帖最后由 bearkino 于 2014-6-22 05:45 编辑

【解题思路】
寻找到规律,[j][length - i - 1] = i j , 然后新建一个二维数组存储得到结果。
或者,对整个正方形进行切割,对角线斜切,然后循环访问顶上三角形的每一个元素,然后把四个三角形中对应的元素一个个移动,最终整体移动四个三角形。

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

【空间复杂度】
O(n)/O(1)

【gist link】
https://gist.github.com/UncleGarden/be270eb06826b3d1eb8a

上面的帖子修改不了  0 0  有个小错误漏写了这里改正
回复

使用道具 举报

🔗
bearkino 2014-6-22 05:42:51 | 只看该作者
全局:
bearkino 发表于 2014-6-22 05:40
【解题思路】
寻找到规律,[j][length - i - 1] = [j], 然后新建一个二维数组存储得到结果。
或者,对整 ...

[j][length - i - 1] = [i] [j]
回复

使用道具 举报

🔗
Neal 2014-6-22 08:10:45 | 只看该作者
全局:
【解题思路】Rotate elements one by one
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/78f0f5d1a8dca8172bd6
回复

使用道具 举报

🔗
heycinderella 2014-6-22 08:45:31 | 只看该作者
全局:
本帖最后由 heycinderella 于 2014-6-22 08:58 编辑

【解题思路】就是书里的思路了,虽然我理解为什么那么做,还是觉得挺恶心的容易出错呀.Main idea: swith each edge layer by layer until we reach the centre, but this requies an extra array to store each edge.* To save space in swaping edges, we swap elements index by index.
【时间复杂度】
O(n), n是数组里element的个数或者O(n^2)n是给的那个长度。不知道到底哪个
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/XiaoxiaoLi/f46c7fce937cd9bfa78f
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
没写

回复

使用道具 举报

🔗
wendychueng 2014-6-22 12:15:34 | 只看该作者
全局:
【解题思路】rotate each pixel clockwise

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

【空间复杂度】O(1)

【gist link】https://gist.github.com/yupingzhang/9f588278d274c3dcac86
回复

使用道具 举报

🔗
guchang 2014-6-22 13:35:28 | 只看该作者
全局:
【解题思路】基本思路是先转置,然后水平翻转,,,可以把两个步骤合并在一起。妈蛋,看错了,以为要N*M,原来只需要N*N。。。
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/guchang/bbfae52733f0d20162c2
回复

使用道具 举报

🔗
RealityPC 2014-6-23 02:40:59 | 只看该作者
全局:
【解题思路】Same as the algorithm in the book, rotate matrix layer by layer.
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/040facc3085647280764
回复

使用道具 举报

🔗
jason51122 2014-6-23 14:00:55 | 只看该作者
全局:
【解题思路】Rotate the matrix in space. Follow the clockwise order. Be careful about the matrix index. In the inner loop, i won't change but j will.
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/d7ad2b604ae4fd7da1fb
回复

使用道具 举报

🔗
fang_wu 2014-6-23 19:04:33 | 只看该作者
全局:
【解题思路】先按照对角线,再上下换
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/d7ad2b604ae4fd7da1fb
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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