Store Page
A=B
All Discussions Screenshots Artwork Broadcasts Videos Workshop News Guides Reviews

A=B

Store Page
A=B > Guides > rahnoc's Guides
Not enough ratings
6-2 回文串 2 (Palindrome 2)
By rahnoc
針對 「6-2 回文串 2」 該題目的解題歷程。

透過某種加工，讓題目變成可方便我們處理的資料結構。
分析回文與否對輸出的影響。
將中繼輸出轉為題目要求的最終輸出。
2
   
Award
Favorite
Favorited
Unfavorite
Created by
rahnoc
Offline
Category: Walkthroughs
Languages: Traditional Chinese
Posted
Updated
19 Jan, 2023 @ 12:31am
25 Jan, 2023 @ 7:39am
246 Unique Visitors
1 Current Favorites
Guide Index
Overview
字元'a' 的陷阱 
當沒有迴圈控制關鍵字可用時，該怎麼辦？ 
進行比對 
* 補充 1 
* 補充 2 
程式碼 
Comments
字元'a' 的陷阱
題目只接受兩種輸出 "true"， "false"。 代表著程式在將字串處理成 "true" 或 "false" 時必須停止。

若你的程式會處理包含其中的單一字元，可能會停不下來，或是變成別的結果。

e.g.

a = 隨便

則原本該停下來的 "false" 一定會被改成 "f隨便lse"。
> false > f隨便lse

下列字元使用時要注意： a e f l r s t u 。
其中的 a 甚至可能包含在題目輸入中，小心不要有 "a = 什麼" 這代換指令。
當沒有迴圈控制關鍵字可用時，該怎麼辦？
  • a. 針對輸入字串 "xxxxx"，如果每個 x 後都加入分隔符號 '|'

    x = x|

    最後輸出
    > x|x|x|x|x|

    看起來沒什麼用。


  • b-1. 那麽如果改成將每個字元加倍 (x 變成 xx) 後，右側再加入分隔符號 '|'

    x = xx|

    最後輸出
    > xx|xx|xx|xx|xx|

    嗯⋯⋯？


  • b-2. 針對 b-1 的輸出，如果 | 右邊有連續的非分隔符號字元，就將 | 右移一個字元

    |xx = x|x

    輸出
    > xx|xx|xx|xx|xx| > xxx|x|xx|xx|xx| > xxx|xx|x|xx|xx| > xxxx|x|x|xx|xx| > xxxx|x|xx|x|xx| > xxxx|xx|x|x|xx| > xxxxx|x|x|x|xx| > xxxxx|x|x|xx|x| > xxxxx|x|xx|x|x| > xxxxx|xx|x|x|x| > xxxxxx|x|x|x|x|

    最後輸出
    > xxxxxx|x|x|x|x|

    ⋯⋯最左邊 | 的位置很可疑？

    雙倍再加分隔，伴隨只破壞連續字元的 | 右移後，
    最左邊的 "xx|" 會在 雙倍版字串 的 正中央。


    接下來試著拿取看看，觀察順序。

  • c. 對 x 組成的字串 (長度 2~n)，進行 b-1, b-2 動作後，從左邊數來第一個 | 開始，一次拿掉 "xx|"，則可以一直拿下去，直到清空。

    xx| =

    執行下去輸出為空字串。

    觀察一下拿掉 xx 的順序，可以發現是從 中央 到 外側 的順序。




  • d-1. 如果將 x 改為 1 2 3 組成的字串，再進行 b-1，b-2
    e.g. 輸入 123

    > 11|22|33 > 1122|3|3|

  • d-2. 從左邊數來第一個 | 開始，一次一次拿掉 | 與前兩個非分隔符號字元

    11| = 12| = 13| = 21| = 22| = 23| = 31| = 32| = 33| =

    輸出
    > 1122|3|3| 11 3|3| (拿掉 22|) > 113|3| 1 3| (拿掉 13|) > 13| (拿掉 13|) >

    最後輸出空字串。

    可以看到 第一個拿的 22| 在最中間，接下來的 13| 到 13| 順序是由內而外。

    從最左側分隔符號開始，拿前兩個字元，等於從雙倍版字串的中央拿出兩個字元。

