根据具体情况填写清单

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) 

Answer 2

如果我们能得到一个功能fillRight填充到右侧，即

fillRight [0,2,1,0,1,2,0,0] = [0,2,1,0,1,2,2,2] 

那么我们可以很容易地实现完整的解决方案：

fillLeft = reverse . fillRight . reverse 
fill = fillLeft . fillRight 

，所以我们可以用我们的精力fillRight。正如其他人所指出的那样，这是一个简单的状态机，我会在其中阐明了状态转移（注意我如何加入一个参数来跟踪状态）以下方式写：

fillRight' :: Bool -> [Int] -> [Int] 
fillRight' _  []  = [] 
fillRight' True (0:xs) = 2 : fillRight' True xs 
fillRight' False (0:xs) = 0 : fillRight' False xs 
fillRight' _  (1:xs) = 1 : fillRight' False xs 
fillRight' _  (2:xs) = 2 : fillRight' True xs 

然后关闭它关闭通过设置初始状态

fillRight = fillRight' False 

Answer 3

这是比较容易，如果你认为的1为空白来解决这个问题，并0和2在单词字母

import Data.List 

words'::[Int]->[[Int]] 
words' [] = [[]] 
words' x = 
    case rest of 
    (1:after) -> first:words' after 
    _ -> [first] 
    where (first, rest) = break (== 1) x 

fill::[Int]->[Int] 
fill x = intercalate [1] $ 
    map (\x -> replicate (length x) (if 2 `elem` x then 2 else 0)) $ 
    words' x 

首先将输入数据分成“单词”，然后只需将单词映射到所有2 s，如果单个单词2位于单词的内部。

这将在输入大小中工作O（n），甚至可以处理无限输入流。

---

例子

main = do 
    print $ fill [1,0,0,0] 
    print $ fill [1,0,0] 
    print $ fill [0,0,1,0,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,1,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,0,1,2,0,1] 
    print $ fill [0,2,1,0,1,2,0,0] 
    print $ fill [2,0,0,0,1,1,0,1] 
    print $ fill [0,1,0,0,0,0,0,1] 

输出

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

Answer 4

这里是代码高尔夫球溶液：

fill xs = foldr step replicate xs 0 0 where 
    step 0 r l m = r (l + 1) m 
    step 1 r l m = replicate l m ++ 1 : r 0 0 
    step 2 r l m = r (l + 1) 2 

main = do 
    print $ fill [1,0,0,0] 
    print $ fill [1,0,0] 
    print $ fill [0,0,1,0,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,1,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,0,1,2,0,1] 
    print $ fill [0,2,1,0,1,2,0,0] 
    print $ fill [2,0,0,0,1,1,0,1] 
    print $ fill [0,1,0,0,0,0,0,1] 

结果

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