【第三轮】6.30-7.6 CareerCup 3.1

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、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
三个可变大小的栈，可以互相借用空间
【时间复杂度】
O(1) for any operation on the stack
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/JoyceeLee/c95e9541526bcb647a7f

【解题思路】
分别输入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();
        }
}

【解题思路】
stack 1 grows right from left-end, stack 2 grows left from right-end, stack 3 grows right from center. move stack 3 when necessary.
【时间复杂度】
O(N) for push operation
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/b9921dbc553ed0fc31d3
【test case】
intput: see code.
output:
|1 1|0 0 0 0 0 0 0 0 |3 3|0 0 0 0 0 0 |2 2 |
|1 1|0 0 0 0 0 0 0 0 |3 3 4 4 4|0 0 0 |2 2 |
|1 1|0 0 0 0 0 0 0 0 |3 3 4 4 4||5 5 5 2 2 |
|1 1|0 0 0 0 |3 3 4 4 4|0 0 0 |6 5 5 5 2 2 |
|1 1 7 7 7 7||3 3 4 4 4|0 0 0 |6 5 5 5 2 2 |
|1 1 7 7 7 7 8|0 |3 3 4 4 4|0 |6 5 5 5 2 2 |
|1 1 7 7 7 7 8|0 |3 3 4 4 4 9||6 5 5 5 2 2 |
|1 1 7 7 7 7 8||3 3 4 4 4 9 10||6 5 5 5 2 2 |
No space available!
Pop out: 8
|1 1 7 7 7 7|0 |3 3 4 4 4 9 10||6 5 5 5 2 2 |
Pop out: 6
|1 1 7 7 7 7|0 |3 3 4 4 4 9 10|0 |5 5 5 2 2 |
Pop out: 10
|1 1 7 7 7 7|0 |3 3 4 4 4 9|0 0 |5 5 5 2 2 |
|1 1 7|0 0 0 0 |3 3 4|0 0 0 0 0 0 0 0 |2 2 |
|1 1 7|0 0 0 0 |3 3 4|0 0 0 0 0 0 0 0 0 0 |
Empty stack!
Press any key to continue . . .

【解题思路】
three pointers for each stack.
【时间复杂度】
【空间复杂度】
【gist link】
https://gist.github.com/gaoyike/4c080dee0aefb287b899

感觉并不好, 很容易出小bug..

【解题思路】
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

【解题思路】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

【解题思路】先定义三个元素的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

【解题思路】
  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

【解题思路】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

【解题思路】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