Серия «LeetCode»

Сегодня будет задачка, которая меня изрядно позабавила.

https://leetcode.com/problems/sort-colors/description/

Суть проста - отсортировать список по заданным правилам.

Я сразу схватился вспоминать алгоритмы сортировки, которые мне когда-то преподавали, гуглить, думать, пробовать... Не буду описывать все свои попытки, но в какой-то момент в голове всплыла фраза, уже не помню, где я прочитал: "Если ты в начале пути, используй встроенные функции языка, если это возможно." И таки да, простая встроенная сортировка питона решает задачу =)

Это еще одно напоминание хозяйке на заметку в части велосипедов.

Ну и традиционно решение от главного конкурента:

Решение от бота ожидаемо оказалось медленнее встроенной функции, что опять же греет =)

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

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

Суть задачки достаточно проста: по заданному набору цифр надо вернуть все возможные комбинации букв, соответсвующие этим цифрам. Из сложностей: нам заранее не известно количество цифр, и каждой цифре у нас может соответствовать разное количество букв( 3 или 4).

Для начала определим словарь, который будет задавать соответствие между символом цифры(ага цифры нам подают в виде строки), и пустую переменную результата. А дальше зададим цикл, который будет перебирать цифры по одной и записывать результат. Фокус в том, что на первой итерации цикла результат будет определен, как список из букв соответствующей первой цифре, а дальше разберем на примере:

digits = "23"

Значит на первой итерации цикла в результат запишем только буквы, соответствующие цифре 2 - это ["a","b","c"], затем срезом просто отбросим первую цифру.

На втором(и последующих) итерациях цикла нам нужно взять текущий результат, вторую цифру и записать все комбинации текущего результата и букв соответствующих второй цифре, затем отбросить вторую цифру.

На третьем(если он конечно есть) взять текущий результат, вторую цифру и записать все комбинации текущего результата и букв соответствующих третьей цифре, затем отбросить третью цифру.

И так до тех пор, пока цифра не закончатся...

Собственно и получился цикл, где мы перебираем цифры. А внутри на первой итерации(когда переменная результата пуста) задаем результат через генератор с единственным циклом, а когда не пуста задаем генератор с двумя циклами: один по текущим значениям результата, второй по буквам, соответствующим текущему значению цифры по словарю.

Результат получился быстрым и элегантным, самому понравилось.

А решение от главного конкурента оказалось слабее, по крайней мере первое рабочее решение:

Набравшись смелости и определив изрядно времени на сегодня, я решил взять задачу, помеченную как сложная. А вот собственно и она:

https://leetcode.com/problems/substring-with-concatenation-o...

На первый взгляд задачка показалась достаточно простой и смутно знакомой. Есть текст (s) и список из текстовых переменных(words). Сначала из списка текстовых переменных составляем словарь всех возможных значений, а потом пробегаемся по значениям и ищем всех их в тексте, чего же тут hard?

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

Если бы хотя бы примерно представлять размер словарика при имеющихся ограничениях на входные данные:

Как всегда перетащил тесткейс на локальную машину, и приложение сожрав 32 Гб памяти сказало кря, даже не сгенерировав словарь до конца. От словарика отказываемся....

Пару дней назад я делал что-то отдаленно похожее, там тоже надо было искать строку в подстроке, только самую длинную.

LeetCode День 2 Longest Substring Without Repeating Characters [Medium]

А тут же нам надо просто подсчитать количество подстрок в строке. Длина подстроки известна заранее - это сумма длин всех слов в words, значит ее и возьмем за длину кадра(среза строки). Т.е. задачка опять на скользящий кадр. Значит осталось сравнить кадр с имеющимися словами в words и записать результат для каждого кадра, а затем вернуть общий результат.

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

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

Решение вышло уже вполне приемлемым по скорости выполнения. На этом стоп.

Ну и как всегда я спросил у chatGPT. Бот выдал решение крайне похожее на мое, но он использовал встроенный модуль collections, о котором я знаю мало.

Однако достаточно было указать боту на низко производительный код, он выдал еще одно решение. Существенно быстрее предыдущего, за счет отказа от встроенного модуля collections в пользу встроенных словарей.

В общем было познавательно, на решение мной вбито 2+ часа. На решение ботом + оптимизация 2+ минуты.

На этот раз будем считать аквариумы объем плоских аквариумов, а значит будет много воды.

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

https://leetcode.com/problems/container-with-most-water/desc...

Собственно организуем вложенный цикл, где внешний перебирает все возможные левые стенки аквариума(т.е. кроме крайней правой), а внутренний перебирает все правые стенки аквариума(кроме крайней левой). Вуаля, и все с первого раза...

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

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

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

