java - 为数组实现撤销和重做

Question

我今天在 Java 面试中遇到了这个问题。

我必须实现一个集合，它是一个数组并具有只能在数组末尾执行的 add 和 delete 方法。

除此之外，我还必须实现另外两个方法，即 undo 和 redo 方法，它们只能执行一次。

例如:

令 x 为包含 {1,5,7,9} 的数组。

现在我在其中添加 {44,66,77} 并使其成为 {1,5,7,9,44,66,77}。

现在当我撤消它时，数组应该删除 {44,66,77}。如果我之后重做，它应该回到 {1,5,7,9,44,66,77}。

对于删除也类似。

在复杂性和内存方面实现此目标的最佳方法是什么？

我对面试官的解答:

1. 制作一个字符串字段，用于存储最后一次操作，即“添加”/“删除”。
2. 和一个 hashmap，它将 key 存储为数组的索引，将 value 存储为数组的索引值。

根据面试官的说法，这是一个完全错误的解决方案。

Answer 1

我会这样解决。基本上，会有三个列表。

• 具有实际值的列表
• 撤消列表 带有Command 接口(interface)的实例

• Redo list 带有 Command 接口(interface)的实例(可选，解释如下)

  public interface Command {
      void do();
      void undo();
  }
  

将有两个Command 实现:AddCommand 和RemoveCommand。

• 在 add() 上，创建了 AddCommand 的新实例并将其添加到撤消列表。然后我们调用该命令的do()，它修改实际值并存储添加项的index。
• 在 remove() 上，创建了 RemoveCommand 的新实例并将其添加到撤消列表。然后我们调用此命令的do()，它修改实际值并存储索引和删除项的值。
• 在undo() 上，我们从undo 列表 中提取最后一个命令并执行该命令的undo() 方法。命令推送到重做列表。 AddCommand 和 RemoveCommand 的撤消方法可还原更改。
• 在 redo() 上，我们从 redo 列表 中提取最后一条命令并再次执行 do() 方法。拉出的命令被添加到撤消列表。

另一个优化是删除redo list 并使用undo index 代替。在这种情况下，当您undo() 时，您不需要从列表中删除/添加值，而只需将undo 索引 减一。同样，redo() 会将其增加 1。

因此最终的解决方案将包含值列表、撤消列表和一个索引值。

更新:

对于最简单的情况，只需要一个undo()/redo() 操作，解决方案看起来会更简单。不用undo list 和index，存储最新的命令实例就足够了。因此，您将拥有一个值列表和一个最后撤消命令的实例。