一亩三分地论坛

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

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

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

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

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

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

x
3.5 Implement a MyQueue class which implements a queue using two stacks

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

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


A30041839 发表于 2015-4-15 17:09:39 | 显示全部楼层
[solution]
when pushing number x to the queue:
1)push x to the first stack
when popping element from the queue:
1)if the second stack is not empty, pop an element from the second stack,return
2)if the first stack is not empty, move its elements to the second stack, and pop an element from the second stack, return
3)raise an "empty queue" exception
[time]
push,back operates in O(1), front and pop operates in O(n)
[space]
O(n)
[gist]
https://gist.github.com/A30041839/1b30ac21cefde12e2804
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-16 22:00:59 | 显示全部楼层
【解题思路】
# solution
# enqueue -- same as the original operation
# dequeue -- use the second stack to store the old element, and pop the oldest one
【时间复杂度】
# for enqueue and isEmpty O(1) in time
# for dequeue O(n) in time
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/zhangjiang2013/7ca3d2df19679845585c
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-16 23:21:57 | 显示全部楼层
【解题思路】
use one Stack for  Enqueue -----EnQueueStack
* use another Stack for Dequeue----DeQueueStack.
* if DeQueueStack is  empty  then  pop  from EnqueueStack and  push to  DequeueStac one by one.
【时间复杂度】
Enqueue O(1) , Dequeue  O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/f1cc4577a700db8cc4dd
【test case】
https://gist.github.com/michaelniu/f1cc4577a700db8cc4dd(main)
Code is runnable
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-18 22:03:25 | 显示全部楼层
【解题思路】
1. naive: using two stack,because queue is FIFO but stack is FILO, when need to pop element, just push every element from si into s2 and then do s2.pop(). The peek() is the same method, after operation, just push every element from s2 back to s1.
2. instead doing reverse operation each time, we can hold two stacks, one is record newStack, the other hold oldStack, when we need to push(), just push newElem onto newStack, when we need to pop,just do pop operation on oldStack,if oldStack is empty, then push elements from newStack to oldStack in reverse order.
【时间复杂度】
Enqueue O(1) , Dequeue  O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/425d9a0b8ae477ab5aaa
【test case】
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-28 14:56:59 | 显示全部楼层
[solution]
when adding x to the queue, just push it to the first stack.
when removing from the queue:
1)if the second stack is not empty, directly pop from the second stack
2)else if the first stack is not empty, shift all elements to the second stack, and pop from the second stack
3)else throw exception
[time]
add O(1), remove and peek operates in O(n)
[space]
O(n)
[gist]
https://gist.github.com/kelly-us/ca1854a0b3d928a2db46
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-5-2 04:01:13 | 显示全部楼层
【解题思路】
建立两个栈,一个做输入栈,一个做输出栈,并使用延迟加载(lazy loading)的思路,即仅当输出栈没有可以取的元素时,才将输入栈的元素压入输出栈
【时间复杂度】
push O(1)
pop 输出栈为空时O(m), m是输入栈内的元素个数,其他时候O(1)
【空间复杂度】
O(m)
【gist link】
https://gist.github.com/alikewmk ... le-3-5-myqueue-java
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-6-7 09:36:00 | 显示全部楼层
【解题思路】Use one stack1 as the temporary stack to store the newly pushed elements, use the
        other stack2 to store the oldest elements. Once stack2 is empty, move all elements from
        stack1 to stack 2. pop and peek from stack2, while push new element to stack1.
【时间复杂度】O(1) for push, worst case O(n) for peek and pop
【空间复杂度】O(n)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_5.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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