DasKoldir

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

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 минут, бот за две секунды. Я конечно понимаю, что я новичок, что алгоритмические задачки хорошо сформулированы, но разница в производительности заставляет задуматься.

Я хз, поймёте ли вы, но попробую донести. Я сам из тех мест, из Архангельской области.

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

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

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

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