interview prepare

时间：2020-03-15 10:08:29 收藏：0 阅读：82

1. implement stack use two queues.

技术分享图片

 1 #coding:utf-8
 2 class MyStack:
 3     def __init__(self):
 4         self.que1=[]
 5         self.que2=[]
 6        
 7     def push(self,val):
 8         #始终插入que1
 9         self.que1.append(val)
10         
11     
12     def pop(self):
13         if(len(self.que1)==0):
14             raise("Empty stack!")
15         while(len(self.que1)>1):
16             self.que2.append(self.que1.pop(0))
17         
18         res=self.que1.pop(0)
19         
20         while(len(self.que2)>0):
21             self.que1.append(self.que2.pop(0))
22 
23         return res
24 
25 
26 stack=MyStack()
27 stack.push(1)
28 stack.push(2)
29 print(stack.pop())
30 stack.push(4)
31 stack.push(5)
32 print(stack.pop())
33 print(stack.pop())
34 print(stack.pop())
35 print(stack.pop())

2. implement que use two stacks.

技术分享图片

 1 class MyQueue:
 2     def __init__(self):
 3         self.stack1=[]    
 4         self.stack2=[]
 5 
 6     def push(self,val):
 7         self.stack1.append(val)
 8     
 9     def pop(self):
10         if(len(self.stack1)==0):
11             raise("Empty que!")
12         
13         while(len(self.stack1)>1):
14             self.stack2.append(self.stack1.pop())    
15         res=self.stack1.pop()
16         while(len(self.stack2)>0):
17             self.stack1.append(self.stack2.pop())
18         return res
19 
20 que=MyQueue()
21 que.push(1)
22 que.push(2)
23 print(que.pop())
24 que.push(3)
25 que.push(4)
26 print(que.pop())
27 print(que.pop())
28 print(que.pop())
29 print(que.pop())

3. min_stack

技术分享图片

 1 class MinStack:
 2     def __init__(self):
 3         self.stack=[]
 4         self.minstk=[]
 5     
 6     def push(self,x):
 7         if(len(self.stack)==0):
 8             self.stack.append(x)
 9             self.minstk.append(x)
10         
11         tmp=min(self.minstk[-1],x)
12         self.stack.append(x)
13         self.minstk.append(tmp)
14     
15     def pop(self):
16         if(len(self.stack)==0):
17             raise("Empty stack!")
18         
19         self.minstk.pop()
20         return self.stack.pop()
21 
22     def get_min(self):
23         return self.minstk[-1]
24 
25 
26 st=MinStack()
27 st.push(-2)
28 print(st.get_min())
29 st.push(0)
30 print(st.get_min())
31 st.push(-5)
32 print(st.get_min())
33 print("pop:",st.pop())
34 print(st.get_min())

4. valid pop_seq

技术分享图片

class Solution:
    def __init__(self):
        pass
    
    def is_valid(self,push_seq,pop_seq):
        self.push_st=[]
        for i in range(len(push_seq)):
            self.push_st.append(push_seq[i])
            while(len(self.push_st) and self.push_st[-1]==pop_seq[0]):
                self.push_st.pop()
                pop_seq.pop(0)

        return len(self.push_st)==0

s=Solution()
push_seq=[1,2,3,4,5]
pop1=[3,2,5,4,1]
print(s.is_valid(push_seq,pop1))


pop2=[3,1,2,4,5]
print(s.is_valid(push_seq,pop2))

5. simple cal

技术分享图片

 1 class Solution:
 2     BEGIN_STATE=0
 3     NUMBER_STATE=1   
 4     OP_STATE=2
 5 
 6     def calculate(self,s):
 7         self.number_st=[]
 8         self.op_st=[]
 9         
10         num=0;
11         state=BEGIN_STATE
12         compute_flag=0
13         
14         for u in range(len(s)):
15             if(s[i]==‘ ‘):
16                 continue
17             if state==BEGIN_STATE:
18                  if(s[i]>=‘0‘ and s[i]<=‘9‘):
19                      state=NUMBER_STATE
20                  else:
21                      state=OP_STATE
22                  i-=1
23             elif state==NUMBER_STATE:
24                 if(0<=int(s[i]<=9)):
25                     number=number*10+int(s[i])
26                 else:
27                     self.number_st.append(number)
28                     if(compute_flag==1):
29                         right,left=self.number_st.pop(),self.number_st.pop()
30                         res=left+right if(self.op.pop()=="+") else left-right
31                         self.number_st.append(res)
32                     number=0
33                     i-=1
34                     state=OP_STATE
35             elif state==OP_STATE:
36                 if(s[i]=="+" or s[i]=="-"):
37                     self.op_st.append(s[i])
38                     compute_flag=1
39                 elif s[i]==‘(‘:
40                     state=NUMBER_STATE
41                     compute_flag=0
42                 elif (0<=int(s[i]<=9)):
43                     state=NUMBER_STATE
44                     i-=1
45                 elif s[i]==‘)‘:
46                     right,left=self.number_st.pop(),self.number_st.pop()
47                     res=left+right if(self.op.pop()=="+") else left-right
48                     self.number_st.append(res)
49             if number!=0:
50                 self.number_st.append(number)
51                 right,left=self.number_st.pop(),self.number_st.pop()
52                 res=left+right if(self.op.pop()=="+") else left-right
53                 self.number_st.append(res)
54 
55             if(number==0 and len(self.number_st)==0):
56                 return 0
57             
58             return self.number_st[0]

View Code

原文：https://www.cnblogs.com/zijidan/p/12495524.html