Я полагаю, что вопрос, как написано, должен толковаться следующим образом:
Вам дана строка, и вы хотите записать эту строку в виде спирали в квадратную сетку. Напишите функцию, которая находит наименьший квадрат, который может содержать строку, записывает строку в сетку, закручивая ее символы вокруг сетки по часовой стрелке, и, наконец, объединяет строки вместе.
Например, строка «По спирали» будет выглядеть так:
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, вашими единственными границами являются стены сетки. Каждый раз, когда вы идете по сетке, сбрасывая буквы и ударяетесь о стену, вы просто сбриваете строку или столбец из матрицы. Следовательно, ваш алгоритм может работать, отслеживая первый и последний допустимый столбец, а также первый и последний допустимый ряд. Затем вы идете по верхнему ряду слева направо написания символов. Когда вы закончите, вы увеличиваете первый допустимый ряд, так как вы больше ничего не можете поместить туда. Затем идите вниз по правой стороне, пока не достигнете дна. Когда вы закончите, вы также заблокируете последний столбец. Например, чтобы оглянуться назад на наш пример «По спирали», мы начнем с пустой сетки 3х3:
. . .
. . .
. . .
После того, как мы напишем первые три символа вверху, у нас останется следующее:
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 градусов влево, вы умножаете его на матрицу вращения
| 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
Наконец, после того как вы записали строку в спираль, вы можете преобразовать этот спиральный текст обратно в строку, проходя по строкам по одному и объединяя все найденные символы.
EDIT : Как указывает @Voo, вы можете упростить последний шаг этого алгоритма, вообще не создавая многомерный массив, а вместо этого кодируя многомерный массив как одномерный массив. Это распространенный (и умный!) Трюк. Предположим, например, что у нас есть сетка, подобная этой:
0 1 2
3 4 5
6 7 8
Тогда мы можем представить это с помощью одномерного массива как
0 1 2 3 4 5 6 7 8
Идея состоит в том, что, учитывая пару (row, col) в сетке N x N, мы можем преобразовать эту координату в соответствующее местоположение в линеаризованном массиве, посмотрев на строку позиции * N + col. Интуитивно это говорит о том, что каждый шаг в направлении y, который вы делаете, эквивалентен пропуску всех N элементов одной строки, и каждый горизонтальный шаг просто перемещает один шаг по горизонтали в линеаризованном представлении.
Надеюсь, это поможет!