用螺旋写一个字符串

Question

我最近参加了一家公司赞助的编码竞赛,有一个我不理解的问题,问题是什么.

这是一个问题:

字符串"paypal是更快,更安全的汇款方式"是从左上角开始以方形螺旋形图案写在正方形内:(您可能希望以固定字体显示此图案以获得更好的易读性).

   P A Y P A L
   F E R W A I
   A M O N Y S
   S D Y E T T
   R N E S O H
   E T S A F E

然后逐行阅读:PAYPALFERWAIAMONYSSDYETTRNESOHETSAFE

编写将采用字符串的代码,计算将包含它的最小平方并返回转换后的字符串:

String convert(String text);

例:

    convert("paypalisthefastersaferwaytosendmoney") 
should return "paypalferwaiamonyssdyettrnesohetsafe"

你了解我们如何解决这个问题吗？

Answer 1

我认为,正如所写的那样,问题应解释如下:

您将获得一个字符串,并希望将该字符串作为螺旋线写入方形网格.编写一个函数,找到可以容纳字符串的最小正方形,通过顺时针在网格周围螺旋字符将字符串写入网格,最后将这些行连接在一起.

例如,字符串"In a spiral"看起来像这样:

                I N A
In a spiral ->  A L S -> INAALSRIP
                R I P

要查看网格的来源,请注意,如果您这样阅读:

     I -> N -> A

               |
               v

     A -> L    S

     ^         |
     |         v

     R <- I <- P

您返回初始文本,如果将行"INA","ALS"和"RIP"粘贴到单个字符串中,则会返回"INAALSRIP".

让我们分别考虑每个问题.首先,要查看可以容纳文本的矩形的最小尺寸,您实际上是在寻找最小的完美正方形,至少与文本的长度一样大.要找到这个,你可以取字符串长度的平方根并将其四舍五入到最接近的整数.这为您提供了您想要的尺寸.但是,在执行此操作之前,您需要从字符串中删除所有标点符号和空格字符(也可能是数字,具体取决于应用程序).您可以通过遍历字符串并将确实按字母顺序复制的字符复制到新缓冲区中来完成此操作.在下文中,我假设你已经完成了这个.

至于如何实际填充网格,有一个非常好的方法来做到这一点.直觉如下.当您在nxn网格中开始时,您的唯一边界是网格的墙.每当你穿过网格划过字母并撞墙时,你只是从矩阵中划掉一行或一列.因此,您的算法可以通过跟踪第一个和最后一个合法列以及第一个和最后一个合法行来工作.然后,您从左到右穿过顶行写字符.完成后,然后递增第一个合法行,因为你不能再放任何东西了.然后,沿着右侧走,直到你到达底部.一旦完成,您就会阻止考虑最后一列.例如,回顾一下我们的"螺旋式"示例,我们从一个空的3x3网格开始:

. . .
. . .
. . .

在我们写完顶部的前三个字符后,我们留下了这个:

I N A
. . .
. . .

现在,我们需要将字符串的其余部分写入空白区域,从右上方开始向下移动.因为我们不能写回到第一行,所以考虑这个的一种方法是考虑解决在较小的空间中以螺旋形式写出其余字符的问题.

. . .
. . .

从左上角开始向下移动.

要真正实现这个算法,我们需要在每个点跟踪一些事情.首先,我们需要在更新它们时存储世界的边界.我们还需要存储当前的写入位置,以及我们面临的方向.在伪代码中,这表示如下:

firstRow = 0, lastRow = N - 1 // Bounds of the grid
firstCol = 0, lastCol = N - 1

dRow = 0  // Amount to move in the Y direction
dCol = 1  // Amount to move in the X direction

row = 0   // Current position
col = 0

for each character ch in the string:
    Write character ch to position (row, col).

    // See if we're blocked and need to turn.
    If (row + dRow, col + dCol) is not contained in the rectangle [firstRow, lastRow] x [firstCol, lastCol]:
        // Based on which way we are currently facing, adjust the bounds of the world.
        If moving left,  increment firstRow
        If moving down,  decrement lastCol
        If moving right, decrement lastRow
        If moving up,    increment firstCol

        Rotate 90 degrees

    // Finally, move forward a step.
    row += dRow
    col += dCol

你可以使用线性代数技巧实现90度转弯:将向量旋转90度向左旋转,将其乘以旋转矩阵

|  0   1 |
| -1   0 |

所以你的新dy和dx是由

|dCol'| = |  0   1 | dCol = |-dRow|
|dRow'|   | -1   0 | dRow   | dCol|

所以你可以通过计算向左转

temp = dCol;
dCol = -dRow;
dRow = temp;

或者,如果您知道数字值为零的字符永远不会出现在字符串中,则可以使用Java初始化所有数组以在任何地方保存零的事实.然后你可以将0视为哨兵,意思是"继续前进是安全的".那个版本的(伪)代码看起来像这样:

dRow = 0  // Amount to move in the X direction
dCol = 1  // Amount to move in the Y direction

row = 0   // Current position
col = 0

for each character ch in the string:
    Write character ch to position (row, col).
    If (row + dRow, col + dCol) is not contained in the rectangle [0, 0] x [n-1, n-1]
             -or-
       The character at [row + dRow, col + dCol] is not zero:
        Rotate 90 degrees

   // Move forward a step
   row += dRow
   col += dCol

最后,一旦你将字符串写入螺旋,你就可以通过一次一行地遍历行并将你找到的所有字符连接在一起,将该螺旋文本转换回字符串.

编辑:正如@Voo指出的那样,你可以简化这个算法的最后一步,实际上根本不创建一个多维数组,而是将多维数组编码为一维数组.这是一个常见的(而且很聪明!)技巧.例如,假设我们有一个这样的网格:

 0  1  2
 3  4  5
 6  7  8

然后我们可以使用一维数组表示这个

 0  1  2  3  4  5  6  7  8

我们的想法是,在N x N网格中给定(row,col)对,我们可以通过查看位置行*N + col将该坐标转换为线性化数组中的相应位置.直观地说,这表示你所采取的y方向上的每一步都相当于跳过一行中的所有N个元素,而每个水平步骤只是在线性化表示中水平移动一步.

希望这可以帮助!