实现数组的撤消和重做

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接口实例撤消列表

• 带有Command接口实例的重做列表(可选,如下所述)

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

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

• 在add(),新建实例AddCommand创建并添加到撤消列表中.然后我们调用do()这个命令,它修改实际值和index添加项的存储.
• 在remove(),新建实例RemoveCommand创建并添加到撤消列表中.然后我们调用do()此命令,该命令修改实际值以及index已删除项的存储和值.
• 在undo()我们从拉最后的命令撤销列表,并执行undo()该命令的方法.该命令被推送到重做列表.撤消方法AddCommand并RemoveCommand还原更改.
• 在redo()我们从拉最后一个命令重做列表,并执行do()再次方法.拉出的命令被添加到撤消列表中.

另一个优化是删除重做列表并使用撤销索引.在这种情况下undo(),您不需要从列表中删除/添加值,而只需将撤消索引减一.同样,redo()将它增加一个.

因此,最终解决方案将具有值列表,撤消列表和索引值.

更新:

对于最简单的情况,只需要一个undo()/ redo()操作,解决方案看起来会更简单.它不是具有撤销列表和索引,而是存储最新的命令实例.因此,我们将有一个值列表和最后一个撤消命令的实例.

Answer 2

要么我误解了这个问题,要么人们正在过度思考这个问题.这个问题有很多限制,所以:

• 当前内容的数组
• 最后删除项目的额外数组(需要撤消删除/重做添加)
• 前一个数组长度的一个变量(需要撤消添加/重做删除)
• 最后一个操作的一个枚举变量(添加/删除)
• 一个布尔值,表示撤消是否刚刚完成

然后在每个不同的操作上更新这些.不需要堆栈或任何东西,因为不需要多次撤消/重做.