data-structures - 检查两个堆栈在 O(1) 空间中是否相等
问题描述
我在一次采访中被问到这个问题:
使用 O(1) 空间检查给定的两个堆栈是否相等(元素的大小和顺序)。
堆栈应保持其早期状态(元素顺序)。
递归使用堆栈空间,因此无效。
我的一位朋友建议使用 String 变量并将一个堆栈中的元素附加到其中并将弹出的元素推送到另一个堆栈,然后从 S2(S1 的旧元素)推送到 S1,并对 S2 执行相同的操作。但这取决于堆栈的大小,因为字符串会根据堆栈的大小而增长。
解决方案
递归与迭代不是这里的问题。问题是如何保持堆栈完好无损,因为完整检查堆栈的唯一方法是清空它。
因此,您需要做的是将弹出的成员存储到临时堆栈中。这不会改变整体空间需求,因为您只推送到其他地方弹出的临时堆栈对象,因此您满足 O(1) 备用需求。
这是迭代解决方案的伪代码:
function stacks_are_equal
precondition: stacks s1, s2
set equal? to true
while s1 is not empty and s2 is not empty
pop x from s1
pop y from s2
push x onto temp1
push y onto temp2
if x ≠ y then
set equal? to false
break out of loop
if s1 is not empty or s2 is not empty set equal? to false
while temp1 is not empty
pop x from temp1
pop y from temp2
push x onto s1
push y onto s2
return equal?
这是递归解决方案:
function stacks_are_equal(s1, s2)
if s1 is empty and s2 is empty return true
if s1 is empty or s2 is empty return false
pop x from s1
pop y from s2
empty? := x = y and stacks_are_equal(s1, s2)
push x onto s1
push y onto s2
return empty?
推荐阅读
- winapi - 如何使用 MinGW 工具集构建 WebView2 应用程序?
- java - 无法在使用 Apache NetBeans 的 JavaFX maven 上使用 JFoenix
- flutter - How to have a Rect move constantly in a linear fashion flutter/flame
- java - 如何在 Netbeans Java 中调用主类
- javascript - 从输入中提取文本内的子字符串并将文本存储在文件夹/目录中
- ruby-on-rails - 这种情况下的 HTTP 状态码(400 或 422)
- python - 使用 Selenium 获取“ul”标签内的文本?
- javascript - 显示所有项目后如何禁用显示更多按钮?分页 API
- c++ - 在 Node.js 中构建和使用 Node.js 的 C(++) 核心依赖项
- postgresql - Postgresql 9.3 副本存档文件夹文件不断添加到主服务器中