什麼是更好的曲折印刷更好的解決方案？

Question

考慮對字符串進行以下轉換。給定一個行和一個字符串作爲輸入，將該字符串在行中來回寫入。例如，給定輸入

請轉換我定製的曲折打印格式

有三排，我們會寫這樣一個曲折的字符串：

P s n t o s i z a i n r 
l a e o v r m t a u t m z d i z g r n i g o m t 
e c e e c o e g p t f a 

（請不要編輯這個打印輸出，這是必需的輸出，它不是一個真正的曲折，它是一個定製的鋸齒形的 ）

最後，我們串連每行的比賽合力得到結果字符串

Psntosizainrlaeovrmtautmzdizgrnigomteceecoegptfa 

我對這個問題，我已經在這裏僞代碼寫出來的算法的草圖：

it is asking about the relationship between {index} and {output row and col} 
Def: 
    down = false; 
    up = false; 
    r=0; 
    c=0; 
    char[][] output; 
there are three cases here: 
case 1: 
    index % 4 == 0, it is the beginning of a down printing 
    r = 0; 
    output[r][c] = in.charAt(index); 
    c++; 
    down = true; up = false; 

case 2: 
    index%4 != 0 && down = true; 
    r = index % 4; 
    output[r][c] = in.charAt(index); 
    if(r == 2){ up = true; down = false; c++;} // when come to the last row of a down formatting 

case 3: 
    index%4 != 0 && up == true; 
    r = 4- index%4; 
    output[r][c] = in.charAt(index); 
    c++; 

對於一個通用的解決方案，我可以取代4作爲nRows+1;

雖然我認爲這可行，但我並不太滿意。有沒有人有更清晰或更快的算法來解決這個問題？

Answer 1

一個可能使這個問題更容易解決的問題是：假設您的行數爲3，並且希望在分佈字符的行之間保持鋸齒形。然後，如果您循環使用四個字符，則在重複此模式之前，您應將它們添加到行1,2,3和2。行數爲5時，在重複此模式之前，請訪問第1,2,3,4,5,4,3和2行。更一般地，如果你的行數爲k，那麼分配字符的行集合將遵循模式1,2,3，...，k，k-1，k-2，...，2 ，其長度爲2k - 2。

鑑於此觀察，您可以通過預先計算包含該週期的表以及該週期的長度，使代碼更清晰。一旦你有了這張桌子，你就可以在角色間循環，跟蹤你所在的角色。當你在第n個字符上時，你可以在位置n mod k處索引到表中，然後將該字符分配到該行中。

僞代碼（使用基於一個指標）：

rowTable = new array of ints length 2k - 2 
for i = 1 up to k: 
    rowTable[i] = i 
for i = 2 up to k - 1: 
    rowTable[(2k - 1) - (i - 2)] = i 

resultRows = new array of strings of length k 

for i = 1 up to the length of your string: 
    Append the current character to resultRows[rowTable[i mod k]] 

Concatenate all the entries of resultRows 

這種方法不要求你在所有的不同情況硬編碼到一個switch語句，這意味着它能夠處理任意而不僅僅是k = 3。而且，它非常快;運行時間是O（n + k），其中n是字符串的長度，k是行數。

希望這會有所幫助！

Answer 2

您怎麼看這一個。原始的字符串是s 從0 -copy字符到rows-1在字符串說str

str[rows]=some impossible to occur in d original string character , like -1 

-copy從s[r]反向字符到s[2r-3]成str

str[2r-2]=some impossible to occur in d original string character, -1 

重複直到長度被覆蓋，這兩個步驟，一個接一個。

在字符串str中，佔用行位置上的每個字符，即str[0],str[rows],str[2rows] ...跳過str[rows]是-1。 重複此步驟直到str的長度。