我最近参加了一家公司赞助的编码竞赛,有一个我不明白的问题,问的是什么。
这是问题:
字符串“ 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"
您了解我们如何解决这个问题吗?
我认为,书面上的问题应解释如下:
您将得到一个字符串,并希望将该字符串作为螺旋形写入正方形网格中。编写一个函数,该函数查找可以容纳字符串的最小正方形,通过沿顺时针方向将其字符沿网格螺旋缠绕将其写入网格,最后将各行连接在一起。
例如,字符串“ 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网格开始时,唯一的边界就是网格的墙。每次您跨过网格放下字母并撞到墙时,您都只是从矩阵中刮掉了一行或一列。因此,您的算法可以通过跟踪第一个和最后一个合法列以及第一个和最后一个合法行来工作。然后,您从左到右跨过第一行书写字符。完成后,您将增加第一合法行,因为您再也无法放置任何内容了。然后,向下走到右侧,直到触底。完成后,您也将不必考虑最后一栏。例如,回顾一下“螺旋式”
. . . . . . . . .
在顶部写下前三个字符后,剩下的就是:
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
然后我们可以使用一维数组将其表示为
这个想法是,给定N x N网格中的(行,列)对,我们可以通过查看位置行* N + col将该坐标转换为线性化数组中的相应位置。直观地讲,这表示您沿y方向执行的每一步等效于跳过一行中的所有N个元素,并且每个水平步仅在线性化表示中水平移动一个步。
希望这可以帮助!