java - 对于改变的锯齿形打印，什么是更好的解决方案？

Question

考虑以下对字符串的转换。给定多行和一个字符串作为输入，将该字符串以之字形在各行之间来回书写。例如给定输入

Please convert me to a customized zigzag printing format

如果是三行，我们会像这样将字符串写成之字形:

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 处建立索引，然后将该字符分配到该行。

在伪代码中(使用基于 1 的索引):

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 而不仅仅是 k = 3。此外，它是非常快;运行时间为 O(n + k)，其中 n 是字符串的长度，k 是行数。

希望这对您有所帮助!