java - 螺旋形地画线

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

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

字符串转换(字符串文本);

例子:

    convert("paypalisthefastersaferwaytosendmoney") 
should return "paypalferwaiamonyssdyettrnesohetsafe"

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

Answer 1

我认为，书面上的问题的解释如下:

You are given a string and want to write that string as a spiral into a square grid. Write a function that finds the smallest square that can hold the string, writes the string into the grid by spiraling its characters around the grid clockwise, and finally concatenates the rows together.

例如，字符串“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”。

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

至于如何真正填充网格，有一种非常好的方法。直觉如下。当您从n x n网格开始时，您唯一的边界就是网格的壁。每次您跨过网格放下字母并撞到墙时，您都只是从矩阵上刮掉了一行或一列。因此，您的算法可以通过跟踪第一和最后一个合法列以及第一和最后一个合法行来工作。然后，您从左到右跨过第一行书写字符。完成后，您将增加第一合法行，因为您再也无法放置任何内容了。然后，向下走到右侧，直到触底。完成后，您还可以将最后一列也排除在考虑范围之外。例如，回顾一下“螺旋式”示例，我们从一个空的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度转弯:将 vector 向左旋转90度，然后将其乘以rotation matrix

|  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×N网格中的(行，列)对，我们可以通过查看位置行* N + col将该坐标转换为线性化数组中的相应位置。直观地讲，这表示您沿y方向执行的每一步等效于跳过一行中的所有N个元素，并且每个水平步仅在线性化表示中水平移动一个步。

希望这可以帮助!