Привет, друзья, надеюсь, у вас все положительные результаты, а тесты отрицательные! Сегодня я хочу поговорить о шаблонах решения проблем для организации ваших данных. Как программист, вы столкнетесь со многими из этих закономерностей на протяжении своей карьеры. Вы особенно увидите их в Leet Code, Hacker Rank и технических интервью. Мы обсудим следующие шаблоны: счетчик частоты, множественный указатель, скользящее окно и разделение и владение. Конечно, есть намного больше шаблонов, но я считаю, что начало работы с этими четырьмя шаблонами поможет новичкам получить представление о создании таких шаблонов. Освоение потока позволит вам перейти к более сложным схемам, и я с радостью расскажу вам больше о них в ближайшем будущем! Перейдем к первым четырем паттернам.
1. Шаблон частотомера
Наш первый шаблон использует объекты или наборы для сбора значений / частот значений. Это полезно, когда у вас есть несколько частей входных данных, и вам нужно сравнить их, чтобы увидеть, содержат ли они одинаковые значения, следовательно, частоты. Я буду использовать задачу LeetCode, чтобы объяснить процесс этого шаблона. Эта проблема называется validAnagrams, и мы должны проверить, состоят ли две входные строки из одинакового количества букв. Нам нужно увидеть, повторяются ли наши части входных данных (символы обеих строк) одинаковое количество раз.
На рисунке 1.0 мы создали переменный объект под названием lookup. Эта переменная является нашим частотомером, и если мы посмотрим на строки с 9 по 13, мы сохраним элементы в нашей переменной. Посмотрите внимательно на строку 12, мы используем троичный оператор, чтобы проверить, сохранил ли наш частотомер ту же букву. Если буква уже сохранена в нашей переменной поиска, увеличьте ее на единицу, а если нет, мы установим ее на единицу. Эта часть очень важна, потому что мы не просто сохраняем элементы из строки, мы также подсчитываем, сколько раз это произошло. Теперь, если мы посмотрим на строки с 14 по 20, это частотный образец в действии. Точно так же, как мы добавляли буквы в поиск переменной, теперь мы убираем буквы и количество, которое они получили. Мы используем условные операторы для проверки буквы второй строки и поиска переменной. Если буква из второй строки не совпадает ни с одной из букв, которые отслеживаются поиском, возвращает false, в противном случае уменьшите вхождение на 1.
2. Шаблон с несколькими указателями
Во втором шаблоне он использует указатели или значения, которые соответствуют индексу или позиции, и перемещается к началу, середине или концу в зависимости от определенного условия. В следующей задаче мы собираемся проверить, имеет ли отсортированный массив нулевую сумму. Нам нужно будет перебрать массив и посмотреть, равны ли указатели в сумме нулю.
Прежде чем мы начнем добавлять индексы, нам нужно создать указатели. На рисунке 1.1 мы создаем левую и правую переменные, чтобы отслеживать, где мы находимся в массиве. Поскольку нам нужно проверять каждый индекс, мы используем цикл while, который останавливается, когда левый становится больше правого. По мере того, как мы перебираем индексы, мы добавляем элемент индекса left и right и присваиваем это значение переменной sum. Затем мы проверим, равна ли эта переменная sum 0. Если она равна 0, отлично, мы вернем элемент индекса. Что будет, если сумма больше 0? Затем мы уменьшим правую сторону на 1 и наоборот, если сумма меньше 0.
3. Скользящее окно
Шаблон скользящего окна включает создание окна, которое может быть либо массивом, либо числом от одной позиции до другой. Это полезно для отслеживания подмножества данных в строке / массиве, и в зависимости от условия окно может уменьшаться или увеличиваться. В следующей задаче от LeetCode мы воспользуемся этим шаблоном и посмотрим, что это за окно. Эта проблема принимает входной массив и число. Это число станет размером нашего окна.
В этой задаче нам нужно создать переменные-заполнители, чтобы отслеживать максимальную сумму и временную сумму. Временная сумма будет постоянно меняться, потому что она будет проходить цикл for. Теперь, когда это решено, нам нужно создать фиксированное окно. Для этого мы используем цикл for и перебираем массив определенное количество раз. Пока мы выполняем итерацию определенное количество раз, мы добавляем значения индекса в maxSum, потому что на данный момент это наибольшая сумма. Здесь на помощь приходит tempSum, мы даем ему то же значение, что и maxSum. Затем мы добавляем значения наших индексов в tempSum. После того, как мы добавили все значения внутри окна, мы сравниваем переменные и видим, какая из них больше, а затем увеличиваем все окно на 1.
4. Разделяй и властвуй
Наш последний шаблон включает в себя разделение набора данных на более мелкие части, а затем повторение процесса с набором подданных. Как только мы больше не можем повторять процесс, мы снова встраиваем подданные в новый набор данных на основе условия. Думайте об этом как о том, чтобы начать разбивать его на более мелкие части, а затем что-то делать с каждой более мелкой частью, чтобы определить, куда идти дальше. Этот шаблон разделяет набор данных, затем захватывает набор субданных и объединяется обратно в новый набор данных. Эта последняя задача называется отсортированной из курса udemy, и эта задача принимает отсортированный массив и значение. Мы будем искать это значение в массиве, и, если нам удалось найти это значение, мы распечатаем индекс.
В этой задаче мы собираемся разделить массив пополам. Мы собираемся пролить его, потому что это ускорит процесс. Так мы сможем более эффективно найти индекс нашей ценности. В примере ввода на рисунке 1.3 значение 6 находится в 5-м индексе массива. В строке 111 мы разбиваем массив пополам и используем это в качестве отправной точки для этого шаблона. Мы проверим и посмотрим, больше или меньше начальная точка входного значения. Если оно больше, мы уменьшим начальную точку на 1 и присвоим ей значение max. Затем мы будем повторять процесс до тех пор, пока он не достигнет индекса, в котором его значение будет равно входному значению. То же самое происходит, если оно меньше входного значения.
Я надеюсь, что это помогло прояснить поток паттернов! Их изначально сложно понять, и на их изучение требуется время. Однако, как только вы получите структуру этих шаблонов, с техническим собеседованием будет легче справляться. Будьте осторожны и удачного кодирования!
