📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2332| 回复: 6
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第四轮】4.13 - 4.19 Career Cup 3.3

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple.
Therefore, in real life, we would likely start a new stack when the previous stack
exceeds some threshold. Implement a data structure SetOf Stacks that mimics
this. SetOf Stacks should be composed of several stacks and should create a
new stack once the previous one exceeds capacity. SetOf Stacks. push() and
SetOf Stacks. pop() should behave identically to a single stack (that is, popO
should return the same values as it would if there were just a single stack).

FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on
a specific sub-stack.

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

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



上一篇:【第四轮】4.13 - 4.19 Career Cup 3.2
下一篇:【第四轮】4.13 - 4.19 Career Cup 3.4
🔗
JamesJi 2015-4-15 22:53:36 | 只看该作者
全局:
本帖最后由 JamesJi 于 2015-4-15 09:56 编辑

【解题思路】
因为说要考虑到容量并且操作要跟单个stack一样,所以想到了利用ArrayList
然后在push的时候需要考虑当前的stack是不是已经满了,如果满了就要new一个新的出来
同样的在进行pop操作时候,需要判断一下pop后的stack是否empty,如果是的就要利用ArrayList的remove将其remove掉Follow up
个人认为要pop指定stack,只需要返回特定的ArrayList中的element即可,然后对相应的stack进行pop操作,可以再加一个函数来实现
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/d3e68b23802de5afc31a
【test case】
回复

使用道具 举报

🔗
A30041839 2015-4-15 23:35:44 | 只看该作者
全局:
[solution]
use a vector to hold multiple stacks. if the last stack is full, then insert a new stack to the vector. push and pop operation all happens on the last stack. To implement the popAt method, just pop the corresponding stack in the vector(is there any trap in this FOLLOW UP?)
[time]
push,pop,popAt operates in O(1)
[space]
O(n)
[gist]
https://gist.github.com/A30041839/876e7667dfa8f6897321
回复

使用道具 举报

🔗
iker01 2015-4-16 22:13:28 | 只看该作者
全局:
【解题思路】
# solution
# use a 2D list to represent the set of stacks
# the last stack is used to store the new element
# when the last stack is full, add a new stack to the end
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/zhangjiang2013/40737ae69adee087fde9
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-OXYN3  2015-4-26 03:09:27
【解题思路】
利用链表存储栈数组和栈编号, 每一个单独的小栈是一个数组
【时间复杂度】
push O(1)
pop  O(1)
popAt O(n*m), n是栈的个数,m是每个栈的长度
【空间复杂度】
O(n*m)
【gist link】
https://gist.github.com/alikewmk ... -3-setofstacks-java
回复

使用道具 举报

🔗
Godbless 2015-6-4 11:33:49 | 只看该作者
全局:
【解题思路】Use another data structure vector in c++ to store different stacks
        For push function, before pushing the value, check if the last stack in the
        vector is full or not. If yes, push back a new stack into the vector and push
        the value into this stack.

        For pop function, after poping the top value, check if the last stack is empty
        or not. If yes, remove this last stack from the vector.
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_3.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复

使用道具 举报

🔗
frozenfire 2015-7-23 02:09:51 | 只看该作者
全局:
[solution]
same as A30041839 except, if want to keep all underlying stacks full except the last one, the pop at will need O(n) time because once it pop out one element, it need to push back all element from topper stacks.
Also, if no need for popat(), using stack<stack<T>> will be really easy to implement.
[time]
push,pop, operates in O(1)
popAt O(n)
[space]
O(n)
[gist]
gist.github.com/frozenfire888/51bdd47e5d78993cfe31
回复

使用道具 举报

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

本版积分规则

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