haskell - 根据具体情况填写 list

Question

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

例如，原始列表类似于[0,1,0,0,2,0,0,1]，2应该填充列表尽可能多，除非遇到 1。因此输出将为 [0,1,2,2,2,2,2,1]。

一个例子:

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

输出:

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

另一个例子:

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

输出:

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

如何解决这个问题？

Answer 1

您可以使用 Deterministic Finite Automaton有两种状态 s_fill 和 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。

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

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

到目前为止，函数fill2从左到右填充了2。剩下的工作就是对(fill2 xs)的结果从右向左填充，可以通过(fill2 xs)的反面轻松获得，如下:

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

输出:

*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]

和

*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)