堆栈和队列亚马逊面试问题

Question

描述给定一个包含 n 个整数的数组 A。您必须创建一个给定整数的队列和堆栈。队列应仅包含素数，堆栈应仅包含合数。数组中的所有数字都是 。形成堆栈和队列的规则是您应该能够使用弹出和出队操作生成数组。注：请仔细阅读本说明假设数组 A 包含 5 个整数： 7 , 21 , 18 , 3 , 12 ，那么队列和堆栈的内容将为： 队列 : 7 , 3 堆栈 : 12 , 18 , 21 现在，如果您遵循堆栈和队列的规则，那么您会发现可以使用堆栈的弹出操作和队列的出列操作来生成数组，如下所示：dequeue from queue : 7pop from stack : 7 , 21pop from stack : 7 , 21 , 18dequeue from queue : 7 , 21 , 18 , 3pop from stack : 7 , 21 , 18 , 3 , 12因此，对于每个数组 A，您必须在第一行中打印队列的内容，在第二行中打印堆栈的内容。输入格式 第一行包含一个整数 n 作为输入，表示数组中整数的总数。下一行包含 n 个空格分隔的整数，表示数组 A 的元素。您的输出应打印两个 array ，每行一个。第一行应该是队列的内容，第二行应该是堆栈的内容。输出格式 第一行打印队列的内容，第二行打印堆栈的内容。样本输入57 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] = output1prime = []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

问题的要点要求给定一系列空格分隔的整数，将列表分为存储在队列中的素数和存储在堆栈中的复合整数。按 FIFO 顺序输出队列中的素数，并按 LIFO 顺序输出堆栈中的复合整数。

队列是线性先进先出 (FIFO) 数据结构。如果我们使用append()来实现enqueue()，使用pop()来实现dequeue()，那么List数据结构就可以用作队列。然而，列表为此目的非常慢，因为在开头插入或删除元素需要 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()