gpt4 book ai didi

data-structures - 检查两个堆栈在 O(1) 空间中是否相等

转载 作者:行者123 更新时间:2023-12-05 02:09:30 25 4
gpt4 key购买 nike

我在面试中被问到这个:

使用 O(1) 空间检查给定的两个堆栈是否相等(元素的大小和顺序)。

堆栈应保持其早期状态(元素顺序)。

递归使用堆栈空间,因此无效。

我的一位 friend 建议使用 String 变量并将一个堆栈中的元素附加到其中,然后将弹出的内容推送到另一个堆栈,然后从 S2(S1 的旧元素)推送到 S1,并对 S2 执行相同的操作。但这取决于堆栈的大小,因为字符串会根据堆栈的大小而增长。

最佳答案

递归 vs 迭代不是这里的问题。问题是如何保持堆栈完好无损,因为检查完整堆栈的唯一方法是清空它。

所以您需要做的是将弹出的成员存储到临时堆栈中。这不会改变整体空间需求,因为您只需要压入在其他地方弹出的临时堆栈对象,因此您可以满足 O(1) 的备用需求。

这是迭代解决方案的伪代码:

<b>function</b> stacks_are_equal
<b>precondition</b>: stacks <i>s1</i>, <i>s2</i><br/>
<b>set</b> <i>equal?</i> to true<br/>
<b>while</b> <i>s1</i> is not empty and <i>s2</i> is not empty
pop <i>x</i> from <i>s1</i>
pop <i>y</i> from <i>s2</i>
push <i>x</i> onto <i>temp1</i>
push <i>y</i> onto <i>temp2</i><br/>
<b>if</b> <i>x</i> ≠ <i>y</i> then
<b>set</b> <i>equal?</i> to false
<b>break</b> out of loop<br/>
<b>if</b> <i>s1</i> is not empty or <i>s2</i> is not empty <b>set</b> <i>equal?</i> to false<br/>
<b>while</b> <i>temp1</i> is not empty
pop <i>x</i> from <i>temp1</i>
pop <i>y</i> from <i>temp2</i>
push <i>x</i> onto <i>s1</i>
push <i>y</i> onto <i>s2</i><br/>
<b>return</b> <i>equal?</i>

这是递归的解决方案:

<b>function</b> stacks_are_equal(<i>s1</i>, <i>s2</i>)
<b>if</b> <i>s1</i> is empty and <i>s2</i> is empty <b>return</b> true
<b>if</b> <i>s1</i> is empty or <i>s2</i> is empty <b>return</b> false<br/>
pop <i>x</i> from <i>s1</i>
pop <i>y</i> from <i>s2</i><br/>
<i>empty?</i> := <i>x</i> = <i>y</i> and stacks_are_equal(<i>s1</i>, <i>s2</i>)<br/>
push <i>x</i> onto <i>s1</i>
push <i>y</i> onto <i>s2</i><br/>
<b>return</b> <i>empty?</i>

关于data-structures - 检查两个堆栈在 O(1) 空间中是否相等,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59766940/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com