Привет, парень, который скоро станет разработчиком программного обеспечения. Если вы, как и я, готовитесь к предстоящим собеседованиям, вы, скорее всего, решите (или собираетесь) решать множество проблем с алгоритмами. В этом посте я хотел бы рассказать о проблеме, которую я недавно решил, в надежде лучше понять ее сам, а также помочь всем, кто может столкнуться с подобными проблемами.
Для этого конкретного плохого парня нам поручили написать функцию, которая распечатывает двустороннюю пирамиду уровней n
, которая следует нескольким простым правилам. Я придумал два способа решения этой проблемы (один я предпочитаю другому). Давайте начнем!
Двусторонняя пирамида, объяснение
Конкретная инструкция для этой проблемы следующая:
Напишите функцию, которая принимает положительное число n. Функция должна отображать в консольном журнале форму пирамиды с n уровнями с использованием символа #. Убедитесь, что у пирамиды есть пробелы с левой * и * правой стороны.
Примеры:
Примечание: эта проблема была взята из курса Стивена Грайдера Udemy Алгоритмы + структуры данных, который я настоятельно рекомендую.
Решение # 1
Сначала я рассмотрел приведенные примеры, чтобы выявить общие закономерности, и записал эти наблюдения. Вот как я разбил шаблоны на примере pyramid(4)
.
- Во-первых, я связал свои наблюдения со стабильным аргументом
n
. В данном случае пирамида состоит из4
илиn
строк. - Затем я пошел по порядку и снова записал свои наблюдения относительно того, сколько пробелов находится по обе стороны от
#
. Из этого я вывел, чтоspaceCount
или количество пробелов с обеих сторон начинается сn — 1
(или4 — 1
, что составляет3
). Для каждой новой строкиspaceCount
уменьшается на1
с каждой стороны, пока вы не дойдете до последней строки, и в этом случае конечныйspaceCount
будет0
. - С другой стороны,
hashCount
или количество#
в середине каждой строки начинается с1
и увеличивается на2
каждый раз, когда вы переходите к новой строке. - Помня об этих наблюдениях, я начал псевдокодирование решения, которое выглядит так:
- Создайте переменную с именем
spaceCount
, изначально установленную наn — 1
. - Создайте другую переменную с именем
hashCount
, изначально установленную на1
. - В то время как
spaceCount
не достигло значения ниже0
,console.log
изspaceCount
количество пробелов, за которым следуетhashCount
количество#
, за которым снова следуетspaceCount
количество пробелов. Я использовалspaceCount
в качестве переменной, значение которой определяет, когда я буду «готов», так как я знаю, что мы закончим печать пирамиды, как только дойдем до строки только с#
и без пробелов. - После каждой итерации мы устанавливаем новое значение
spaceCount
на единицу меньше, чем было, и устанавливаем новое значениеhashCount
на два значения больше, чем было.
- Затем я закодировал свое решение:
Во внешнем цикле while я создал две переменные с именами spaces
и hashes
, в которых будут храниться фактические фрагменты строки; изначально это пустые строки. Я создал два внутренних цикла while, которые добавляют к указанным пустым строкам либо пробелы, либо #
в соответствии с текущими spaceCount
и hashCount
. Затем я объединил части строки и console.log
вытащил их. И, наконец, я уменьшаю spaceCount
на 1
и увеличиваю hashCount
на 2
для каждой итерации внешнего цикла while.
И вуаля, готово! Мне нравится это первое решение, поскольку оно в точности соответствует тому, что я наблюдал, без особых математических расчетов (не считая подсчета). Следующее решение, на мой взгляд, немного сложное, но я считаю, что изучение нескольких способов решения одной и той же проблемы всегда приводит меня к чему-то новому.
Решение # 2
Это решение предполагает рассмотрение пирамиды в виде строк и столбцов. Таким образом, вы можете идентифицировать каждую позицию в пирамиде, указав номер строки, к которой она принадлежит, и номер столбца, к которому она принадлежит, в стиле линкора. Используя эту матрицу, мы можем определить, в какой позиции добавить #
, а в какой - добавить пространство. Я нарисовал диаграмму, помеченную rowIdx
и columnIdx
, и выделил несколько наблюдений:
Здесь есть несколько «стабильных» переменных, на которые мы можем обратить внимание. Во-первых, все строки имеют общую «среднюю точку» в columnIdx 3
, мы можем использовать это, чтобы определить «диапазон» columnIdx
, в который мы будем добавлять #
, а не пробелы. Во-вторых, мы замечаем, что длина каждой строки постоянно 7
. Это полезно знать, чтобы при построении каждой строки мы знали, когда остановиться.
Мы будем использовать два for
цикла: внутренний цикл, который добавляет либо #
, или пробел в конкретную строку, и внешний цикл, который распечатывает каждую строку. Давайте решим этот слой за раз, сначала построив внешний цикл:
- Во второй строке мы указываем, что будем создавать строки от индекса
0
до индекса прямо передn
. Учитывая, что здесь происходит индексирование на основе 0, условиеrowIdx < n
гарантирует, что мы завершим цикл сn
количеством распечатанных строк.rowIdx++
- это итерационная часть циклаfor
, которая гарантирует, что мы увеличиваем индекс на единицу с каждой итерацией. - Обратите внимание, что
row
еще не определен. Затем давайте обсудим логику того, как мы конкретизируем каждую строку с учетом сделанных нами наблюдений, а затем закодируем соответствующим образом.
Сначала я написал, как вычислить стабильную длину каждой строки из n
, поскольку n
- единственный аргумент, передаваемый в функцию; следовательно, нам нужно найти способы вывести все остальное, связанное с n
. Чтобы перейти от n = 4
к rowLength = 7
, мы можем использовать формулу: rowLength = n * 2 — 1
. Знание длины полезно для нашего внутреннего for
цикла, поскольку мы можем установить его как условие, где, пока columnIdx
меньше, чем rowLength
, мы можем продолжать добавлять символы (либо #
, либо пробел).
Затем я написал, как я могу вычислить midpoint
, в приведенном выше случае это columnIdx 3
. А это формула: midpoint = Math.floor(rowLength / 2)
. Поскольку rowLength
в данном случае это 7
, 7 / 2 = 3.5
. Используя Math.floor()
, мы округляем результат до 3
, таким образом получая columnIdx 3
.
Затем я вывел образец пробелов и #
для каждой строки по отношению к midpoint
и rowIdx
, вот так:
- Глядя на шаблон выше, мы можем сказать, что
columnIdx
, куда мы будем добавлять#
, относятся кstartIdx
midpoint — rowIdx
кendIdx
midpoint + rowIdx
. Обратитесь к приведенной выше диаграмме для визуального представления матрицы строк и столбцов.
Учитывая всю эту информацию, мы можем написать логику для построения каждой строки следующим образом:
- Создайте переменную с именем
row
, которая изначально является пустой строкой. - Определить
rowLength
- Определить
midpoint
- Цикл от
columnIdx
к индексу непосредственно передrowLength
- Диапазон индексов, в которые мы должны поместить
#
, отstartIdx
изmidpoint — rowIdx
доendIdx
изmidpoint + rowIdx
, как указано выше. - Если текущий
columnIdx
принадлежит этому диапазону, тогда добавьте#
к строкеrow
, если нет, добавьте вместо этого пробел
И, наконец, код:
Опять же, я предпочитаю первое решение, поскольку оно требует меньше вычислений и намного проще. Однако это решение позволяет по-другому взглянуть на ту же проблему. Есть третье решение, которое включает в себя рекурсию, но я не буду здесь вдаваться в подробности.
Навыки, которые я приобрел при решении этой проблемы, включают: 1) поэтапное изложение закономерностей, которые я наблюдал в приведенных примерах, и 2) соотнесение упомянутых наблюдений с «стабильными» переменными, особенно с аргументами, предоставленными для функция.
Надеюсь, вы найдете это полезным. И я желаю вам всего наилучшего на следующем собеседовании по программированию!