Каждое решение начинается со стратегии, а алгоритм – это стратегия решения проблемы кодирования. Поэтому программисты должны научиться разрабатывать эффективный алгоритм и преобразовывать этот «алгоритм» в правильный код, чтобы выполнять свою работу.

Но в структуре данных и алгоритмах существует множество проблем с кодированием, и в большинстве случаев эти проблемы для нас новы. Таким образом, как программист, мы должны развиваться как уверенные в себе решатели проблем, которых не пугает сложность данной проблемы. Наша долгосрочная цель должна быть простой: научиться создавать правильный и эффективный код за заданное время. По мере того, как мы будем практиковаться все больше и больше, у нас будет больше опыта в решении проблем, и наша работа будет легкой. Вот некоторые важные навыки, которые мы должны практиковать для каждой проблемы с кодированием:

  • Разработка подхода к пониманию проблемы
  • Думая о правильном базовом решении
  • Разработка пошагового решения для псевдокода
  • Анализ эффективности решения
  • Дальнейшая оптимизация решения
  • Преобразование псевдокода в правильный код

Теперь критический вопрос будет заключаться в следующем: существует ли какая-то четко определенная управляемая стратегия для подхода и решения проблемы кодирования? Если да, то каковы важные шаги? Давайте думать и исследовать!

Шаг 1: Понимание проблемы

Решение проблемы требует четкого понимания проблемы. К сожалению, иногда мы читаем первые несколько строк и принимаем на себя оставшуюся часть проблемы. Или иногда мы игнорируем этот шаг из-за чего-то подобного, что мы видели в прошлом. Мы должны считать это недобросовестной практикой и разработать четкий подход к пониманию проблемы.

При решении проблем каждая мелочь может помочь нам разработать эффективное решение. Иногда небольшое изменение в вопросе может изменить подход к решению. Небольшое дополнительное время на понимание проблемы придаст нам больше уверенности позже. Дело в том, что мы никогда не хотим узнать на полпути, что неправильно поняли проблему.

Неважно, проходили ли мы вопрос в прошлом или нет: мы должны прочитать вопрос несколько раз. Так что возьмите бумагу и записывайте все, пока решаете проблему. Изучение некоторых примеров также поможет нам прояснить, сколько случаев может обрабатывать наш алгоритм и возможные шаблоны ввода-вывода. Мы также должны изучить сценарий для больших входных данных, пограничных случаев и недопустимых входных данных. Иногда описание проблемы довольно часто страдает от следующих типов недостатков:

  • Описание проблемы может основываться на некоторых неопределенных предположениях.
  • Описание проблемы может быть двусмысленным или неполным
  • Описание проблемы содержит различные противоречия

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

  • Что такое вход и выход?
  • Какой тип данных доступен?
  • Каков размер или масштаб ввода?
  • Как хранятся данные? Какова структура данных?
  • Есть ли в данных какие-то особые условия или порядки?
  • Какие существуют правила работы с данными?

Шаг 2: Обдумывание правильного базового решения

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

  • Помогите нам построить хорошую уверенность или мотивацию в начале.
  • Обеспечьте отличную точку для начала разговора с интервьюером.
  • Иногда это дает подсказку для повышения эффективности за счет сокращения некоторых циклов, удаления некоторых промежуточных шагов или эффективного выполнения некоторых операций.

Вот несколько примеров шаблонов грубой силы: три вложенных цикла, два вложенных цикла, решение с использованием дополнительной памяти, решение с использованием сортировки, двойной обход в двоичном дереве с учетом всех подмассивов или подстрок, полный перебор и т. д.

Обдумав и изложив идею грубой силы, интервьюер может спросить о ее временной и пространственной сложности. Нам нужно работать на бумаге, анализировать каждую критическую операцию и писать в форме нотации Big-O. На этом этапе важно четкое концептуальное представление об анализе пространственно-временной сложности. Хорошая практика анализа различных шаблонов кода (итеративного, рекурсивного и т. д.) очень помогла бы.

Шаг 3: Разработка эффективных решений для псевдокода

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

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

Идея была бы простой: мы должны изучить вариант использования эффективных шаблонов решения проблем в различных структурах данных. Постоянно думать, анализировать и искать лучшее решение — основная идея.

Вот несколько лучших примеров задач, в которых возможны несколько уровней оптимизации. Практика таких типов вопросов по кодированию очень помогает укрепить уверенность.

Найти индекс равновесия массива

  • Использование вложенных циклов: время = O(n²), память = O(1)
  • Использование массива суммы префиксов: Время = O(n), Память = O(n)
  • Использование одиночного сканирования: Время = O(n), Память = O(1)

Ловушка дождевой воды

  • Использование вложенных циклов: время = O(n²), память = O(1)
  • Использование динамического программирования: время = O(n), память = O(n)
  • Использование стека: время = O(n), память = O(n)
  • Использование двух указателей: Время = O(n), Память = O(1)

Проверить на пару с заданной суммой

  • Использование вложенных циклов: время = O(n²), память = O(1)
  • Использование сортировки и бинарного поиска: Время = O(nlogn), Память = O(1)
  • Использование сортировки и двух указателей: время = O(nlogn), память = O(1)
  • Использование хэш-таблицы: время = O(n), память = O(n)

Найти старший элемент в массиве

  • Использование двух вложенных циклов: Время = O(n²), Память = O(1)
  • Использование сортировки: время = O(nlogn), память = O(1)
  • Использование принципа «разделяй и властвуй»: время = O(nlogn), память = O(logn)
  • Использование хэш-таблицы: время = O(n), память = O(n)
  • Использование битовых манипуляций: время = O(n), память = O(1)
  • Использование рандомизации: Время = O(logn), Память = O(1)
    Примечание. Если значение n очень велико.
  • Алгоритм голосования Бойера-Мура: время = O (n), память = O (1)

Максимальная сумма подмассива

  • Использование трех вложенных циклов: Время = O(n³), Память = O(1)
  • Использование двух вложенных циклов: Время = O(n²), Память = O(1)
  • Используя разделяй и властвуй: Время = O(nlogn), Память = O(logn)
  • Использование динамического программирования: время = O(n), память = O(n)
  • Алгоритм Кадане: время = O(n), память = O(1)

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

Шаг 4: Преобразование псевдокода в чистый, правильный и оптимизированный код

Наконец, нам нужно заменить каждую строку псевдокода реальным кодом на наших любимых языках программирования, таких как C++, Java, Python, C#, JavaScript и т. д. Никогда не забывайте тестировать фактический код с помощью образцов тестовых данных и проверять, равен ли фактический результат ожидаемый результат. При написании кода на собеседованиях обсуждайте образцы данных или тестовые примеры с интервьюером.

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

  • Выполняется ли этот код для всех возможных входных данных, включая пограничные случаи?
  • Можем ли мы оптимизировать код дальше? Можем ли мы удалить некоторые переменные, цикл или дополнительное пространство?
  • Часто ли мы повторяем некоторые шаги? Можем ли мы определить его отдельно, используя другую функцию?
  • Является ли код читабельным или написанным с хорошим стилем кодирования?

Дополнительные проблемы для отработки шагов решения проблем

Наслаждайтесь обучением, наслаждайтесь программированием, наслаждайтесь алгоритмами!