LeetCode #49 - Group Anagrams
HTML-код
- Опубликовано: 8 июн 2024
- В данном видео рассмотрен пример решения задачи №49 c сайта LeetCode (leetcode.com/problems/group-a...) на языке Java.
Дружное сообщество:
t.me/pse_club
Материалы для разработчиков:
proselyte.net/
00:00:00 - Анализ задания
00:01:30 - Анализ первого варианта решения
00:02:33 - Реализация первого варианта решения
00:06:28 - Оценка сложности первого варианта решения
00:07:14 - Анализ второго варианта решения
00:09:45 - Реализация второго варианта решения
00:13:29 - Оценка сложности второго варианта решения
![Dimension 20: Never Stop Blowing Up Trailer [Dropout Exclusive Series]](http://i.ytimg.com/vi/xYeXpbHnGEM/mqdefault.jpg)
Я когда решаю, некоторые или похожие задачи на LeetCode, и после успешного решения, мне становиться доступен рейтинг "всех засабмичених решений" по скорости и памяти, я еще долго сижу и улыбаюсь просматривая код из обоих топов. Но, это для многих слишком =) Спасибо за труд, лайк в копилку!
Спасибо за отзыв!
Да, есть крайне интересные и сложные решения. Побитовые операции и динамическое программирование - это отдельный мир :)
топ
Спасибо за поддержку!
А что за процедура с вычетом чара 'a' и инкрементацией?
Каждый символ char имеет последовательного цифровое значение. a - 97, b - 98 и т.д.
А если у качестве ключа использовать сумму ASCII кодов символов строки и не сортировать ничего? Ведь а = 97, z = 122, они должны получиться уникальными вроде как.
Если так, то осталось придумать, как незатратно посчитать сумму для charArray. Какой-нибудь mapToInt или просто приведением типов...
Спасибо за комментарий!
Если я верно понял идею, то тогда возможна коллизия, т.е. одна и та же сумма у разных ключей.
@EugeneSuleimanov а если hashCode() ?
@@andrey1266 сохраняется вероятность коллизии.
Классная идея, если посчитать чексуммы, то сразу отбраковываются не анаграммы и получаем группы с ключом чексуммы, внутри групп по прежнему будет сохранятся неопределенность, поэтому прогоняем их через алгоритм, между собой элементы разных групп также уже не нужно сравнивать, поскольку они точно не могут быть анаграммами.
@@EugeneSuleimanov как вариант можно помимо чексуммы делать маску наличия или отсутствия символов, только не массив, а битовую, 26 бит влезает в int), соответственно сравниваем чексуммы и инты, обеспечит ли это полную уникальность увы не знаю. Можно было бы использовать сумму и произведение, но 26 в 100 степени получается большое число, которое не влезает в целочисленные типы, его бы нормировать как-то... в общем красивое решение этой задачи лежит не в области программирования, а в области математики, нужны два или три простых алгоритма, которые каждый по отдельности не дадут уникальность, а все вместе дадут))
Так второе решение работает медленне. Или я чего не понял?)
С точки зрения оценки сложности алгоритма - быстрее.
Тоже это смутило. Решение лучше, а leetcode говорит, что оно медленнее работает и требует больше памяти)
Можно засабмитить еще раз, у литкода каждый раз разные результаты по моим наблюдениям)
Цікаве відео, дякую!!!
Скільки Ви приділятєте часу в неділю на вирішення задач такого формату? і яку складность задач зазвичай обираєте?
Дякую за відгук! Намагаюся щодня приділяти 2-2.5 години на дод. навчання. Чергую алго, системний дизайн, книги і т.д. Скільки саме йде рішення завдань не можу підказати точно. Розподіл: 40% easy, 40% medium, 20% hard.
@@EugeneSuleimanov ого!!! Гарний темп
Это и есть типа спортивное программирование? Кто как красивее типа таких задач решит?
Это не спортивное программирование. Алго задачи, которые призваны помочь определить уровень разработчика. Обычно, используются в качестве первого этапа отбора.
+
Спасибо за комментарий!
Не совсем понял, зачем стринг билдер, если массив и так маска, у нас как я понял в каждом элементе количество символов с соответствующим кодом, можно не делать никаких строковых масок, а работать прямо с массивом.
Передавать массив ключом - не рекомендуется как минимум по двум причинам:
- мутабельность
- сложности сравнения
@@EugeneSuleimanov мы его и так мутируем, обнуляем на каждой итерации, просто уберем массив в класс реализуем и reset и сравнение и хэш, вроде в сравнении сложности никакой, внутри массива примитивы.
@@denisn6408 String - иммутабелен
@@EugeneSuleimanov но он лишний, можно сделать свой иммутабельный класс с массивом внутри и билдером для добавления символов, после того как символы добавлены по билду заодно материализуем и хэш
@@denisn6408 можно сделать и класс, но какая тогда разница?
Евгений, gpt чат использовали, или сами решали?
Спасибо за вопрос!
Без ChatGPT :)