透過 d-1 d-2，可以用分隔符號作為錨，最左邊的為啟動點。
用最左分隔符號，可從內而外處理雙倍版字串
進行比對
  • e-1. 針對 d-1 d-2，若我們 d-2 改成：限制只清 連續相同字元 的話
    e.g.: 輸入非回文字串 123

    11| = 22| = 33| =

    輸出
    > 1122|3|3| 11 3|3| (拿掉) > 113|3|
    到這裡會卡住。



  • e-2. 若輸入為回文字串時
    e.g.: 輸入 121

    11| = 22| = 33| =

    輸出
    > 1122|1|1| 11 1|1| (拿掉) > 111|1| 1 1| (拿掉) > 11| >
    則會清空。


    限制在只清除連續相同(非分隔符號)字元的情況下，
    • 輸入為回文字串 = 可清空，
    • 輸入為非回文 = 會中途卡住。




    脫離 1 2 3，開始針對題目的 a b c

  • 仿照 e-1 ，想辦法 雙倍加分隔

    a = AA| b = BB| c = CC|

    但是

    a = AA|
    不能用，因為當答案為 false 時，會發生

    > false > fAAlse
    不可能停在 "false"。

    必須避開 "a=什麼" 這種代換，因為輸出用的終端 "false" 中有 'a'。


    因此我們要針對 'a' 來特別處理。

  • 首先，因為 2<=輸入長度，因此不會有 "a" 單一一個的情況，有 'a' 時必定相連。
    (aa, ab, ac, ba, ca 五種狀況)

    aa = AA|a ab = AA|b ac = AA|c ba = bAA| (注意) ca = cAA| (注意) |a = |AA| b = BB| c = CC|


    (注意)的 ba 和 ca 那兩行其實可以不用寫，因為

    ba = bAA|
    會被
    b = BB| |a = |AA|
    取代

    ca = cAA|
    會被
    c = CC| |a = |AA|
    取代

    總之放在上面等於多寫，放在下面又跑不到。
    只是為了方便解釋才列出來。


  • 雙倍加分隔完成後，再來要向右「有限制的」移動分隔。

    |AA = A|A |AB = A|B |AC = A|C |BA = B|A |BB = B|B |BC = B|C |CA = C|A |CB = C|B |CC = C|C

    重點在判斷 | 右邊有沒有「相鄰」的兩個(A,B,C組成)字元。 相鄰情況共有九種。

    (在判斷「相鄰」上，有減少行數的手段，詳見 *補充1)




    現在題目加工已完成

  • 再來就是從第一個分隔符號開始嘗試 拿其左鄰兩個相同字元了

    AA| = BB| = CC| =
    當輸入為回文時，跑完可以把題目清空。

    但是，要求的答案為 "true"，所以如果調整代換為

    AA| = true BB| = true CC| = true

    不幸的，這樣在第一次成功代換後會卡住，像是
    e.g. 輸入aa

    > AA|AA| > AAA|A| > AtrueA| (卡住)


  • 要怎麼在一次的比對成功後，可以再嘗試進行下一步呢？ 如果加上⋯⋯

    trueA = A trueB = B trueC = C

    回想一下，當「雙倍加分隔，只破壞連續字元的|右移」加工後，右半邊會是像

    ..yy|x|x|x|
    的狀況，

    每次抓到最左邊的 yy| 並處理時，右邊緊鄰接著的東西，只有兩種情況：

    1. 接著一個非分隔符號字元： 表示還有未處理的分隔符號。

    2. 到最右側了： 剛剛用掉的是最後一個分隔符號。

    那麼
    在右邊還有東西時，把剛剛的 "true" 消除以繼續。
    在右邊沒東西時，最後一個 "true" 就會留下來。




    上面例子講的是輸入為回文的理想情況，但如果不是的話，怎麼把卡住時剩下的東西，變成 "false" 呢？


  • 卡住時，代表最左邊的 | ，與其相連的左邊兩個字元不一樣。
    e.g. 輸入為 abc

    > AA|BB|CC| > AABB|C|C| AA C|C| > AAC|C| (卡在AC|)

    「包」住剛剛 拿掉的 BB| 的，是 A C。 若為雙倍化後的回文字串，不會有左右不同的情況。


    雙倍化後的回文字串，由中心到外，一定是一層一層左右對齊的包著。

    「雙倍加分隔，只破壞連續字元的|右移」加工後，相連 ABC 只在 最左那個分隔字元的 左邊，在邊界的這個若無法執行代換/消除，必然會留著。

    其左半邊只有 ABC 而沒有 |；
    而右半邊則沒有相連的 ABC。

    左右都不會有滿足
    AA| = BB| = CC| =
    的情況，必然卡住。


    因為 2<=輸入，所以不會有空字串的情況。 卡住時，一定是最左邊的 | 遇到困難。


    所以會像是
    xxx(有困難卡住)|x|x|x| > xxx(不同|)x|x|x|
    這樣。

    現在要想辦法在不會造成現有程式碼誤動作的情況下，將這卡住的輸出 清空，合併，變成 "false"。




  • 此時如果選擇先處理分隔字元，把它清掉的話

    | =

    就會踩到陷阱。

    因為代換是左到右一個接一個換，也就是說
    現實是
    > AAC|C| AAC C| > AACC|

    而不是妄想的一次清空
    > AAC|C| > AACC (沒這回事)

    原本卡住時就代表沒希望，不用繼續了。但此時會誤觸，跑上面的

    CC| = true

    輸出
    > AAtrue
    變成這鬼東西，然後你就 GG 惹。


  • 那⋯⋯ 還是先清理 A B C 好了

    A = * B = * C = *


    然後會卡住時，右邊一定有還沒用到的分隔符號。
    共幾個不知道，但至少會有最右邊尾巴那一個 |。 所以可用來消除

    *| = |


  • 現在只剩下分隔符號了

    卡住時，沒用掉的 | 數量一定為一個以上。 把它們合併到只剩下一個，就能放心代換為 "false" 了。

    || = | | = false
