堆叠和排队亚马逊面试问题

Question

描述

你得到了一个由n个整数组成的数组A。您必须创建一个队列和给定整数的堆栈。队列应该只包含素数，堆栈应该只包含复合数。数组中的所有数字都将为。形成堆栈和队列的规则是，您应该能够使用pop和dequeue操作生成数组。注意：请仔细阅读此解释

如果数组A包含5个整数：7、21、18、3、12，则队列和堆栈的内容为：队列：7，3堆栈：12、18、21现在，如果您遵循堆栈和队列的规则，那么您可以使用堆栈的弹出操作和队列的出列操作生成数组，如下所示：

dequeue from queue : 7
pop from stack : 7 , 21
pop from stack : 7 , 21 , 18
dequeue from queue : 7 , 21 , 18 , 3
pop from stack : 7 , 21 , 18 , 3 , 12

因此，对于每个数组A，您必须在第一行打印队列的内容，在第二行打印堆栈的内容。

输入格式第一行包含一个整数n作为输入，表示数组中整数的总数。下一行包含n个空格分隔的整数，表示数组A的元素。您的输出应该打印两个数组，每行一个。第一行应该是队列的内容，第二行应该是堆栈的内容。

输出格式在第一行打印队列的内容，在第二行打印堆栈的内容。

样本输入

5
7 21 18 3 12

样本输出

7 3 
12 18 21 

我的代码

backwas = input()
num1 = list(map(int, input().split()))
dic = {}
for num in num1:
output = []
for i in range(2,num+1):
if num%i == 0:
output.append(i)
for item in set(output):
output1 = list(set(output))
dic[num] = output1
prime = []
comp = []
for num in num1:
list1 = []
list1 = list(dic[num])
if len(list1) != 1:
comp.append(str(num))
else:
prime.append(str(num))

print(" ".join(prime))
print(" ".join(comp))

我的代码出现问题

如果你阅读得当，你会立即注意到这个问题的难点是按照正确的顺序列出两个列表，也就是说，当对它们进行一些操作时，它们会返回原始列表。我的代码无法执行此操作。我应该如何解决此问题？

Answer 1

问题的jist要求给定一个以空格分隔的整数序列，将列表分为存储在Queue中的素数和存储在Stack中的复合整数。按FIFO顺序输出que中的素数，按LIFO顺序输出堆栈中的复合整数。

队列是一种线性先进先出(FIFO(数据结构。如果我们使用append((实现enqueue((，使用pop((实现dequeue(。但是，列表执行此操作的速度相当慢，因为在开头插入或删除元素需要O(n(时间。使用集合mnodule中的出列类是首选的队列实现机制，因为追加和弹出操作需要O(1(时间。

堆栈是线性后进先出(LIFO(或先进先出(FILO(数据结构。与队列类似，可以使用列表数据结构来实现堆栈，但与队列情况一样，如果列表很长，则会出现性能问题。因此，出列类是实现堆栈的首选类。

根据指令，第一行输入给出第二行输入中的整数数
第二行由空格分隔的整数组成。输出由两行组成。

• 第一个输出行应该按照输入的顺序显示输入中的素数
• 第二行应该按照输入的相反顺序显示输入的复合数字

以下是我解决问题的方法：

#Utility to detect a Prime
def is_prime(n: int) -> bool:
"""
Integer -> Boolean
returns True if n is a prime number
"""
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(sqrt(n))
f = 5
while f <= r:
if n%f == 0:
return False
if n%(f+2) == 0:
return False
f +=6
return True

使用列表方法

# Implementation with Lists assuming instr is list of integers
def list_method(instr: str):
qlist = []
stklist = []
inLst = list(map(lambda x:int(x) ,instr.split()))
for n in inLst:
if is_prime(n):
qlist.append(n)
else:
stklist.append(n)
print(" ".join(map(lambda x: str(x), qlist)))
print(" ".join(map(lambda x: str(x), stklist[::-1])))

使用出队类

from collections import deque
def queue_method(instr: str):
q = deque()
stk = deque()
inLst = list(map(lambda x:int(x) ,instr.split()))
for n in inLst:
if is_prime(n):
q.append(n)
else:
stk.append(n)
print(" ".join([str(q.popleft()) for i in range(len(q))]))
print(" ".join([str(stk.pop()) for i in range(len(stk))]))

Answer 2

这里有一个简单的方法，使用埃拉托斯特尼筛和2个数组。

num1 = [7,21,18,3,12]    # your list
n = max(num1)
prime = [True for i in range(n+1)] 
p = 2
while (p * p <= n):  #creating a Sieve using standard operations
if (prime[p] == True): 
for i in range(p * p, n+1, p): 
prime[i] = False
p += 1
prim, comp = [], []
for i in num1:
if prime[i]:
prim.append(i)
else:
comp.append(i)
for i in prim:
print(i, end = " ")
print()
for i in comp[::-1]:
print(i, end = " ")
print()