Evgeniy
Интересно, написано, что в среднем константа, а в худшем линейная
Порридж В Ко-ливинге
Я знаю
Порридж В Ко-ливинге
Но это бред
Evgeniy
Почему?
Evgeniy
перебрать же надо всё
Порридж В Ко-ливинге
Так можно сказать что любая hash функция линейная
Evgeniy
там нет хэша
Evgeniy
в неупорядоченном
Evgeniy
ну я так понимаю
Evgeniy
а в обычном set есть
Evgeniy
Возможно ошибаюсь
Evgeniy
Хотя нет, в обычном просто дерево
Порридж В Ко-ливинге
В обычном точно нет
Порридж В Ко-ливинге
Т.к. откуда у хэша log N
Evgeniy
дерево
Evgeniy
а хэш за константу вычисляется
Evgeniy
хеш у нас в мепах
Evgeniy
Однако там те же самые характеристики у функций
Evgeniy
Похоже там вообще нет хешей
Evgeniy
Нигде
Evgeniy
Complexity
Logarithmic in the size of the container.
Evgeniy
https://en.cppreference.com/w/cpp/container/map/contains
Evgeniy
Теперь мне стало интересно, какие контейнеры в c++ работают с хэшами?
Evgeniy
Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity).
Evgeniy
Понятно
Evgeniy
Худший случай всё сбивает
Viktor
Порридж В Ко-ливинге
https://en.cppreference.com/w/cpp/container/unordered_set
Viktor
соотвественно одни под капотом — деревья, другие — хэш-таблицы
Порридж В Ко-ливинге
Порридж В Ко-ливинге
У дерева не может быть лимита
Evgeniy
Порридж В Ко-ливинге
А у Hash может быть колизии
Evgeniy
Порридж В Ко-ливинге
Поэтому O(N) может быть
Порридж В Ко-ливинге
Но в это считать – берд
Evgeniy
Ну вот, всё понятно теперь
Порридж В Ко-ливинге
Т.к. тогда вообще 90% всех O(N) становятся O(N^2)
Viktor
Сегодняшняя задачка просто огонь. Я час тупил в бинарные представления чисел чтобы увидеть паттерн наконец.
Evgeniy
Evgeniy
Указано, что она на дп
Порридж В Ко-ливинге
Ой, не пугайте меня
Порридж В Ко-ливинге
Я от сегодняшней еле отошел
Порридж В Ко-ливинге
🤣
Evgeniy
Я ещё не делал
Viktor
ДПшечка, да.
Evgeniy
Viktor
там просто рекурсивное соотношение очень простое и очень круто объясняется по смыслу (по крайней мере я себе его так объяснил)
Viktor
так что удивительно, что я сразу не заметил это
Viktor
а только после тупления
Evgeniy
Ну в числе столько единиц, из скольких степеней двоек оно состоит
Evgeniy
А вот связать с предыдущим числом, надо подумать
Evgeniy
Наверное тоже стоит расписать ответы в строку
Evgeniy
С уважением к дп)
Evgeniy
Уловил связь, надо теперь реализовать
Viktor
а смог эту связь человеческим языком объяснить?
Viktor
ну можно потом, чтобы не спойлерить.
Evgeniy
Сложновато)
Evgeniy
4 строки
Evgeniy
где-то перебрал)
Evgeniy
Даже 5
Evgeniy
https://leetcode.com/problems/counting-bits/discuss/656728/S-O(n)-DP-solution-using-bitwise-operations
Evgeniy
Думаю тут можно упростить как-то
Evgeniy
Но работает
Evgeniy
Любопытно. А какая идея за этим?
Когда начинаем перебирать числа, идущие вслед за очередной степенью двойки то количество единиц в них больше на 1, чем число единиц у этого числа минус то самое число, являющееся степень двойки, которую мы только что прошли.
Evgeniy
Сложновато объяснил
Evgeniy
Но вообще люди там предлагают решение проще
Viktor
Да, нормальная тема. Моя идея была в том, что у всех четных чисел количество единиц то же, что и у чисел вдвое меньше, ну потому что умножение на 2 это сдвиг одного бита и все единички сдвинутся, но количество то же будет. А если нечетное, то можно отступить на шаг назад и станет четным, ну и плюс один, потому что если число стало нечётным с четного, то последний нолик сменился на 1
Viktor
Это я понял благодаря последней подсказке когда тупил кучу времени уже на числами разными.
Evgeniy
Evgeniy
Но я не смотрел подсказки
Evgeniy
Evgeniy
с помодоро