«веб-макак» 😂

надо тут похвастаться моей наркоманской версией permutations-ii. В дискуссиях не нашел другого дятла, который зафигачил бы префиксное дерево)) https://leetcode.com/problems/permutations-ii/discuss/930497/Solution-you-haven't-seen-before-(trie!)

надо тут похвастаться моей наркоманской версией permutations-ii. В дискуссиях не нашел другого дятла, который зафигачил бы префиксное дерево)) https://leetcode.com/problems/permutations-ii/discuss/930497/Solution-you-haven't-seen-before-(trie!)

надо тут похвастаться моей наркоманской версией permutations-ii. В дискуссиях не нашел другого дятла, который зафигачил бы префиксное дерево)) https://leetcode.com/problems/permutations-ii/discuss/930497/Solution-you-haven't-seen-before-(trie!)

Я премутации очень тупо решал: class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [[]] for n in nums: temp = [] for comb in res: for i in range(len(comb)+1): temp.append(comb[:i] + [n] + comb[i:]) res = temp return res

Но не будет наверное работать, если надо будет возвращать премутации с уникальными элементами (типо (1,2,1) и (1,1,2) одно и тоже)

“не будет наверное работать” - что ж вы батенька обо мне такого низкого мнения, что думаете, что я в священные leetcode-discussions полезу с неоттестированным кодом!

это не те, это у тебя permutations-1

Я премутации очень тупо решал: class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [[]] for n in nums: temp = [] for comb in res: for i in range(len(comb)+1): temp.append(comb[:i] + [n] + comb[i:]) res = temp return res

у меня почти слово в слово permutations-1 так же сделано. Там в решениях много всяких подходов, и они все сложнее, чем вот этот.

у меня почти слово в слово permutations-1 так же сделано. Там в решениях много всяких подходов, и они все сложнее, чем вот этот.

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: res = set([()]) for n in nums: temp = set() for comb in res: for i in range(len(comb)+1): temp.add(comb[:i] + (n,) + comb[i:]) res = tuple(temp) return res

Runtime: 56 ms, faster than 69.61% of Python3 online submissions for Permutations II. Memory Usage: 14.4 MB, less than 10.13% of Python3 online submissions for Permutations II. Runtime: 44 ms, faster than 98.73% of Python3 online submissions for Permutations II. Memory Usage: 14.3 MB, less than 10.13% of Python3 online submissions for Permutations II. Runtime: 52 ms, faster than 85.97% of Python3 online submissions for Permutations II. Memory Usage: 14.4 MB, less than 10.13% of Python3 online submissions for Permutations II.

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: res = set([()]) for n in nums: temp = set() for comb in res: for i in range(len(comb)+1): temp.add(comb[:i] + (n,) + comb[i:]) res = tuple(temp) return res

Погоди, массивы сравниваются внутри сета не по ссылке?

Погоди, массивы сравниваются внутри сета не по ссылке?

Сравниваются? Это tuple, я предпологаю они в тупую как текст сравнивается

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

Можно ж как-то через многочлены?

Да не коллизий. Просто захэшировал [1,2,3], а его по ссылке сделали [1,2,2] вот и все, хана сэту. Да, я сначала тоже в текст переводил

В хеш таблице ключи всегда строки. Придётся объект сериализовать в строку как-то.

Хз. Не совсем понял о чем ты/вы

Хочется как-то единообразно превращать массив в чиселко. У меня какие-то мутные воспоминания о том, что элементы массива могут стать коэффициентами в полиноме

вроде это rolling hash называется, когда в этом многочлене в качестве x выбирается некоторое простое число, обычно 31 или 53, а все остальные чиселки являются коэффициентами, плюс по модулю какому-нибудь большому считается а-ля 1e9+7, но тоже простому числу, и получается более или менее равномерное распределение по индексам

а разве в таком случае не будет коллизии на [0,0,1] и [0,0,-1] ?

да, в таком случае будет. rolling hash хорошо работает для строк, когда там по смыслу коэффициенты от 1 до 26 натуральные числа. но на самом деле если и будет коллизия что страшного? положим в цепочку

