一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.30-7.6 CareerCup 3.5

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-29 21:15:16 | 显示全部楼层 |阅读模式

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

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

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


回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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




chouclee 发表于 2014-7-2 00:02:40 | 显示全部楼层
【解题思路】
用两个stack,一个专门供enqueue (记做pushStack),一个专门用来dequeue (popStack),每次enqueue,直接把元素push进pushStack,每次dequeue,优先从popStack中pop元素,如果没有元素,就将pushStack中的元素全部pop进popStack,再pop元素。
【时间复杂度】
enqueue: O(1)
dequeue:average O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/chouclee/9fb80a96222d8b8f9d53
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-7-2 11:15:38 | 显示全部楼层
本帖最后由 qianhuang 于 2014-7-2 16:27 编辑

【解题思路】
use a stack to push data, use a stack to pop data.
【时间复杂度】
push: O(1)
pop: O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/061661593396c1ee9602


回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-7-2 12:08:17 | 显示全部楼层
qianhuang 发表于 2014-7-2 11:15
【解题思路】
use a stack to push data, use a stack to pop data.
when we push(), if all data are i ...

I don't understand why you push the data in 'out' stack back in 'in' stack when pushing new data in 'in' stack. These works are redundant.
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-7-2 16:25:49 | 显示全部楼层
ryancooper 发表于 2014-7-2 12:08
I don't understand why you push the data in 'out' stack back in 'in' stack when pushing new data i ...

you are right. Thank you for suggestion.
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-3 05:12:02 | 显示全部楼层
【解题思路】
Implement class API in a similar way as the c++ queue class.
use stackIn to store incoming data, stackOut to pop data. Move all data from stackIn to stackOut in a FILO manner when stackOut runs empty. Update first and last element each time we push or pop (which is the only tricky part in this problem).
【时间复杂度】
O(1) for push
O(N) for pop when data moving is necessary
【空间复杂度】
O(N)
【gist link】
formatting...占坑……
【test case】
(0) -> push(1) -> pop(0) -> push(1) -> push(2) -> pop(1) -> push(2) -> push(3) -> pop(2) -> pop(1) -> pop(0) -> pop(0, error)
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-3 05:19:45 | 显示全部楼层
qianhuang 发表于 2014-7-1 22:15
【解题思路】
use a stack to push data, use a stack to pop data.
【时间复杂度】

I assume your pop() function doesn't have return value, then how would you get the top element value since you don't have a top() function to keep track of it? It seems to me that you're only popping things out while losing information about them, and that's not the way queue works....
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-3 08:03:57 | 显示全部楼层
【解题思路】
本来是比较简单的问题,我为了记录first and last element额外纠结了很多东西…各种debug完以后什么也不想再写了……
一切尽在comments中,最新版已经把first last那些去掉了,可以在revision history里看到……
(其实我只是饿了噗嗤而且之前发的一篇贴莫名其妙消失了TT)
【时间复杂度】
O(1) for push
O(N) for pop
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/40b53ce17164e2126777
【test case】
(0)->push(1)->pop(0)->push(1)->push(2)->pop(1)->push(2)->push(3)->pop(2)->pop(1)->pop(0)->pop(0,error)
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-7-3 08:45:03 | 显示全部楼层
【解题思路】
Divide queue into two stacks, whose top element is head and tail of the queue

【时间复杂度】
O(1)

【空间复杂度】
O(1) amortized cost

【gist link】
https://gist.github.com/chrislukkk/6a9f88001b172ba629ed
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-7-3 10:23:47 | 显示全部楼层
ivycheung1208 发表于 2014-7-3 05:19
I assume your pop() function doesn't have return value, then how would you get the top element val ...

thank you for review.
PS: 怎么点评别人的帖子?我找不到这功能?
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-3 11:27:03 | 显示全部楼层
qianhuang 发表于 2014-7-2 21:23
thank you for review.
PS: 怎么点评别人的帖子?我找不到这功能?

要攒够1000分升到高级农民才可以…我也是最近才发现
话说很少人用c++刷题呐 握爪
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-3 14:48:30 | 显示全部楼层
【解题思路】
用两个stack,一个专门入队,一个专门出队
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/4cd3b04782250d47aa69
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-4 05:43:55 | 显示全部楼层
【解题思路】
one stack for enqueue, the second stack for dequeue;  if the second stack is empty, pop all elements in the first stack and push to the second one.
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】https://gist.github.com/jyhjuzi/0768b50cf97db7914564
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-5 05:09:44 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-7-5 09:30:44 | 显示全部楼层
【解题思路】
Use one stack as the 'push' stack and another as the 'pop' stack. Push all elements to the push stack, and pop from the pop stack. When the pop stack is empty, push all elements from the push stack to the pop stack

【时间复杂度】
POP: amortized O(1), worst case O(n), Push is O(1)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/XiaoxiaoLi/fb712533a48d73b4415f
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-6 01:18:16 | 显示全部楼层
【解题思路】2 stacks, 1 for insert, another for deque
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link】https://gist.github.com/bitcpf/36f4295d5b02d9b14d75
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-6 06:05:02 | 显示全部楼层
【解题思路】2 stacks, enqueue & dequeue
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link】
https://github.com/donnice/donni ... 076dfe699d3994b4cf6
回复 支持 反对

使用道具 举报

pud 发表于 2014-7-6 10:41:39 | 显示全部楼层
【解题思路】
two stacks, one for enqueque, one for dequeue
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】https://gist.github.com/yokiy/6e167df8c936e92241d9
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-6 12:23:14 | 显示全部楼层
【解题思路】one stack for push, one stack for poll
【时间复杂度】O(1) for push; O(n) for poll, depends on the order of operations
【空间复杂度】O(n)
【gist link】https://gist.github.com/nealhu/bdcb03625883ae62f023
回复 支持 反对

使用道具 举报

tangcx18 发表于 2014-7-6 19:56:08 | 显示全部楼层
【解题思路】
Create two stacks, stackNewest and stackOldest.
Push elements into stackNewest and pop elements
from stackOldest. If stackOldest is empty when
trying to pop, pop elements from stackNewest and
push into stackOldest.
【时间复杂度】      
enQueue  deQueue
O(1)     O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/b0b386c99fa59f665c8a
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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