Что является лучшим решением для измененной зигзагообразной печати? - PullRequest
Новая
       0

Что является лучшим решением для измененной зигзагообразной печати?

2 голосов
/ 30 августа 2011

Рассмотрим следующее преобразование для строки. Задавая в качестве входных данных количество строк и строку, напишите эту строку зигзагообразно вперед и назад по строкам. Например, заданный ввод

Пожалуйста, преобразуйте меня в индивидуальный зигзагообразный формат печати

с тремя строками, мы написали бы строку зигзагом так: 

P   s   n   t   o   s   i   z   a   i   n   r
 l a e o v r m t a u t m z d i z g r n i g o m t
 e   c   e   e   c   o   e   g   p   t   f   a

(пожалуйста, не редактируйте эту распечатку, это обязательный вывод, это не настоящий зигзаг, это индивидуальный зигзаг)

Наконец, мы объединяем конкурсы каждой строки вместе, чтобы получить результирующую строку 

Psntosizainrlaeovrmtautmzdizgrnigomteceecoegptfa

У меня есть набросок алгоритма для этой проблемы, который я написал здесь в псевдокоде: 

it is asking about the relationship between {index} and {output row and  col}
Def:
  down = false;
  up = false; 
  r=0;
  c=0;
  char[][] output; 
there are three cases here:
case 1: 
  index % 4 == 0, it is the beginning of a down printing
  r = 0;
  output[r][c] = in.charAt(index);
  c++;
  down = true; up = false;

case 2:
  index%4 != 0 && down = true;
  r = index % 4;
  output[r][c] = in.charAt(index);
  if( r == 2){ up = true; down = false; c++;}  // when come to the last row of a down formatting

case 3:
  index%4 != 0 && up == true;
  r = 4- index%4;
  output[r][c] = in.charAt(index);
  c++;

Для общего решения я могу заменить 4 на nRows+1;

Хотя я думаю, что это работает, я не слишком доволен этим. У кого-нибудь есть более понятный или более быстрый алгоритм решения этой проблемы?

Ответы [ 2 ]

1 голос
/ 30 августа 2011

Одним из наблюдений, которое может значительно облегчить решение этой проблемы, является следующее: Предположим, что у вас есть количество строк, равное 3, и вы хотите продолжать зигзагообразно разбивать строки, распределяя символы.Затем, если вы переберите четыре символа, вы добавите их в строки 1, 2, 3 и 2, прежде чем повторять этот шаблон.С числом строк пять вы бы посетили ряды 1, 2, 3, 4, 5, 4, 3 и 2, прежде чем повторять этот шаблон.В более общем случае, если у вас есть количество строк k, то набор строк для распределения символов следует шаблону 1, 2, 3, ..., k, k - 1, k - 2, ..., 2, который имеет длину 2k - 2.

Учитывая это наблюдение, вы можете сделать код намного чище, предварительно рассчитав таблицу, содержащую этот цикл, а также длину этого цикла.Когда у вас есть эта таблица, вы можете циклически переключаться между персонажами, отслеживать, на каком персонаже вы находитесь.Когда вы находитесь на n-м символе, вы должны индексировать таблицу в позиции n mod k, а затем распределять символ в эту строку.

В псевдокоде (с использованием индексов на основе единицы): 

rowTable = new array of ints length 2k - 2
for i = 1 up to k:
    rowTable[i] = i
for i = 2 up to k - 1:
    rowTable[(2k - 1) - (i - 2)] = i

resultRows = new array of strings of length k

for i = 1 up to the length of your string:
    Append the current character to resultRows[rowTable[i mod k]]

Concatenate all the entries of resultRows

Этот подход не требует жесткого кодирования во всех различных случаях в оператор switch, что означает, что он может обрабатывать произвольные k вместо просто k = 3. Более того, он очень быстрый;время выполнения - O (n + k), где n - длина строки, а k - количество строк.

Надеюсь, это поможет!

0 голосов
/ 06 сентября 2012

Что вы думаете об этом.Исходная строка - s - копирует символы от 0 до rows-1 в строке, скажем str

str[rows]=some impossible to occur in d original string character , like -1

- копирует обратные символы от s[r] до s[2r-3] в str

str[2r-2]=some impossible to occur in d original string character, -1

повторять до тех пор, пока длина не будет покрыта для этих двух шагов, один за другим.

В строке str взять каждый символ в расположении строк, то есть str[0],str[rows],str[2rows] ... пропуская гдеstr[rows] равно -1.Повторите этот шаг до длины ул.

...