Привет, парень, который скоро станет разработчиком программного обеспечения. Если вы, как и я, готовитесь к предстоящим собеседованиям, вы, скорее всего, решите (или собираетесь) решать множество проблем с алгоритмами. В этом посте я хотел бы рассказать о проблеме, которую я недавно решил, в надежде лучше понять ее сам, а также помочь всем, кто может столкнуться с подобными проблемами.

Для этого конкретного плохого парня нам поручили написать функцию, которая распечатывает двустороннюю пирамиду уровней n, которая следует нескольким простым правилам. Я придумал два способа решения этой проблемы (один я предпочитаю другому). Давайте начнем!

Двусторонняя пирамида, объяснение

Конкретная инструкция для этой проблемы следующая:

Напишите функцию, которая принимает положительное число n. Функция должна отображать в консольном журнале форму пирамиды с n уровнями с использованием символа #. Убедитесь, что у пирамиды есть пробелы с левой * и * правой стороны.

Примеры:

Примечание: эта проблема была взята из курса Стивена Грайдера Udemy Алгоритмы + структуры данных, который я настоятельно рекомендую.

Решение # 1

Сначала я рассмотрел приведенные примеры, чтобы выявить общие закономерности, и записал эти наблюдения. Вот как я разбил шаблоны на примере pyramid(4).

  • Во-первых, я связал свои наблюдения со стабильным аргументом n. В данном случае пирамида состоит из 4 или n строк.
  • Затем я пошел по порядку и снова записал свои наблюдения относительно того, сколько пробелов находится по обе стороны от #. Из этого я вывел, что spaceCount или количество пробелов с обеих сторон начинается с n — 1 (или 4 — 1, что составляет 3). Для каждой новой строки spaceCount уменьшается на 1 с каждой стороны, пока вы не дойдете до последней строки, и в этом случае конечный spaceCount будет 0.
  • С другой стороны, hashCount или количество # в середине каждой строки начинается с 1 и увеличивается на 2 каждый раз, когда вы переходите к новой строке.
  • Помня об этих наблюдениях, я начал псевдокодирование решения, которое выглядит так:
  1. Создайте переменную с именем spaceCount, изначально установленную на n — 1.
  2. Создайте другую переменную с именем hashCount, изначально установленную на 1.
  3. В то время как spaceCount не достигло значения ниже0, console.log из spaceCount количество пробелов, за которым следует hashCount количество #, за которым снова следует spaceCount количество пробелов. Я использовал spaceCount в качестве переменной, значение которой определяет, когда я буду «готов», так как я знаю, что мы закончим печать пирамиды, как только дойдем до строки только с # и без пробелов.
  4. После каждой итерации мы устанавливаем новое значение 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. Обратитесь к приведенной выше диаграмме для визуального представления матрицы строк и столбцов.

Учитывая всю эту информацию, мы можем написать логику для построения каждой строки следующим образом:

  1. Создайте переменную с именем row, которая изначально является пустой строкой.
  2. Определить rowLength
  3. Определить midpoint
  4. Цикл от columnIdx к индексу непосредственно перед rowLength
  5. Диапазон индексов, в которые мы должны поместить #, от startIdx из midpoint — rowIdx до endIdx из midpoint + rowIdx, как указано выше.
  6. Если текущий columnIdx принадлежит этому диапазону, тогда добавьте # к строке row, если нет, добавьте вместо этого пробел

И, наконец, код:

Опять же, я предпочитаю первое решение, поскольку оно требует меньше вычислений и намного проще. Однако это решение позволяет по-другому взглянуть на ту же проблему. Есть третье решение, которое включает в себя рекурсию, но я не буду здесь вдаваться в подробности.

Навыки, которые я приобрел при решении этой проблемы, включают: 1) поэтапное изложение закономерностей, которые я наблюдал в приведенных примерах, и 2) соотнесение упомянутых наблюдений с «стабильными» переменными, особенно с аргументами, предоставленными для функция.

Надеюсь, вы найдете это полезным. И я желаю вам всего наилучшего на следующем собеседовании по программированию!