Я вызываю экзорциста. Вы говорите о какой-то черной магии

мы говорим про функции хеширования, конкретно вот про этот вариант — https://www.geeksforgeeks.org/string-hashing-using-polynomial-rolling-hash-function/ , если хочется сделать шаг назад и понять как работает хеш-таблица и нахера мы вообще сейчас про это говорим, то советую посмотреть моё видео про хеш-таблицы 😊

вот этот видосик в смысле (если ещё не смотрел) https://www.youtube.com/watch?v=FZEi19-B3XA&list=PLvWwA9iDlhHB1qp22la3mn01JuVOwyuqw&index=4

да, в таком случае будет. rolling hash хорошо работает для строк, когда там по смыслу коэффициенты от 1 до 26 натуральные числа. но на самом деле если и будет коллизия что страшного? положим в цепочку

@vitkarpov Вообще есть смысл разбирать все базовыве алгоритмы сортировки и имплементировать их

Ну опять же, зависит от того сколько у тебя времени. Если условно бесконечно много, т.е. собес ещё не назначен — можно и копать.

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

потом выступишь на какой-нибудь конференции с докладом а-ля «нахера я заимплементил все сортировки и что понял из сравнения их работы»

Вероятнее всего меня не пригласят ни на какую конфеиенцию

Happy Monday! 👋 Продолжаем решать задачи на динамическое программирование, на этой неделе разбираем двумерную дпшечку. https://vitkarpov.me/posts/number-of-dice-rolls-with-target-sum/

Доброе утро, ребята!

Доброе утро, ребята!

Тут Эдинбург спит еще спит, а Москва бодровствует

Решил через Map, какое то наверное неполноценное ДП получилось: https://pastebin.com/VUmTzuny

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

Решил через Map, какое то наверное неполноценное ДП получилось: https://pastebin.com/VUmTzuny

Доброе утро, ребята!

Сергей, расскажи что такое и как стать Google Certified Mobile Web Specialist 🙂

Виктор, для начала спасибо за видеокурс по алгоритмам, оттуда я сюда и попал. Хочу так же ясно и понятно излагать свои мысли по ходу написания кода. Очень полезный скилл. По поводу сертификации, коротко уже никак, гугл ее закрыл. В целом обо всем по чуть-чуть в мире веб разработки. Создавали сертификацию в рамках популяризации PWA (progressive web apps), когда веб-сайт, как приложение можно добавить на рабочий стол, добавить сплэш скрин, убрать контролы браузера, работа в офф-лайн через кэширование в сервисворкерах. Пуш нотификации и ещё много всяких API добавлено в андройды и хром в основном. Так же были задачи на производительность (например, убрать сложные вычисления в web worker), accessibility, оптимальное использование изображений в веб (тэг picture, webp и тд) и много разного на общий кругозор. Что это дало? Коротко - ничего, кроме новых знаний (это хорошо) и рекрутеры немного чаще пишут из-за слова Google. И ты если честно первый, кто вообще поинтересовался что это)

Виктор, для начала спасибо за видеокурс по алгоритмам, оттуда я сюда и попал. Хочу так же ясно и понятно излагать свои мысли по ходу написания кода. Очень полезный скилл. По поводу сертификации, коротко уже никак, гугл ее закрыл. В целом обо всем по чуть-чуть в мире веб разработки. Создавали сертификацию в рамках популяризации PWA (progressive web apps), когда веб-сайт, как приложение можно добавить на рабочий стол, добавить сплэш скрин, убрать контролы браузера, работа в офф-лайн через кэширование в сервисворкерах. Пуш нотификации и ещё много всяких API добавлено в андройды и хром в основном. Так же были задачи на производительность (например, убрать сложные вычисления в web worker), accessibility, оптимальное использование изображений в веб (тэг picture, webp и тд) и много разного на общий кругозор. Что это дало? Коротко - ничего, кроме новых знаний (это хорошо) и рекрутеры немного чаще пишут из-за слова Google. И ты если честно первый, кто вообще поинтересовался что это)

Ха, крутяк! Слово гугл в «о себе» не помешает 😄

Какой год то везучий