根據具體情況填寫清單

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]