一亩三分地论坛

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

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

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

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

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

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

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


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


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




兰橘清檬 发表于 2014-7-3 10:48:02 | 显示全部楼层
【解题思路】
三个可变大小的栈,可以互相借用空间
【时间复杂度】
O(1) for any operation on the stack
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/JoyceeLee/c95e9541526bcb647a7f
回复 支持 2 反对 0

使用道具 举报

readman 发表于 2014-6-29 23:31:09 | 显示全部楼层
【解题思路】
three pointers for each stack.
【时间复杂度】
【空间复杂度】
【gist link】
https://gist.github.com/gaoyike/4c080dee0aefb287b899

感觉并不好, 很容易出小bug..
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-30 00:25:59 | 显示全部楼层
【解题思路】
First stack start from left most, expanding to right
Third stack start from right most, expanding to left
Second stack start from the middle of the array, expanding to both sides

PS: Double array size when space not enough

【时间复杂度】
O(N) for double space.
Amortized O(1) for both push and pop

【空间复杂度】
O(N) -> size of the array

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

使用道具 举报

donnice 发表于 2014-6-30 07:27:19 | 显示全部楼层
【解题思路】
分别输入3个栈的长度,其和为Array的长度。栈的头top1为0,top2为length_1,top3为length_1+length_2
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】老规矩
import java.util.*;
class Stack{
       
        int top_1;
        int top_2;
        int top_3;
        int l_1 ;
        int l_2;
        int l_3;
        int stackNo;
        Object[] stElem;

        public Stack(int l_1,int l_2, int l_3){
                top_1 = 0;
                top_2 = l_1;
                top_3 = l_1+l_2;
                stElem = new Object[l_1+l_2+l_3];
                }
       
        public  Object pop(int stackNo){       
                if(stackNo == 1){
                        if(top_1 == 0)
                                return null;
                        else
                                return stElem[--top_1];
                }
                else if(stackNo == 2){
                        if(top_2 == l_1-1)
                                return null;
                        else
                                return stElem[--top_2];
                       
                }
                else{
                        if(top_3 == l_1+l_2-1)
                                return null;
                        else
                                return stElem[--top_3];
                       
                }
        }
       
       

        public void push(int stackNo, Object e){
                switch(stackNo){
                        case 1: stElem[top_1++] = e;
                                    break;
                        case 2: stElem[top_2++] = e;
                                        break;
                        case 3:        stElem[top_3++] = e;
                                        break;
                }
        }

        public void display(){
                for(int i = top_1-1; i>=0;i--)
                        System.out.print(stElem[i]+" ");
                System.out.println();
                for(int j = top_2-1; j>top_1-1; j--)       
                        System.out.print(stElem[j]+" ");
                System.out.println();
                for(int k = top_3-1; k>top_2-1; k--)       
                        System.out.print(stElem[k]+" ");
                System.out.println();
        }
}

