Телеграмм чат группы proalgorithms страница 3148

2020 March 11

DK

unsigned answ(0);
for (int bit = 31; bit >= 0; bit--) {
if (curr->left->count() < (1u << bit)) {
curr = curr->left;
} else {
answ |= (1u << bit);
curr = curr->right;
}
}

источник

12:11пожаловаться #1

DK

Dmitry Kozyrev in pro.algorithms

Аккуратно обработать случай nullptr слева и справа

источник

12:12пожаловаться #2

DK

Dmitry Kozyrev in pro.algorithms

count надо хранить - количество уникальных листьев и пересчитывать

источник

12:12пожаловаться #3

АГ

Александр Горнак in pro.algorithms

Мне кажется это некорректный алгоритм или я его не понимаю, например в левом поддереве числа 2, 4, 5
В правом тройка, тогда мы должны идти вправо и мекс будет 6, но мы пойдём влево и придём в 8, так как 3<(1<<31)

источник

12:18пожаловаться #4

KK

Kirill Kaymakov in pro.algorithms

Александр Горнак

Мне кажется это некорректный алгоритм или я его не понимаю, например в левом поддереве числа 2, 4, 5
В правом тройка, тогда мы должны идти вправо и мекс будет 6, но мы пойдём влево и придём в 8, так как 3<(1<<31)

С какого? мех будет 0

источник

12:25пожаловаться #5

АГ

Александр Горнак in pro.algorithms

Я предполагаю что 0 и 1 нам уже не подошли

источник

12:26пожаловаться #6

KK

Kirill Kaymakov in pro.algorithms

Mex мультимножества чисел это минимальное неотрицательное целое число, не входящее в множество.

источник

12:26пожаловаться #7

KK

Kirill Kaymakov in pro.algorithms

Ты, в общем, кажись не понимаешь, что мех это не максимальное число + 1)

источник

12:27пожаловаться #8

DK

Dmitry Kozyrev in pro.algorithms

Александр Горнак

Мне кажется это некорректный алгоритм или я его не понимаю, например в левом поддереве числа 2, 4, 5
В правом тройка, тогда мы должны идти вправо и мекс будет 6, но мы пойдём влево и придём в 8, так как 3<(1<<31)

Можете дать конкретный пример из чисел, которые хранятся во всем дереве, и запрос, который работает неправильно? Я обьясню на примере

источник

12:27пожаловаться #9

АГ

Александр Горнак in pro.algorithms