用螺旋写一个字符串
我最近参加了一家公司赞助的编码竞赛，有一个我不理解的问题，问题是什么。
这是一个问题：
字符串“paypal是更快，更安全的汇款方式”是从左上角开始以正方形螺旋形图案写在正方形内:(您可能希望以固定字体显示此图案以获得更好的易读性）。
PAYPAL FERWAI AMONYS SDYETT RNESOH ETSAFE 然后逐行阅读：PAYPALFERWAIAMONYSSDYETTRNESOHETSAFE
编写将采用字符串的代码，计算将包含它的最小平方并返回转换后的字符串：
字符串转换（String text）;
例：
convert("paypalisthefastersaferwaytosendmoney") should return "paypalferwaiamonyssdyettrnesohetsafe"
你了解我们如何解决这个问题吗？
我认为，正如所写的那样，问题应解释如下：
您将获得一个字符串，并希望将该字符串作为螺旋线写入方形网格。 编写一个函数，找到可以容纳字符串的最小正方形，通过顺时针在网格周围螺旋字符将字符串写入网格，最后将这些行连接在一起。
例如，字符串“In a spiral”将如下所示：
INA In a spiral -> ALS -> INAALSRIP RIP
要查看网格的来源，请注意，如果您这样阅读：
I -> N -> A | v A -> LS ^ | | v R <- I <- P
你得到了初始文本，如果你将行“INA”，“ALS”和“RIP”粘合成一个字符串，你就会得到“INAALSRIP”。
让我们分别考虑每个问题。 首先，要查看可以容纳文本的矩形的最小尺寸，您实际上是在寻找最小的完美正方形，至少与文本的长度一样大。 要找到这个，你可以取字符串长度的平方根并将其四舍五入到最接近的整数。 这为您提供了您想要的尺寸。 但是，在您可以执行此操作之前，您需要从字符串中删除所有标点符号和空格字符（也可能是数字，具体取决于应用程序）。 您可以通过遍历字符串并将确实按字母顺序复制的字符复制到新缓冲区中来完成此操作。 在下文中，我假设你已经做到了这一点。
至于如何实际填充网格，有一个非常好的方法来做到这一点。 直觉如下。 当您在nxn网格中开始时，您的唯一边界是网格的墙。 每当你穿过网格划过字母并撞墙时，你只是从矩阵中划掉一行或一列。 因此，您的算法可以通过跟踪第一个和最后一个合法列以及第一个和最后一个合法行来工作。 然后，您从左到右穿过顶行写字符。 当你完成后，你就增加了第一个合法的行，因为你不能再放任何东西了。 然后，沿着右侧走，直到你到达底部。 完成后，您将阻止考虑最后一列。 例如，回顾一下我们的“螺旋式”示例，我们从一个空的3x3网格开始：
. . . . . . . . .
在我们写完顶部的前三个字符后，我们留下了这个：
INA . . . . . .
现在，我们需要将字符串的其余部分写入空白区域，从右上方开始向下移动。 因为我们不能写回到第一行，所以考虑这个问题的一种方法是考虑解决在较小的空间中以螺旋forms写出其余字符的问题。
. . . . . .
从左上角开始向下移动。
要真正实现这个算法，我们需要在每个点跟踪一些事情。 首先，我们需要在更新它们时存储世界的边界。 我们还需要存储当前的写入位置，以及我们面临的方向。 在伪代码中，这表示如下：
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个元素，而每个水平步骤只是在线性化表示中水平移动一步。
希望这可以帮助！
我在Python中编写了一个实现，我认为它实现了一种类似于工作的方法。 虽然你标记了你的问题Java，但有时我认为原型和学习问题是明智的，特别是在高级动态语言中的“面试问题”。 语言本身就像运行的伪代码一样，这有助于您了解问题的形状或问题的形状。
这个人提出问题的方式就是这里的线索：
- 有一个漂亮的盒子，像字母的形状。 一个好的开始就是问自己，我如何编写一个包含一盒字母的代码。
- 什么数据结构（带有x +（y * c）查找或2d数组的数组）将存储字母框。
- 我如何将它们放入，如何将它们取出？
从你将它分解为更小的部分，你应该能够理解这个问题，然后开始制定答案。
它可能在很少的代码行中完成，但我觉得这样做是尽可能线性的。 这是一个不太好的python答案：
from math import * import pprint directions = [ (0,1),(1,0),(0,-1),(-1,0) ] def store_spiral(array,s,l): direction = 0 dx = directions[direction][0] dy = directions[direction][1] x=0 y=0 for c in s: array[x][y] = c x = x +dx y = y +dy if (x >= l) or (y >= l) or (x<0) or (y<0): x=x-dx y=y-dy direction = (direction + 1) % 4 dx = directions[direction][0] dy = directions[direction][1] x=x+dx y=y+dy elif (array[x][y]!=''): x=x-dx y=y-dy direction = (direction + 1) % 4 dx = directions[direction][0] dy = directions[direction][1] x=x+dx y=y+dy def convert(s): l = len(s) sl = int(ceil(sqrt(l))) # make empty 2d array of [ ['','', ... ], .... ] ar2 = [['' for i in range(sl)] for j in range(sl)] store_spiral(ar2,s,sl) x='' for ar in ar2: for l in ar: x=x+l return x a = convert("paypalisthefastersaferwaytosendmoney") print a
这里有一个想法如何制作一个更酷的版本，但它需要在这里产生一系列称为“限制”的值，这就是“转弯之前的行走长度”。
from math import * import pprint # directions = East,South,West,North directions = [ (0,1),(1,0),(0,-1),(-1,0) ] x=0 y=-1 def store_spiral(array,s,l): global x global y direction = 0 dx = directions[direction][0] dy = directions[direction][1] d=0 n=0 limits=[5,4,4,3,3,2,2,1,1,1,1] limit=limits[n] for c in s: d=d+1 x=x+dx y=y+dy array[y+(x*l)]=c if d>limit and (limit>0): direction = (direction + 1) % 4 dx = directions[direction][0] dy = directions[direction][1] n=n+1 if n>=len(limits): break limit=limits[n] d=0 def convert(s): l = len(s) sl = int(ceil(sqrt(l))) # make empty 2d array of [ ['','', ... ], .... ] ar = ['*' for i in range(l)] #try: store_spiral(ar,s,sl) #except: # pass x='' n=0 for l in ar: x=x+l print l, n=n+1 if n==sl: n=0 print return x a = convert("paypalisthefastersaferwaytosendmoney") print print 'result: ',a
方形边的大小是方形的平方根，其中方形是第一位的长度。
回答：
- 将长度作为整数
- 找到长度的平方根作为浮点数，即根
- 检查root的小数部分是否为非零
- 如果root的小数部分中存在非零，则将1添加到root的整数部分，否则添加0
- 结果是整数
- 这个数字是一个答案，你的广场的每一边有多大
- 实例化一个空白正方形，大小与计算的一样
- 通过从左上角开始“螺旋式”访问每个插槽填充广场
- 断言在完成后，源字符串中没有任何内容
- 断言方形的剩余未填充部分小于（2x边尺寸 – 1）
- 以从左到右，从上到下的顺序重新访问正方形以重建输出
- 断言输出长度等于输入长度
- 完成
我认为：
你有
ABCHIDGFE
您将其转换为方形（如果可能）
ABC HID GFE
然后顺时针方向做弦
ABCDEFGHI
并返回此字符串
我不知道该做什么，如果它不可能正确的话。
这就是我对这个问题的理解。
让我们说我们有一个字符串“hello world这是我编写的第一个脚本，今天你好吗”
该字符串有64个字符。
现在，如果你查看你给的字符串，它有36个字符，其中平方根是6，因此每边有6个字母。
所以上面的字符串有64个字符，其平方根为：8
这意味着每边最小正方形需要8个字母。
这个答案涉及“计算最小尺寸平方”要求背后的过程。
//在c ++中
string convert（const string＆s）{int len = s.size（）;
//base case if (len == 0) return string(""); // minimum square calculation int i = 1; while (i*i < len) ++i; //cout << "i=" << i << endl; //matrix initialization vector > matrix; matrix.resize(i); for (int j = 0; j < i; ++j) matrix[j].resize(i); for (int j = 0; j < i; ++j) for (int k = 0; k < i; ++k) matrix[j][k] = ' '; //logic int r = 0, c = 0; bool right = true, down = false, left = false, up = false; int curr_len = 0; int side = i - 1; while (curr_len < len) { if (right) { for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j) { matrix[r][c] = s[curr_len]; //cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n"; ++c; ++curr_len; } right = false; down = true; } if (down) { for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j) { matrix[r][c] = s[curr_len]; //cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n"; ++r; ++curr_len; } down = false; left = true; } if (left) { for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j) { matrix[r][c] = s[curr_len]; //cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n"; --c; ++curr_len; } left = false; up = true; } if (up) { for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j) { matrix[r][c] = s[curr_len]; //cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n"; --r; ++curr_len; } up = false; right = true; side = side - 2; ++r; ++c; } } stringstream ss; for (int j = 0; j < i; ++j) { for (int k = 0; k < i; ++k) { ss << matrix[j][k]; } } return ss.str();
}
人们在上面的解决方案中使用了大量嵌套循环和if语句。 就个人而言，我觉得如何在以下方面做到这一点更清洁：
direction current input position current row current column num rows to fill num cols to fill Fill right row 0 from column 0 to column 5. Fill down column 5 from row 1 to row 4. Fill left row 5 from column 4 to column 0 Fill up column 0 from row 4 to row 1 etc...
这是一个经典的递归解决方案，如果你真的想要，甚至可以修改为fork-join池。 这个特殊的解决方案实际上根据输入调整输出网格大小，所以如果你从输入中修剪出足够的字符，你可能会获得5行×6个字符串（尽管你总是可以将行修剪掉并只生成一个正方形很多空白）。
public static void placeright(char output[][], char input[], int position, int row, int col, int numrows, int numcols) { for (int i=0;i= chars.length) { rows--; } char output[][] = new char[rows][cols]; placeright(output, chars, 0, 0, 0, rows, cols); for (int i=0;i
试试这个
package com.misc; public class SprintSpiral { public static void main(String[] args){ int xStart = 0; int xEnd = 3; int yStart = 0; int yEnd = 3; int[][] arr = new int[4][4]; arr[0][0]=1; arr[1][0]=2; arr[2][0]=3; arr[3][0]=4; arr[0][1]=5; arr[1][1]=6; arr[2][1]=7; arr[3][1]=8; arr[0][2]=9; arr[1][2]=10; arr[2][2]=11; arr[3][2]=14; arr[0][3]=15; arr[1][3]=16; arr[2][3]=17; arr[3][3]=18; for (int i = 0; i < 16; i++) { for (int j = xStart; j <= xEnd; j++) { System.out.println(arr[j][yStart]); } ++yStart; for (int j = yStart; j <= yEnd; j++) { System.out.println(arr[xEnd][j]); } xEnd--; for (int j = xEnd; j >= xStart; j--) { System.out.println(arr[j][yEnd]); } yEnd--; for (int j = yEnd; j >= yStart; j--) { System.out.println(arr[xStart][j]); } xStart++; } } }
首先用点字符填充6×6矩阵。然后将方向设置为1.然后每次方向中的下一个字符不是点字符时改变方向。
public class Spiral { static String phrase="paypalisthefastersaferwaytosendmoney"; static int deltax,deltay,direction; public static void setDelta(){ if(direction==1){ deltax=1; deltay=0; }else if(direction==2){ deltax=0; deltay=1; }else if(direction==3){ deltax=-1; deltay=0; }else if(direction==4){ deltax=0; deltay=-1; } } public static void main(String[] args) { int index=0,x,y,N=6; char[][] MATRIX=new char[N][N]; for(y=0;y=0 && y=0){ MATRIX[y][x]=phrase.charAt(index); System.out.print(MATRIX[y][x]); index++; if(direction==1 && MATRIX[y][x+1]!='.' || x+1==N-1) break; if(direction==2 && MATRIX[y+1][x]!='.' && y=0) break; x+=deltax; y+=deltay; } if(direction==4) direction=1; else direction++; setDelta(); x+=deltax; y+=deltay; } } }
计算最小平方很容易。 你可以检查输入字符串中的字符数和最小方形大小n * n。
1*1= 1 2*2 = 4 3*3 = 9
所以你可以通过输入公式轻松找到n
n*n >= length(input string).
看起来像PAYPALISTHEFASTERSAFERWAYTOSENDMONEY是输入和
PAYPAL FERWAI AMONYS SDYETT RNESOH ETSAFE
是输出给我..
即使问题没有明确说明最初提供算法。 这是递归解决方案的伪代码：
convert(input): spiral(out[][],input,0,0,sqrt(input.len)) return out.toString() spiral(out[][],input,ix,iy,size) if size>0 //calculate the frame coords with starting indices ix,iy & size of the frame place first 4*(size-1) chars on a frame on the ´out´ matrix //recursive call to create inner frame spiral(out,input.remainingString(),ix+1,iy+1,size-2) else return
和java中的实现：
public class PayPal { private enum Dir { RIGHT, DOWN, LEFT, UP; } public String convert(String input) { double dRoot = Math.sqrt(input.length()); int root; if (Double.compare(dRoot, (int) dRoot) == 0) { root = (int) dRoot; } else { root = (int) dRoot + 1; } char[][] out = new char[root][root]; spiral(out, 0, 0, root, input); StringBuilder sb = new StringBuilder(); for (char[] line : out) { sb.append(line); } return sb.toString(); } private void spiral(char[][] out, int i, int j, int size, String input) { Dir direction = Dir.RIGHT; if (size > 0) { if (size == 1) { out[i][j] = input.charAt(0); } else { for (int k = 0; k < 4 * (size - 1); k++) { int di = (k != 0 && k % (size - 1) == 0 ? size - 1 : k % (size - 1)); switch (direction) { case RIGHT: out[i][j + di] = input.charAt(k); break; case DOWN: out[i + di][j + size - 1] = input.charAt(k); break; case LEFT: out[i + size - 1][j + size - 1 - di] = input.charAt(k); break; case UP: out[i + size - 1 - di][j] = input.charAt(k); break; } if (k != 0 && (k % (size - 1) == 0)) //Change direction { direction = Dir.values()[direction.ordinal() + 1]; } } } spiral(out, i + 1, j + 1, size - 2, input.substring(4 * (size - 1))); } else { return; } } }