Dailик. Побеждать себя. Побеждать алгоритм.
Читаю задание. Китайская грамота. Ничего не понятно.
I. Есть набор чисел на входы
Есть bitwise OR - т.е. побитовое или. 1 | 2 = 3;
0001
0010
----
0011
II. Есть subset
Подмножество. Подмножества? Нет. О. Чего? nums a. Какие у него есть подмножества? Набор чисел?
По какому признаку? Все уникальные? Сделать из них группы? Вернуть их? Или какой-то результат?
return: кол-во разных не нулевых подмножеств. У которых... Которые делаем по признаку...
"У тебя максимальное число(больше всех) битовых операций ИЛИ!"
Что? Ты что-нибудь понял?
У этой задачи примерно 80% рейтинг приёмов. Плачу. Т.е. достаточно лёгкая...
Подмножество - это что получили из nums удаляя(а может и нет!) элементы.
А разные подмножества - когда каждый отличается от другого... чем-то?... (C) Кэп
⏳ ...спустя время...Hint 1, 2. Нет. Они не помогают, когда не понял условие задачи. Есть мастера bitwise OR?
Просто же! 84% acceptance.
🕐 ...прошло пару часов...
Какая комбинация из чисел при их операции OR друг с другом даст максимально возможное число.
А?! КакогО?!
🕘 ...настал вечер. Работа. Садик. Тех. Конференция. Созвон. И вот Ya back again.
21:05. Погнали.
То есть, мне нужно попробовать каждый с каждым, да ещё и в разных комбинациях. Хотя, порядок не важен:
3 2 1 5
3 2
3 2 1
3 2 1 5
....
2 3 <---уже была
2 1
2 5
2 1 5
2 3 5
....
1 3
1 2 <---уже была
1 5
....
Эм... да здесь кол-во перестановок. Задача на них.
🧠 Хотя, нет. Стоит ли решать под вечер с не варящим котелком? Гоу ниткод? Блин, был близок...
Ещё попытка.
Перебираю все возможные комбинации. Без разницы какие числа где стоят относительно друг друга. Нужны лишь уникальные комбинации по самим неповторяющимся числам.
У каждого числа есть индекс. Так, чтобы одно число с этим же индексом в этом наборе не присутствовало.
0 1 2 3 4
5 2 9 9 3
5 5 <--нельзя, т.к. у обоих индекс 0
9 9 <--ок, это разные 9ки
III. Получить все комбинации...
Допустим получил. Пройдусь по ним, находя такую, которая даёт макс результат при применение ко всем числам в этой комбинации побитового ИЛИ.
Пускай текущий пока максимальный. Его добавляю во временный результат из списка таких комбинаций.
Если нашёл более максимальный, сбрасываю временный результат, добавляю текущую комбинацию(сет).
// это больше для меня, или тебе также полезен такой формат поста-рассуждения?
Ок. Сводим к простой(наверное) подзадачи по получению комбинаций.
Рекурсия? Dynamic programming? С каждого текущего места может пойти в следующее. Или через следующее.
IV. Наблюдение
Явно само подмножество, которое состоит из всех элементов и будет макс. Кстати да. Вот отправная точка.
Могут ли меньше элементов дать такой же результат? Да! В силу специфики bitwise OR. Какие-то единички просто друг друга перетерают. Ну, не мешают.
Но такое число - молодец. Рождает новую комбинацию.
К примеру дали [5, 1]:
5ка - 0101
1ца - 0001
Их комбинация:
5 | 1 - 0101 = 5
Ну как бы ничего плохого не стало от единицы. От 5ки уже там бит стоял. Зато добавилась новая комбинация в ответ:
{5}
{5, 1}
V. Код
Ну это всё лирика. Show me your code. Again. And I tell you who you are.
Сделал решение. Пока не всё проходит.
2 2 2. 7 комбинаций. У меня меньше.
Все напишем:
2
2 2
2 2 2
2 2
VI. Конец
😢 Всё, здесь я закончился. Один цикл с рекурсией внутри по всем. А зачем она?... Просто бы итерировался.
Надо начинать каждый раз со следующего числа. Первая комбинация - оно само. Остальные - комбо из оставшихся чисел, где его же может и не быть))
2
2 2
2
Вот они. Все 7 комбинаций. Ок.
Ок. 2/3 test case.
Ок. Отладка. Ещё время... Не нахожу что не так...
Ок. Слишком долго. Смотрю solution.
Вывод
Был близок. Как это можно решить за 0.5 часа?
У меня заняло утром 17 минут и сейчас 1.5 часа.
Говорят, что если 0.5 часа не получается, надо смотреть. Ну тут азарт. Я думаю, нормально. Можно и поспать.