一亩三分地论坛

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

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

[CareerCup] 【第四轮】4.13 - 4..19 Career Cup 3.1

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

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

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

x
3.1 Describe how you could use a single array to implement three stacks.


请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

    【解题思路】
    【时间复杂度】
    【空间复杂度】
    【gist link]
    【test case】(optional,如果觉得比较好,欢迎贴出来分享)

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


laonong15 发表于 2015-4-16 04:08:23 | 显示全部楼层
【解题思路】
   
* Flexible division.
* the first stack start from   beginning of the  array and move forward like :
* Array  [0,1,2,3...]
* stack1 bottom -- > top
* empty when top =-1;
*
* the second stack start from  end of  the   array and  move backward  like
* Array  [..... n-2,n-2,n-1]
* stack2 :top <-- bottom
* empty  when top = n;
*
* The third  star from  in the middle of the array  could be  n/2 or n/3 and move forward, also
*  use two pointer to know the  start and the end of the  stack  Like
*
* Array  [n/2,n/2+1,n/2+2,...]
* stack3 : bottom(start)-->top(end)
* empty  end =start-1
*
* the functions  will be
*
* push(stackNum, data)
*
* pop (stackNum)
*
* isEmpty(stackNum)
*
* when push data to  one  stack   be careful to see if  it collide to the boundary of the other stack.

【时间复杂度】
    【空间复杂度】
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-18 06:27:52 | 显示全部楼层
【解题思路】
将一个数组分成等分的三段,给每一段赋一个指针(所以栈的长度是固定的)
【时间复杂度】
push和pop操作都是O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... 3-1-arraystack-java
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-6-2 12:12:08 | 显示全部楼层
  【解题思路】Divide the array into three equal parts, implement push, pop, peek
        and other basic stack functions to build stacks for each part.
    【时间复杂度】O(1) for both push and pop
    【空间复杂度】O(n)
    【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_1.cpp
    【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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