* 補充 1
在移動分隔符號 | 時，需要判斷有相鄰才移動，

|AA = A|A |AB = A|B |AC = A|C |BA = B|A |BB = B|B |BC = B|C |CA = C|A |CB = C|B |CC = C|C
需要 9 行。


但是如果我們在雙倍化時，改為每個ABC 加上左右外套

aa = (A)(A)|a ab = (A)(A)|b ac = (A)(A)|c |a = |(A)(A)| b = (B)(B)| c = (C)(C)|

則移動分隔符號時的判斷可寫成
|(A)( = (A)|( |(B)( = (B)|( |(C)( = (C)|(
9 行變成 3 行。


由於 A 變成了 (A)，所以之後的比對與清理程式碼也要修正，但邏輯沒有變化只是字串代換。

A 改成 (A，沒有右界 也行，只要有個邊界能用來判斷是否相鄰即可。
左右包起來只是讓閱讀時比較方便。
* 補充 2
想更佳減少行數的讀者，可以試著將用到的字元編碼，像本文章包含

'A', 'B', 'C', '(', '|'

共5種，可以用兩個字元去進行編碼。 在確保不會混淆的前提下，之後在清除階段時可以多省幾行。
程式碼
# ac. (19/24) 右括號方便閱讀 # * 在第六章因為禁止(指令)，所以可以用左右括號。 # 若要在沙盒內測試，括號會被誤認為控制指令像是 (start) 那種的括號，而產生錯誤。 # 沙盒中請將 () 以其他字元替代，像是 < >。 # 雙倍加右分隔 aa = (A)(A)|a ab = (A)(A)|b ac = (A)(A)|c |a = |(A)(A)| b = (B)(B)| c = (C)(C)| # 只破壞連續字元的|右移 |(A)( = (A)|( |(B)( = (B)|( |(C)( = (C)|( # 抓最中心 pair (A)(A)| = true (B)(B)| = true (C)(C)| = true # 嘗試抓下一個 pair true( = ( ## 開始收尾 # 清空 a b c (A) = * (B) = * (C) = * *| = | # 合併分隔字元 || = | | = false
1 Comments
< >
josida 30 Sep, 2023 @ 6:20pm 
很好的教学！