每日编码问题 260：重建一个混乱的数组 - 直觉？

Question

我正在解决下面的问题。

序列 [0, 1, ..., N] 已经打乱了，关于其顺序的唯一线索是一个表示每个数字是否大于或小于上一个数字的数组。给定此信息，重建与其一致的数组。

例如，给定 [None, +, +, -, +]，您可以返回 [1, 2, 3, 0, 4]。

我浏览了这篇文章中的解决方案，但仍然无法理解该解决方案为何有效。如果我在面试时遇到这个问题，我认为我无法想出解决方案。谁能解释其背后的直觉？提前致谢！

Answer 1

这个答案试图给出一个通用策略来寻找解决此类问题的算法。它并不是试图证明为什么给定的解决方案是正确的，而是为实现这种解决方案提供了一条途径。

\n\n

解决此类问题（实际上是各种各样的问题）的一种久经考验的方法是从小示例开始，然后逐步解决。这对于谜题是有效的，但对于现实中遇到的问题也是如此。

\n\n

首先，请注意，这个问题是故意提出的，不会轻易地为您指明正确的方向。它让你觉得其中有某种魔力。仅给出正负列表，如何重构 N 个数字的列表？

\n\n

好吧，你不能。对于 10 个数字，存在10! = 3628800可能的排列。并且只有2\xe2\x81\xb9 = 512可能的标志列表。这是一个非常巨大的差异。大多数原始列表在重建后会完全不同。

\n\n

以下是如何解决该问题的概述：

\n\n

\n
• 从非常简单的例子开始
\n
• 尝试逐步提升，增加一点复杂性
\n
• 如果您发现某些事情似乎是死胡同，请尝试以其他方式增加复杂性；不要在看不到进展的情况上花费太多时间
\n
• 在探索替代方案的同时，重新审视旧的死胡同，因为你可能会获得新的见解
\n
• 尝试递归是否有效:\n\n
  \n
  • 给定 N 的解，我们可以轻松构造 N+1 的解吗？
  \n
  • 甚至更好：给定 N 的解，我们可以轻松构造 2N 的解吗？
  \n
\n
• 给定一个递归解，能否将其转换为迭代解？
\n
• 算法是否做了一些可以推迟到最后的重复性工作？
\n
• ....
\n

\n\n

那么，让我们从简单的开始（在开头为 None 写 0）：

\n\n

\n
• 非常短的列表很容易猜到：\n\n
  \n
  • '0++' \xe2\x86\x92 0 1 2 \xe2\x86\x92 显然只有一种解决方案
  \n
  • '0--' \xe2\x86\x92 2 1 0 \xe2\x86\x92 只有一种解决方案
  \n
  • '0-+' \xe2\x86\x92 1 0 2 或 2 0 1 \xe2\x86\x92 嘿，没有唯一的结果，尽管问题只要求其中一种可能的结果
  \n
\n
• 仅包含加号的列表:\n\n
  \n
  • '0++++++' \xe2\x86\x92 0 1 2 3 4 5 6 \xe2\x86\x92 唯一的可能性
  \n
\n
• 仅包含缺点的列表:\n\n
  \n
  • '0--------'\xe2\x86\x92 7 6 5 4 3 2 1 0 \xe2\x86\x92 唯一可能
  \n
\n
• 列出一个减号，其余加号：\n\n
  \n
  • '0-++++' \xe2\x86\x92 1 0 2 3 4 5 或 5 0 1 2 3 4 或 ...
  \n
  • '0+-+++' \xe2\x86\x92 0 2 1 3 4 5 或 5 0 1 2 3 4 或 ...
  \n
  • \xe2\x86\x92 似乎没有出现非常明显的模式
  \n
\n
• 也许一些递归可以帮助？\n\n
  \n
  • 给定 N 的解，再加一个符号？
  \n
  • 添加加号很简单：只需重复该解决方案并添加最大的加号 1
  \n
  • 经过一番思考后添加一个减号：将所有数字加 1 并添加一个零
  \n
  • \xe2\x86\x92 嘿，我们有一个可行的解决方案，但可能不是最有效的\n\n
    \n
    • 该算法只是附加到现有列表，不需要真正递归地编写它（尽管这个想法是递归表达的）
    \n
    • 可以通过将最大数字存储在变量中来改进附加加号，这样就不需要在每一步中搜索它；似乎没有必要进一步改进
    \n
    • 追加减号比较麻烦：每次追加都需要遍历列表\n\n
      \n
      • 如果我们不附加零，而是附加 -1，并在最后进行添加，会怎么样？
      \n
      • 当只有一个减号时，这显然有效
      \n
      • 当遇到两个减号时，第一次追加-1，第二次追加-2
      \n
      • \xe2\x86\x92 嘿，这适用于遇到的任意数量的减号，只需将其计数器存储在变量中，并在算法结束时与它求和
      \n
    \n
  \n
\n

\n\n

从鸟瞰角度来看，这是提出解决方案的一种可能途径。许多路线通往罗马。引入负数可能看起来很棘手，但在考虑了递归算法一段时间后，这是一个合乎逻辑的结论。

\n

Answer 2

它之所以有效，是因为所有更改都是连续的，要么加一，要么减一，从同一位置开始递增和递减序列。这保证了我们总体上有一个顺序列表。例如，给定任意

[None, +, -, +, +, -]

为了方便垂直翻转，我们可以看到

None   0
+      1
-     -1
+      2
+      3
-     -2

现在只需将它们向上移动两位（占-2）：

2 3 1 4 5 0
 + - + + -