2D траверса в спиральном узоре с использованием рекурсии - PullRequest
5 голосов
/ 01 ноября 2009

Я готовлюсь к собеседованию и застрял в этом вопросе довольно давно. Может кто-нибудь, пожалуйста, помогите мне с кодом. Если не завершено, то может быть фрагмент этого? Пожалуйста ..

1 Ответ

18 голосов
/ 01 ноября 2009

Python 2, печатает вложенный 2D-список по часовой стрелке, от верхнего левого угла до центра:

>>> def clockwise(r):
...     return list(r[0]) + clockwise(list(reversed(zip(*r[1:])))) if r else []
... 
>>> a = [ 
...   [ 1,  2,  3], 
...   [ 5,  6,  7], 
...   [ 9, 10, 11]]
>>> clockwise(a)
[1, 2, 3, 7, 11, 10, 9, 5, 6]
>>> a = [ 
...   [ 1,  2,  3,  4], 
...   [ 5,  6,  7,  8], 
...   [ 9, 10, 11, 12],
...   [13, 14, 15, 16]]
>>> clockwise(a)
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

Так что здесь происходит? Аргументом clockwise является двумерный массив r. Мы хотим напечатать его содержимое слева направо, по часовой стрелке. Поэтому, если двумерный массив не пустой, мы можем напечатать его первый элемент, который является верхней строкой. Далее мы хотим напечатать последние элементы оставшихся строк (числа справа). Мы не хотим повторяться. Так что мы делаем, чтобы преобразовать оставшиеся строки так, чтобы следующие числа, которые будут напечатаны, находились в верхней строке. Мы делаем это путем транспонирования оставшихся строк (чтобы они стали столбцами), а затем их обращения.

Возможно, алгоритм станет понятнее, если я напишу его на Хаскеле:

import Data.List

clockwise :: [[a]] -> [a] 
clockwise (x:xs) = x ++ (clockwise $ reverse $ transpose $ xs) 
clockwise _      = []
...