Каждое решение начинается со стратегии, а алгоритм – это стратегия решения проблемы кодирования. Поэтому программисты должны научиться разрабатывать эффективный алгоритм и преобразовывать этот «алгоритм» в правильный код, чтобы выполнять свою работу.
Но в структуре данных и алгоритмах существует множество проблем с кодированием, и в большинстве случаев эти проблемы для нас новы. Таким образом, как программист, мы должны развиваться как уверенные в себе решатели проблем, которых не пугает сложность данной проблемы. Наша долгосрочная цель должна быть простой: научиться создавать правильный и эффективный код за заданное время. По мере того, как мы будем практиковаться все больше и больше, у нас будет больше опыта в решении проблем, и наша работа будет легкой. Вот некоторые важные навыки, которые мы должны практиковать для каждой проблемы с кодированием:
- Разработка подхода к пониманию проблемы
- Думая о правильном базовом решении
- Разработка пошагового решения для псевдокода
- Анализ эффективности решения
- Дальнейшая оптимизация решения
- Преобразование псевдокода в правильный код
Теперь критический вопрос будет заключаться в следующем: существует ли какая-то четко определенная управляемая стратегия для подхода и решения проблемы кодирования? Если да, то каковы важные шаги? Давайте думать и исследовать!
Шаг 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 и т. д. Никогда не забывайте тестировать фактический код с помощью образцов тестовых данных и проверять, равен ли фактический результат ожидаемый результат. При написании кода на собеседованиях обсуждайте образцы данных или тестовые примеры с интервьюером.
Упрощение и оптимизация кода может потребовать нескольких итераций наблюдения. Нам нужно задать эти вопросы, как только мы закончим писать код:
- Выполняется ли этот код для всех возможных входных данных, включая пограничные случаи?
- Можем ли мы оптимизировать код дальше? Можем ли мы удалить некоторые переменные, цикл или дополнительное пространство?
- Часто ли мы повторяем некоторые шаги? Можем ли мы определить его отдельно, используя другую функцию?
- Является ли код читабельным или написанным с хорошим стилем кодирования?
Дополнительные проблемы для отработки шагов решения проблем
- Переместить нули в конец массива
- Найти минимальное и максимальное значение в массиве
- Удалить дубликаты из отсортированного массива
- Сортировка массива 0, 1 и 2
- Повернуть матрицу на 90 градусов против часовой стрелки
- Контейнер с наибольшим количеством воды
- Сортировка массива в осциллограмме
- n Повторяющийся элемент в массиве размером 2n
- Поиск в 2D-матрице, отсортированной по строкам
- Найти k-й наименьший элемент в массиве
- Действительный горный массив
Наслаждайтесь обучением, наслаждайтесь программированием, наслаждайтесь алгоритмами!