public class Q3_1{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                System.out.print("请分别输入栈1,2,3长度:");
                int l_1 = sc.nextInt();
                int l_2 = sc.nextInt();
                int l_3 = sc.nextInt();
                Stack st = new Stack(l_1,l_2,l_3);               
                System.out.print("请输入栈1元素:");
                for(int i = 0; i<l_1; i++)
                        st.push(1,sc.nextInt(10));
                System.out.print("请输入栈2元素:");
                        for(int j = l_1; j<l_1+l_2; j++)
                        st.push(2,sc.nextInt());
                System.out.print("请输入栈3元素:");
                for(int k = l_1+l_2-1; k<l_1+l_2+l_3-1; k++)
                        st.push(3,sc.nextInt());
                st.display();
                System.out.print("请输入想要除首的栈:");
                st.pop(sc.nextInt());
                st.display();
                System.out.print("请输入想要插入的栈数和元素:");
                int stNo = sc.nextInt();
                int e = sc.nextInt();
                st.push(stNo, e);
                st.display();
        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-30 12:12:40 | 显示全部楼层
【解题思路】Put all elements in an array, data is arranged as [statck1 element, statck2 element, statck3 element, statck1 element,statck2 element,...,statck3 element] . Double the array size when one stack is full. Shrink the array size to half when all three stacks are one-quarter size full
【时间复杂度】
average O(1) for push() and pop()
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/chouclee/184a1b3674cd88df29f5
回复 支持 反对

使用道具 举报

pud 发表于 2014-7-1 04:48:49 | 显示全部楼层
【解题思路】先定义三个元素的array,记录第二个元素的位置start。stack1都添加在array[0],stack3添加在array[n], stack2 添加在start
但是之前设定的三个元素不好删除,要是前面删除位置就变了
【时间复杂度】
O(1) for push() and pop()
【空间复杂度】
O(n)
【gist link】
   https://gist.github.com/yokiy/4e228802469995021bfa
回复 支持 反对

使用道具 举报

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

使用道具 举报

monkerek 发表于 2014-7-1 19:53:45 | 显示全部楼层
【解题思路】
  evenly divide an array into 3 parts to implement stacks separately.
  use 3 flags to indicate the top index of each stack. check before operation if current stack is full or empty
  this solution only works for constant length of array
【时间复杂度】
O(1)
【空间复杂度】
O(1) for constant length of array
【gist link】
https://gist.github.com/monkerek/1328ad30aacc9dfe0d31
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-1 22:20:05 | 显示全部楼层
【解题思路】Separate the array into 3 sub array, use each of them as an stack
【时间复杂度】O(1)
【空间复杂度】O(1) for constant length of array
【gist link】https://gist.github.com/bitcpf/34c6d76cf8dd6a15e17e
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-2 09:55:36 | 显示全部楼层
【解题思路】Partition the array into 3 parts, each stack uses one of them
【时间复杂度】O(1) for pop and push
【空间复杂度】O(n)
【gist link】https://gist.github.com/nealhu/f82239cf57ed8dfafaa5
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-2 13:35:10 | 显示全部楼层
【解题思路】
three partitions: stack 1 starts from index 0 and grows to the right; stack 2 starts from 1/3*size and grows to the right, in order to enhance the array usage, this stack is movable; stack 3 starts from the end and grows to the left.
【时间复杂度】
Amortized O(1) if move stack 2 is not involved, otherwise O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/f2e1f8627b141e38e423
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-3 01:43:06 | 显示全部楼层
【解题思路】
三个固定大小的栈
【时间复杂度】
O(1) for any operation on the stack
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/JoyceeLee/35063250c87856a764f6
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-3 05:58:22 | 显示全部楼层
【解题思路】
divide the array into three parts for three stacks. If one stack is full, shift the next one and make a room for the full one.
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】https://gist.github.com/jyhjuzi/6dfe30952ebb223cc1e3
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-6 06:23:11 | 显示全部楼层
【解题思路】Use a circular array to shift elements when there is no room for current stack.
【时间复杂度】O(N) for push() and O(1) for other operations
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/b19f532fc5d4fcc3f190
回复 支持 反对

使用道具 举报

tangcx18 发表于 2014-7-6 19:25:29 | 显示全部楼层
【解题思路】 Partition the array into three equal parts, and position each stack by a pointer
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/2fc833043d654ab01d10
回复 支持 反对

使用道具 举报

guchang 发表于 2014-7-6 22:19:56 | 显示全部楼层
【解题思路】
三个不可变大小的stack。貌似这样难度回小很多,,呵呵
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/guchang/29b1c82ee2604e338268
回复 支持 反对

使用道具 举报

Tsien 发表于 2014-7-6 23:57:20 | 显示全部楼层
本帖最后由 Tsien 于 2014-7-6 23:59 编辑

【发错,待修正】
//【解题思路】
//利用递归,从中间向两边走
//【时间复杂度】
//O(n)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-7 02:05:07 | 显示全部楼层
【解题思路】
分成三个固定大小的栈(这样其实不好,长度应是可变的)
【时间复杂度】
O(1) for any operation on the stack
【空间复杂度】
O(N)
【gist link】https://gist.github.com/hilda8519/7137b113481e228481f2
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-7 06:03:19 | 显示全部楼层

【解题思路】
fixed-size 3 stack
【时间复杂度】
O(1) 实为数组index操作模拟
【空间复杂度】
O(1)  
【gist link】
https://gist.github.com/xun-gong/8f411da215c2de327575
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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