这是一个异常大的答案。如果还存在一个优雅的两班轮,我不会感到惊讶,但直到那一个被张贴在这里是我的。
假设您有一个简单的 2D 图,其中 x 轴表示解析步骤,y 轴表示当前 X 和星数之间的差异,n(x)-n(*)。例如,对于输入xx*xx**
,图表将是这样的:
╫
╫ +
╫ + + +
╫ + + +
╬═╧═╧═╧═╧═╧═╧═╧
x x * x x * *
为了使表达式有效,此图在 y 轴上不得达到零或低于零,并且最后 y 的值必须为 1(堆栈上的单个值)。
为您提供了三个用于输入表达式的操作:插入、删除和替换。这个替换操作实际上是两者之一:用*替换x,用x替换*。当您在表达式中间的某处应用插入或删除时,图形会发生变化,以便从该点开始,图形中的所有点都会向上或向下移动。应用替换时,点会在图中向上或向下移动两个槽口。一个有趣的注意事项:我们不必处理删除操作,因为结果与应用相反的插入相同,不同之处在于插入可以始终应用,只有在有可用符号时才删除。
您的目标是找到最少数量的操作。如果我们只观察最终目标(y = 1),那么我们将确定我们必须移动图形并应用尽可能多的替换操作和一个额外的插入操作的缺口数。如果 N(x)-N(*) 的总和为 N,则操作数将为 floor((N-1)/2)。该符号确定要应用哪些操作。
问题是我们必须注意另一个条件,即图形永远不能达到零。为了确定这一点,我们必须首先对我们的表达式应用先前的操作。'Insert x' 添加在开头,'insert *' 出现在末尾,从开头搜索并用 x 替换每个 *,从结尾向后搜索并用 * 替换每个 x。
在这一步之后,我们有了新的表达方式。从头开始迭代并寻找 y=0 的地方。如果有这样的地方,那么你必须在它之前插入一个 x,并在表达式末尾插入一个 * 作为补偿。但请记住,您可能已经这样做了(在开头插入 x,或在结尾插入 *)。如果你有两个插入 x,那么假装它实际上是用 x 替换 *(少一个操作),而忘记必须插入 x。与一对插入 * 类似:删除两个插入 *,然后再应用一个“将 x 替换为 *”。您确实必须应用它,即更改表达式,因为如果从 end 搜索时找到的 x 实际上在您当前位置之前,那么您不能应用替换,因此不能将两个插入操作压缩为一个替换。
继续迭代直到结束,计算额外的操作,并且始终牢记您是否有一个插入 x 和一个插入 *。应该是这样的。最后,您将进行许多操作。