一亩三分地论坛

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

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

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

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

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

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

x
3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array).The stack supports the following operations: push, pop, peek, and isEmpty.


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


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





chouclee 发表于 2014-6-30 00:21:38 | 显示全部楼层
本帖最后由 chouclee 于 2014-6-30 00:31 编辑

【解题思路】
方案一:如果不允许用Stack.size()函数,那么可以使用insertion sort,开一个额外的stack2,对于原stack中的最顶端的element,先pop进一个temp变量,如果比stack2.peek()大的话就直接push进stack2,否则一直将stack2中的元素pop进原stack,直到可以将该element push进stack2。该操作重复至原stack为空。空间为O(n),时间为O(n^2)
方案二:如果允许使用Stack.size()函数,可以使用Merge sort。每次将一个stack的一半pop进另一个新开的stack,然后分别对其排序,需要注意的是,merge操作后顺序会变成descending的,因此还要reverse一下。空间为O(n),时间为O(nlgn)
【时间复杂度】O(n^2) / O(nlgn)
【空间复杂度】O(n)     / O(n)
【gist link】https://gist.github.com/chouclee/7ecae00e8d7b540398a7

补充内容 (2014-6-30 16:09):
第一次是对的,反而编辑错了。。。merge-sort的空间应该是O(nlgn),
并且就算不可以stack.size()函数,也可以自己遍历一遍求出个数,空间和时间的复杂度不变。
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-7-2 11:22:49 | 显示全部楼层
【解题思路】
push and pop of two stacks.
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/af02f882b1f6e4c7132c
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-7-2 12:21:48 | 显示全部楼层
chouclee 发表于 2014-6-30 00:21
【解题思路】
方案一:如果不允许用Stack.size()函数,那么可以使用insertion sort,开一个额外的stack2, ...

Your merge sort actually violates the question constraint, since we can use at most one additional stack. In your merge function, you use a third stack
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-7-2 12:53:19 | 显示全部楼层
ryancooper 发表于 2014-7-2 12:21
Your merge sort actually violates the question constraint, since we can use at most one additional ...

呀,没仔细看这里题目,谢谢指出。
我看的是第5版的书。。。那里是可以用多个stacks。。。
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-7-2 13:29:50 | 显示全部楼层
【解题思路】
If system stack can be considered as valid additional stack. Then we can have a recursive algorithm which leads to simple coding.

Pseudo code for Sorting:
Sort( stack with n elements)
       pop the top element out
       then recursively sort the stack with n-1 elements
       then insert the original top element to the right place

Pseudo Code for insert
Insert(stack with n elements, element)
       if stack is empty or the top element is less than or equal to element, then we just push this element into the stack
       otherwise(similar to the procedure in sort):
                      we fetch the top element of the stack
                      we recursively insert the element into the right place in the stack with n-1 element
                      then we put the original top element back

【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/ryancooper/fd37ad761c15da4c95d4
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-3 07:57:44 | 显示全部楼层
【解题思路】
similar as book solution but perform sort in place, use an additional stack to hold sorted elements (but in descending order so that the sorting can be STABLE!)
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/e69d2cf5c66aee0fa17a
【test case】
Pay attention to cases where identical elements exist!
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-7-3 09:10:35 | 显示全部楼层
【解题思路
keep popping the top element, and inserting it in to the correct position into addition stack, then popping sorted elements back from the additional stack to the original one

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

【空间复杂度】
O(N)

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

使用道具 举报

chouclee 发表于 2014-7-3 10:55:15 | 显示全部楼层
本帖最后由 chouclee 于 2014-7-3 10:59 编辑
ivycheung1208 发表于 2014-7-3 07:57
【解题思路】
similar as book solution but perform sort in place, use an additional stack to hold so ...

捕获.PNG
我这边的第五版说的是“may use additional stacks"

P.S 我搞懂了,我用的是12年出版的第五版,你们用的是13年出版的,囧囧。。。
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-3 11:28:45 | 显示全部楼层
chouclee 发表于 2014-7-2 21:55
我这边的第五版说的是“may use additional stacks"

P.S 我搞懂了,我用的是12年出版的第五版,你们 ...

所噶……不过解析里也有讨论可以用多个unlimited stacks的情况 就像你写的那样嗯……
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-3 16:46:30 | 显示全部楼层
【解题思路】
push and pop of two stacks, sort one element for one time
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/d0deb8471e0a0897fe24
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-4 07:05:35 | 显示全部楼层
【解题思路】
1. at most one extra stack;    insert method to sort
2. if more than one extra stacks are allowed, use merge sort

【时间复杂度】1. O(n^2)  2. O(nlgn)
【空间复杂度】1.O(n)       2.O(n)
【gist link】https://gist.github.com/jyhjuzi/d8ce4f37872a1e255329

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

使用道具 举报

heycinderella 发表于 2014-7-6 07:57:30 | 显示全部楼层

【解题思路】
// Variation of Insertion Sort by using an extra stack. Iterate through every item in the input stack
        // We need to find the right place to insert the item in the result stack
        // we need to pop every item that is larger than it and we can store them by pushing them in the input stack, and then we push the element in the result stack
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/XiaoxiaoLi/34f1cdc635f1365a9f70
回复 支持 反对

使用道具 举报

tangcx18 发表于 2014-7-6 21:25:54 | 显示全部楼层
【解题思路】
Assign the top element to another variable, pop it and
compare with the elements in the other stack. If it is
larger, just push it into the stack. Otherwise, pop elements
from the stack and push into original stack until the
original element is larger.
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/269d132360db2047c50e
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-6 21:54:04 | 显示全部楼层
【解题思路】Use another stack to reverse the source stack, when pop and push find the match value
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/bitcpf/ae426595e81cfcc832a8
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-7 02:50:25 | 显示全部楼层
【解题思路】用一个临时变量来记录stack里的最大值,将该值赋进信的stack,以此类推
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist】
https://github.com/donnice/donnice/blob/master/Q3_6
【Test】
代码里自带
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-7 03:43:50 | 显示全部楼层
【解题思路】
use temp stack to store the sorted elements, pop element from the original stack and insert to the temp stack
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/02b8f9a6206c7739601c
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-7 05:01:34 | 显示全部楼层
【解题思路】use 2 stack for push and pop, sort one for each time
【时间复杂度】o(n^2)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/faf7ac0aa630fff10216

回复 支持 反对

使用道具 举报

pud 发表于 2014-7-7 05:44:42 | 显示全部楼层
【解题思路】
pop element in the original stack to temp, compare temp with sorting stack, push larger element in sorting stack back to the original stack.
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link】https://gist.github.com/yokiy/9cb9c81a0b80be6e1b5e
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 13:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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