Но что же это значит? А значит это, что сдвигать надо всегда только меньшую по высоте сторону аквариума, потому что объем воды меряется как произведение меньшей по высоте стороны на ширину. Зафиксируем мысль, что если мы сдвигаем большую сторону аквариума, его объем точно уменьшиться, потому что ширина уменьшиться, и не важно что произойдет с высотой большей стороны, потому что считать объем мы все равно будем по меньшей. А этот расчёт для нас просто лишний, т.к. мы ищем максимальный объем аквариума. А это значит, что такой расчёт объема просто не нужно выполнять. Вот тут мы и сэкономим количество итераций.

Обратите внимание на картинку ниже, для обхода всех вариантов понадобилось всего 8 обсчётов объема, тогда когда как для первого решения это было бы 36 обсчётов(8 + 7 + 6 + 5 + 4 + 3 + 2 + 1). Да и увеличение числа границ на единицу для последнего решения увеличивает количество обсчётов всего на 1(линейная зависимость), тогда как для первого решения получается арифметическая прогрессия.

Все рассуждения выше подтвердились результатами:

От ChatGpt узнал, что это называется подход с двумя указателями решение в общем то идентично:

Сегодня было не сложно, пользоваться гайдами не стыдно, все уже изобретено до нас =)

Несмотря на знатное облажание в прошлый раз, я решил продолжить ̶л̶а̶ж̶а̶т̶ь̶ ̶п̶у̶б̶л̶и̶ч̶н̶о̶ решать задачи и выкладывать свои соображения тут.

https://leetcode.com/problems/longest-substring-without-repe...

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

Очевидное решение в лоб - это перебрать все возможные подстроки внутри данной строки и оценить эти подстроки на уникальность символов. Значит нам нужна функция для определения строки из уникальных символов и какой-то цикл обхода.

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

Действительно это будет работать для относительно коротких строк, но я не обратил внимание на мелкий шрифт в конце:

Т.е. на вход может подаваться текст на 50000 знаков. На одном из кейсов я закономерно получил ошибку, и даже перенеся на локальную машину подсчёты затянулись на 10+ минут, дальше я просто прервал исполнение.

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

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

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

Ну и таки да, сначала подсчитали максимально возможный размер подстроки в отдельной функции и все тесты прошли успешно.

Ну и бонусом решение от chatGpt, которое оказалось намного лучше моего:

В целом собой доволен, но решение от chatGpt опять вгоняет меня в уныние. Мало того, что бот сделал быстрее чем я, он сделал сильно лучше, чем я.

Всем привет. Сегодня решил взять задачку посложнее начального уровня и вот что из этого вышло. Ссылка на задачу:

https://leetcode.com/problems/reverse-integer/description/

Как я понял задачу: на вход подается целое число в пределах от -2 ** 31 <= x <= (2 ** 31) - 1. Нужно вернуть целое число с цифрами в обратном порядке и тем же знаком(+/-). Если результат вышел за пределы -2 ** 31 <= x <= (2 ** 31) - 1 вернуть 0.

Что пришло в голову сразу же, как можно решить в лоб:

Сначала отбросим знак в какую-нибудь переменную и будем работать с неотрицательным числом. Для этого определим статический метод класса, который будет определять, отрицательное ли наше число. В общем то, можно прямо в функции было сравнивать заданное число с нулем, но принцип единственной ответственности (SRP) запрещает:

Самая проблема, что мы не знаем порядка числа(сколько цифр в числе), поэтому принял решение брать последнюю цифру в числе через остаток от деления на 10 и отбрасывать ее через целочисленное деление на 10:

Ну и завернуть все это в цикл while, с условием пока x - положительный :

В принципе на этом можно было бы и закончить, все таки 15% лучших по скорости, но уж как то все это кривовато. Пока думал, как же определить количество разрядов в числе, где-то на границе создания вертелось, что можно проще и вот эта строка не давала покоя: count = len(str(x))

Тут мы определяем количество разрядов просто по количеству символов, а что если для решения задачи работать не с числом, а с символами, которые их означают?

И таки да, сначала число приводим к строке, затем через срез разворачиваем строку и приводим обратно к числу.

Схлопнем эти три строки в одну, поправим логику в методе проверки результата и отправим итоговое решение:

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

Посмотрим, что же предлагает нам chatGPT:

Я добился результата за 20 минут, бот за две секунды. Я конечно понимаю, что я новичок, что алгоритмические задачки хорошо сформулированы, но разница в производительности заставляет задуматься.