Проверьте, равны ли два стека в пространстве O (1) - PullRequest
Новая
       22

Проверьте, равны ли два стека в пространстве O (1)

1 голос
/ 16 января 2020

Меня спросили об этом в интервью:

Проверьте, равны ли данные два стека (размер и порядок элементов), используя пробел O (1).

Стеки должны сохранять свое прежнее состояние (порядок элементов).

Рекурсия использует пространство стека, поэтому недопустимо.

Один из моих друзей предложил использовать переменную String и добавить в нее элементы из одного стека, а pu sh выдал другой, а затем pu sh из S2 (старые элементы S1) в S1 и сделать то же самое с S2. Но это зависит от размера стека, так как строка будет расти в зависимости от размера стека.

Ответы [ 2 ]

1 голос
/ 16 января 2020

Использовать рекурсию ... Вот пример использования java. 

private static boolean equalhelper(Stack<Integer> s1, Stack<Integer> s2)
{
    if(s1.isEmpty() && s2.isEmpty())
        return true;
    if(s1.isEmpty() || s2.isEmpty())
        return false;       

    Integer a=s1.pop();
    Integer b=s2.pop();
    if(!a.equals(b))
    {
        s1.push(a);
        s2.push(b);
        return false;
    }
    else
    {
        boolean check= equalhelper( s1, s2);
        s1.push(a);
        s2.push(b);
        return check;
    }
}
1 голос
/ 16 января 2020

Рекурсия против итерации здесь не проблема. Проблема заключается в том, как оставить стеки нетронутыми, потому что единственный способ проверить стек полностью - это очистить его.

Так что вам нужно сохранить сохраненные элементы во временных стеках. Это не меняет общих требований к пространству, так как вы только добавляете sh во временные объекты стека, которые извлекаются в другом месте, и, таким образом, вы удовлетворяете запасному требованию 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>
...