以螺旋书写的字符串 [英] Writing a string in a spiral

问题描述

我最近参加了编码赛区由公司赞助，并有我没有理解，至于究竟是什么苦恼一个问题。

I had recently participated in coding competion sponsored by an company and there was this one question which I did not understood, as to what was it asking.

下面的问题：

字符串PayPal是更快，更安全的方式来发钱是写在一个 从左上角开始的正方形内顺时针螺旋形图案： （您可能想显示这个模式在固定的字体为更好的可读性）。

The string "paypal is the faster, safer way to send money" is written in a clockwise spiral pattern inside a square starting from the upper left corner: (you may want to display this pattern in a fixed font for better legibility).

   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

Then read line after line: PAYPALFERWAIAMONYSSDYETTRNESOHETSAFE

写code，将采取一个字符串，计算最小平方即会 包含它并返回转换后的字符串：

Write the code that will take a string, calculate the minimum square that will contain it and return the converted string:

字符串转换（字符串文本）;

String convert(String text);

例如：

    convert("paypalisthefastersaferwaytosendmoney") 
should return "paypalferwaiamonyssdyettrnesohetsafe"

你明白，我们如何能解决这个问题？

Do you understand as to how we can approach this problem?

推荐答案

我相信这个问题，因为写的，就是要PTED跨$ P $如下：

I believe that the question, as written, is meant to be interpreted as follows:

您将得到一个字符串，并希望写字符串作为螺旋成方形网格。编写一个函数，找到可以容纳字符串最小的广场，写串入电网通过电网螺旋顺时针方向绕其特征，最后并置的排在一起。

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.

作为一个例子，字符串以螺旋是这样的：

As an example, the string "In a spiral" would look like this:

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

要看到网格来源于请注意，如果你读它是这样的：

To see where the grid comes from, note that if you read it like this:

     I -> N -> A

               |
               v

     A -> L    S

     ^         |
     |         v

     R <- I <- P

您找回最初的文本，如果胶水行INA，ALS和RIP成一个字符串你回来INAALSRIP。

You get back the initial text, and if you glue the rows "INA", "ALS," and "RIP" into a single string you get back "INAALSRIP."

让我们分别考虑每一个问题。首先，要看到，能容纳文本的矩形的最小尺寸，你基本上寻找最小的完全平方数至少一样大的文本长度。要了解这一点，你可以把你的字符串的长度的平方根和圆形它到最接近的整数。这就给了你你想要的尺寸。然而，在你能做到这一点，你需要去掉所有的标点和空格字符的字符串（也许是人数为好，根据不同的应用程序）。您可以通过走在字符串和复制了这确实是字母到一个新的缓冲区中的字符做到这一点。在下文中，我会假设你已经做到了这一点。

Let's consider each problem separately. First, to see the smallest size of a rectangle that can hold the text, you're essentially looking for the smallest perfect square at least as large as the length of your text. To find this, you could take the square root of the length of your string and round it up to the nearest integer. That gives you the dimension you'd like. However, before you can do that, you need to strip out all of the punctuation and space characters from the string (and perhaps the numbers as well, depending on the application). You could do this by walking across the string and copying over the characters that are indeed alphabetic into a new buffer. In what follows, I'll assume that you've done this.

至于如何真正填补了网格，有一个真正伟大的方式来做到这一点。直觉如下。当您在N×N个网格开始，你唯一的边界是网格的墙壁。你行军穿越电网下探字母撞墙了每一次，你刚刚剃掉了一排或矩阵列。因此，你的算法可以通过跟踪第一和最后法律列和第一个和最后法律行的工作。你在顶部行再步行从左至右书写字符。当你做，你再增加第一个合法的行，因为你不能把任何东西有什么比较。然后，走在右边，直到你击中的底部。一旦你做，你会再挡掉来自考虑的最后一栏为好。例如，回头看看我们的在一个螺旋式的例子，我们有一个空的3×3格开始：

