根据具体情况填写清单

我参加了一次面试，面试官给了我一个关于list的问题。

例如，原始列表如下[0,1,0,0,2,0,0,1], the 2应该尽可能地填充列表，除非遇到 1。所以输出将是[0,1,2,2,2,2,2,1].

一个例子：

[0,2,1,0,1,2,0,0]

output:

[2,2,1,0,1,2,2,2]

另一个例子：

[2,0,0,0,1,1,0,1]

output:

[2,2,2,2,1,1,0,1]

如何解决这个问题呢？

您可以使用确定性有限自动机 http://en.wikipedia.org/wiki/Deterministic_finite_automaton有两个状态s_fill and s_keep如下：

fill2 :: [Int] -> [Int]
fill2 xs = s_keep xs []
   where s_keep []     w = reverse w
         s_keep (c:cs) w = if c == 2 then s_fill cs (c:w) else s_keep cs (c:w)
         s_fill []     w = reverse w
         s_fill (c:cs) w = if c == 1 then s_keep cs (c:w)
                          else s_fill cs (2:w)

在该州s_fill， 功能fill2不断填充2到累加器的头部，直到1满足，在这种情况下，DFA 跳转到状态s_keep.

In s_keep, fill2将每个元素本身推回到累加器w until 2遇到，在这种情况下DFA跳转到s_fill.

当剩余列表（s_{keep,fill} 的第一个参数）为空时，递归终止。在这种情况下，该函数返回累加器的相反值，因为头部附近的元素被推得更深，靠近累加器的尾部。

到目前为止，该函数fill2从左到右填2。剩下的工作就是从右到左填充结果(fill2 xs)，可以很容易地得到(fill2 xs)如下：

fill2' xs = reverse $ fill2 $reverse $fill2 xs

Output:

*Main> fill2' [0,1,0,0,2,0,0,1]
[0,1,2,2,2,2,2,1]
*Main> fill2' [0,2,1,0,1,2,0,0]
[2,2,1,0,1,2,2,2]
*Main> fill2' [2,0,0,0,1,1,0,1]
[2,2,2,2,1,1,0,1]

and

*Main> fill2' [0,0,1,0,2,0,1]
[0,0,1,2,2,2,1]

--- 代码的原始版本 ---

（感谢 @ØrjanJohansen 指出下面代码原始版本的问题以及填充的初始状态和方向）。

fill2 :: [Int] -> [Int]
fill2 str = s_fill str []
   where s_keep []     w = reverse w
         s_keep (c:cs) w = if c == 2 then s_fill cs (c:w) else s_keep cs (c:w)
         s_fill []     w = reverse w
         s_fill (c:cs) w = if c == 1 then s_keep cs (c:w)
                          else s_fill cs (2:w)