As for how to actually fill in the grid, there's a really great way to do this. The intuition is as follows. When you start off in an n x n grid, your only boundaries are the walls of the grid. Every time you march across the grid dropping letters and hit a wall, you've just shaved off a row or a column from the matrix. Consequently, your algorithm could work by keeping track of the first and last legal column and the first and last legal row. You then walk across the top row from left to right writing characters. When you're done, you then increment the first legal row, since you can't put anything there any more. Then, walk down the right side until you hit the bottom. Once you're done, you would then block off the last column from consideration as well. For example, to look back at our "In a spiral" example, we start off with an empty 3x3 grid:

. . .
. . .
. . .

在我们写在顶部的前三个字符，我们就离开了这一点：

After we write the first three characters across the top, we're left with this:

I N A
. . .
. . .

现在，我们需要将字符串的其余部分写入到空白区域，从上右方启动和向下移动。因为我们不能永远写回顶行，思考这个的方法之一是考虑解决在较小的空间写在一个螺旋的其余字符的问题

Now, we need to write the rest of the string into the blank space, starting from the upper-right square and moving down. Because we can't ever write back into the top row, one way of thinking about this is to think about solving the problem of writing the rest of the characters in a spiral in the smaller space

. . .
. . .

从左上角开始并向下移动。

Starting from the upper-left corner and moving downward.

要真正实现这是一个算法，我们需要跟踪的几件事情在每个点。首先，我们需要存储世界的界限，因为我们正在更新他们。我们还需要存储我们当前的写入位置，以及什么方向我们正在面对的问题。在伪code，这是psented重新$ P $如下：

To actually realize this as an algorithm, we need to keep track of a few things at each point. First, we need to store the bounds of the world as we're updating them. We also need to store our current write location, along with what direction we're facing. In pseudocode, this is represented as follows:

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度到左边，你的的旋转矩阵

You can implement the ninety-degree turn using a trick from linear algebra: to rotate a vector 90 degrees to the left, you multiply it by the rotation matrix

|  0   1 |
| -1   0 |

所以，新的DY和DX以

So your new dy and dx are given by

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

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

So you can turn left by computing

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

另外，如果你知道一个事实，即该字符的数值为零永远不会出现在字符串中，你可以使用Java的初始化所有的数组到处举办零的事实。然后，你可以把0作为一个哨兵，意思是可以有把握地继续前进。该版本的（伪）的code是这样的：

Alternatively, if you know for a fact that the character with numeric value zero never appears in the string, you can use the fact that Java initializes all arrays to hold zeros everywhere. You can then treat 0 as a sentinel meaning "it's safe to keep moving forward." That version of the (pseudo)code would look like this:

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

最后，当你写串入螺旋，可以通过跨行人走动的时间和串联起来所有你找到的字符转换是螺旋形的文字回字符串。

Finally, once you've written the string into the spiral, you can convert that spiraled text back into a string by walking across the rows one at a time and concatenating together all of the characters that you find.

修改：作为@Voo所指出的，可以简化这个算法并不实际创建一个多维数组的一切，而不是编码多维数组作为一维数组中的最后一步。这是一种常见的（和聪明！）的技巧。举个例子，我们有一个这样的网格：

EDIT: As @Voo points out, you can simplify the last step of this algorithm by not actually creating a multidimensional array at all and instead encoding the multidimensional array as a single-dimensional array. This is a common (and clever!) trick. Suppose, for example, that we have a grid like this:

 0  1  2
 3  4  5
 6  7  8

然后我们就可以重新present这使用一维数组

Then we can represent this using a one-dimensional array as

 0  1  2  3  4  5  6  7  8

的想法是，给定一个（行，列）对在N×N个格子，我们可以转换坐标的线性阵列中的相应位置通过观察位置行* N +栏。直观地，这表示，在y方向的每一步您采取相当于跳过一个行的所有N个元件，并且每个水平步骤只是移动一步水平地线性化重presentation

The idea is that given an (row, col) pair in an N x N grid, we can convert that coordinate to a corresponding location in the linearized array by looking at position row * N + col. Intuitively, this says that every step in the y direction that you take is equivalent to skipping all N elements of one row, and each horizontal step just moves one step horizontally in the linearized representation.

希望这有助于！

这篇关于以螺旋书写的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！