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

Основные операции побитового сдвига

Левый сдвиг (<<)

Каждый бит числа сдвигается влево на заданное количество позиций.

Пример

1010 << 1 = 10100

Эта операция эквивалентна умножению числа на 2 для каждого сдвига.

Правый сдвиг (>>)

Каждый бит числа сдвигается вправо на заданное количество позиций.

Пример

1010 >> 1 = 0101 = 101

Эта операция эквивалентна делению числа на 2 для каждого сдвига.

---------

Примеры использования:

- Быстрое умножение и деление:
- Маскирование битов
- Шифрование и сжатие данных:

Использование побитовых сдвигов может значительно ускорить выполнение операций, особенно в задачах, требующих работы с низкоуровневыми данными. Это важный инструмент в арсенале любого программиста, стремящегося к написанию эффективного кода.

Наименования битов

Когда мы говорим о задачах, связанных с битовыми манипуляциями, мы можем встретить несколько важных терминов, которые будет крайне полезно знать. Давайте познакомимся с самыми важными.

1. Старший бит (Most Significant Bit, MSB)

Это бит, который имеет наибольший вес в двоичном числе и находится в крайней левой позиции.
Например, в числе 1000 (в двоичной системе) старший бит равен 1.

2. Младший бит (Least Significant Bit, LSB)

Это бит, который имеет наименьший вес в двоичном числе и находится в крайней правой позиции.
Например, в числе 1000 (в двоичной системе) младший бит равен 0.

3. Средние биты (Intermediate Bits)

Это биты, находящиеся между старшим и младшим битами, которые также могут влиять на значение числа.

4. Установленный бит

Это бит, значение которого равно 1 в двоичном представлении числа.

5. Значимый бит

Значимые биты — это биты, которые существенно влияют на значение числа. Обычно это все биты, начиная с первого установленного бита до младшего бита.
Например, в числе 0010110 (в двоичной системе) значимые биты — 10110.

6. Последний установленный бит (Last Set Bit)

Это самый правый бит, который имеет значение 1 в двоичном представлении числа. Этот бит также иногда называют младшим установленным битом.

Вес Хэмминга

Возможно вы уже слышали такое определение, а может быть и нет, но я совершенно точно уверен, что вы знаете его значение ?

Вес Хэмминга (Hamming weight) также известный как популяционное число (population count), представляет собой количество единичных (установленных) битов в двоичном представлении числа.
Формально, для числа ? вес Хэмминга определяется как сумма всех битов числа ? в его двоичной форме.

Примеры

1️⃣ Число 5

- Двоичное представление: 101
- Вес Хэмминга: 2 (два бита установлены в 1)

2️⃣ Число 13

- Двоичное представление: 1101
- Вес Хэмминга: 3 (три бита установлены в 1)

Это предельно простое определение является крайне важным так как Вес Хэмминга используется для различных задач в информатике. Вот только некоторые примеры:

— Теория кодирования. В кодах с обнаружением ошибок и исправлением ошибок вес Хэмминга может использоваться для измерения расстояния Хэмминга между двумя кодовыми словами, что позволяет определять количество ошибок.

— Криптография. В криптографических алгоритмах вес Хэмминга может использоваться для оценки случайности и сложности ключей.

— Обработка сигналов. Вес Хэмминга может применяться для анализа и фильтрации сигналов, а также для оценки шума.

Привет. Сегодня я бы хотел обсудить с вами один интересный вопрос, который не касается алгоритмов, но напрямую относится к работе.

Наткнулся в интернетах на жаркий тред, где обсуждают нормально ли писать сообщения по работе в нерабочее время.

В чем суть. Есть условно два стула.

1. Одни считают, что писать нормально в любое момент. Человек с передающей стороны может написать сообщение в удобное ему время. Человек же с принимающей стороны сам может выстроить свой режим и окружение таким образом, чтобы получать уведомления и отвечать на них только в рабочее время. То есть ответственность за обеспечение своего удобства и комфорта на принимающей стороне.

2. Другие считают, что писать можно исключительно в рабочее время, то есть ответственность на передающей стороне. Человек, который отправляет сообщения должен либо пользоваться отложенной отправкой, либо ставить себе напоминалки чтобы написать строго в рабочее время. Сообщения в нерабочее время считаются нарушением личных границ.

Расскажите, что вы думаете по этому поводу? Какой вариант для вас более предпочтительный? Или может у вас есть другие идеи?

Сколько нужно стрел, чтобы лопнуть все воздушные шары

Сложность: ? Средняя

ℹ️ Описание

К плоской стене, представляющей плоскость XY, приклеено несколько сферических воздушных шаров. Шары представлены в виде двумерного целочисленного массива points, где points[i] = [xstart, xend] обозначает шар, горизонтальный диаметр которой простирается между xstart и xend. Вы не знаете точных координат Y воздушных шаров.

Вы можете выстрелить стрелой прямо вертикально (в положительном направлении Y) из разных точек вдоль оси X. Воздушный шар с xstart, xend разрывается стрелой, выпущенной в x, если x start <= x <= xend. Нет ограничений на количество выпущенных стрел.

Выпущенная стрела продолжает двигаться вверх бесконечно, разрывая все воздушные шары на своем пути. Найдите минимальное количество стрел, которое необходимо выпустить, чтобы лопнуть все воздушные шары.

⚠️ Ограничения

— В массиве points может быть от 1 до 105 элементов
— 2^31 <= xstart < xend <= 2^31 - 1

*1️⃣* Пример

Входные данные**

points = [[10,16],[2,8],[1,6],[7,12]]
Ответ: 2

Пояснение

— Выстрелите стрелой в точку x = 6, лопнув шарики [2, 8] и [1, 6].
— Выстрелите стрелой в точку x = 11, лопнув шарики [10, 16] и [7, 12].

2️⃣ Прим**ер

Входные данные**

points = [[1,2],[3,4],[5,6],[7,8]]
Ответ: 4

Пояснение

Для каждого воздушного шара нужно выпустить одну стрелу, всего получится 4 стрелы.

3️⃣ Прим**ер

Входные данные**

points = [[1,2],[2,3],[3,4],[4,5]]
Ответ: 2

Пояснение

— Выстрелите стрелой в точку x = 2, лопнув шарики [1, 2] и [2, 3].
— Выстрелите стрелой в точку x = 4, лопнув шарики [3, 4] и [4, 5].

✅ Решение

Для решения этой задачи первым делом надо отсортировать массив points по правой границе шаров. Такая сортировка поможет нам с легкостью определить, сколько стрел нужно выпустить, чтобы лопнуть все шары.

Если шары отсортированы по конечной координате, то мы знаем, что у следующего шара есть всего два варианта положения.

— Его начальная координата больше конечной координаты текущего шара. В таком случае эти шары не пересекаются и их нельзя сбить одной стрелой.
— Его начальная координата меньше или равна конечной координате текущего шара. В таком случае эти шары пересекаются и их можно сбить одной стрелой, если выстрелить в конечную координату текущего шара.

Исходя из этого мы можем сформировать крайне простой алгоритм:

— Итерируемся по всем шарам в отсортированном массиве.
— Запоминаем координату последнего выстрела, которую по умолчанию выставляем в минимально возможное значение.
— Если начальная координата текущего шара больше координаты последнего выстрела, то это означает, что нам нужен сделать выстрел по правой границе шара и увеличить счетчик выпущенных стрел на 1.
— Если начальная координата текущего шара меньше или равна координате последнего выстрела, то это означает, что шар пересекается с предыдущим и нам не нужно делать новый выстрел, потому что он уже был сбит предыдущей стрелой.

Посмотреть реализацию в блоге

#arrays#medium

Сжатие строки

Как и обещали, возвращаемся к вам с отпуска с новыми силами. Сегодня хочется разобрать одну из очень популярных и классических задач с собеседований - пишем свой простенький архиватор ?

Сложность: ? Средняя

ℹ️ Описание

Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив и вернет количество символов в сжатом массиве по следующему принципу:
— Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['a', 'n'], где a - исходный символ, n - количество повторений этого символа, идущих подряд. В случае если n — многозначное число, каждая цифра должна быть добавлена отдельным символом.
— Если буква не повторяется - оставить ее без изменений.

Все изменения нужно совершить in-place, в качестве ответа функции вернуть количество символов в сжатой строке.

⚠️ Ограничения

— Длина входящего массива от 1 до 2000 символов
— Элементы массива - символы латиницы, цифры или знаки

*1️⃣* Пример

Входные данные**

```

chars = ["a","a","b","b","c","c","c"]

```

Ответ

```

6

```

Исходный массив должен быть преобразован в

```

chars = ["a","2","b","2","c","3"]

```

2️⃣ Прим**ер

Входные данные**

```

chars = ["a"]

```

Ответ

```

1

```

3️⃣ Пример
Входные данные

```

chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

```

Ответ

```

4

```

Исходный массив должен быть преобразован в

```

chars = ["a","b","1","2"]

```

✅ Решение

Задача решается достаточно элементарно, главная загвоздка - замена элементов in-place.

Для решение задачи нам понадобятся несколько индексов:
— Индекс текущего элемента lastElemIdx
— Индекс начала последовательности одинаковых элементов firstElemIdx
— Индекс элемента, который будет заменен при сжатии строки newPositionIdx. Для эффективности решения мы будем заменять элементы исходного массива, а после «отрежем» хвост. В противном случае нам бы пришлось вырезать повторяющиеся символы, смещая хвост массива на n элементов влево, что значительно замедлит алгоритм.

Далее нам достаточно аккуратно обойти и модифицировать исходный массив.

Посмотреть реализацию в блоге

#arrays#medium

`` console.log(
__
_ / /|
|\ \/_/
\_\| / __
\/_/__\ .-=='/~\
____,__/__,_____,______)/ /{~}}}
-,------,----,-----,---,\'-' {{~}}
jgs '-==.}/
`)

```

Сегодня не будет задач!

Cегодня мы поздравляем всех наших подписчиц с прекрасным женским днем.
Будьте красивыми, счастливыми и прокаченными в алгоритмах!

С праздником! ?

Максимальный зигзагообразный путь в бинарном дереве
Продолжаем закреплять тему деревьев. В общем виде, если вы встречаете задачу на деревья или графы, с большой долей вероятности стоит вспоминать и модифицировать поиск в ширину/глубину.

Сложность: ? Средняя

ℹ️ Описание

Напишите функцию, которая будет вычислять длину самого длинного зигзагообразного пути в бинарном дереве. Путь может начинаться НЕ с корневого элемента дерева.

⚠️ Ограничения

Количество элементов в дереве от 1 до 50000

✅ Решение

Для решение задачи нам потребуется вспомнить как работает алгоритм поиска в глубину и немного модифицировать его. Основная сложность данной задачи в том, что наш путь не обязан начинаться от корня дерева, он может «всплывать» из более глубоких слоев дерева, поэтому на каждой ноде нам нужно оперировать четырьмя величинами:

- Длиной пути, начинающегося от текущего элемента направо.
- Длиной пути, начинающегося от текущего элемента налево.
- Длиной максимального пути «снизу» с левой дочерней ноды.
- Длиной максимального пути «снизу» с правой дочерней ноды.

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

Посмотреть примеры и реализацию в блоге

?️ Оценка сложно**сти

По времениO(n) —так как нам нужно совершить поиск в глубину по бинарному дереву, перебрав все n его элементов.
По памяти**

O(n) — так как мы используем рекурсивный подход. Это означает, что мы будем хранить в памяти n переменных во время вычисления стека рекурсии.

#tries#medium

Угадай число

Сегодня мы рассмотрим вместе с вами еще одну классическую задачу из учебников.

Сложность: ? Легкая

ℹ️ Описание

Мы играем в игру, где вы должны угадать загаданное число.
Игра заключается в следующем.

— Я выбираю число от 1 до n.
— Вы должны угадать, какое число я выбрал.
— Каждый раз, когда вы угадаете неправильно, я скажу вам, больше или меньше выбранное мной число, чем ваше предположение.

Вы можете использовать предоставленный метод guess для проверки догадки со следующей сигнатурой.

int guess(int num)

Метод возвращает следующие результаты:

— -1 если ваша догадка больше, чем выбранное мной число;
— 1 если ваша догадка меньше выбранного мной числа;
— 0 если ваша догадка равна выбранному мною числу.

Угадайте число, которое я загадал.

⚠️ Ограничения

Загадываемое число всегда находится в диапазоне от 1 до 2^31 - 1

1️⃣ Пример

Исходные данные: n = 10, загадано число 6 Ответ: 6

2️⃣ Пример

Исходные данные: n = 1, загадано число 1 Ответ: 1

3️⃣ Пример

Исходные данные: n = 2, загадано число 1

Ответ: 1

✅ Решение

Это классическая задача, которая решается при помощи бинарного поиска.

Нам нужно итеративно выполнять несколько шагов.

1. Найти крайнюю левую и правую границы интервала, то есть 1 и n соответственно.
2. Найти середину этого интервала и проверить полученное число:
   — если полученное число больше загаданного, то правую границу нужно сместить на mid - 1;
   — если полученное число меньше загаданного, то левую границу нужно сместить на mid + 1;
   — если полученное число равно загаданному, то мы нашли ответ.

Этот алгоритм нужно повторять до тех пор, пока мы не найдем ответ или пока левая и правая границы не пересекутся.

Посмотреть реализацию в блоге

?️ Оценка сложно**сти

По времени

O(log n) так как мы перебираем диапазон чисел бинарным поиском.
По памяти**

0(1) так как мы не выделяем дополнительной памяти.

#binary_search

Непересекающиеся интервалы

В эту пятницу у нас с вами очередная задача. Приготовьтесь, объяснение ее решения не самое простое.

Сложность: ? Средняя

ℹ️ Описание

Дан массив интервалов intervals, где intervals[i] = [start, end]. Напишите функцию, которая возвращает минимальное количество интервалов, которое вам нужно удалить, чтобы остальные интервалы не пересекались.

⚠️ Ограничения

— Длина массива находится в диапазоне от 1 до 10^5
— Каждый элемент массива также является массивом из двух элементов
— Значения границ интервалов находятся в диапазоне от -5 * 10^4 до 5 * 10^4
— Нижняя граница интервала всегда меньше верхней

1️⃣ Пример

Входящие данные

```

[[1,2],[2,3],[3,4],[1,3]]

```

Ответ

```

1

```

2️⃣ Пример

Входящие данные

```

[[1,2],[1,2],[1,2]]

```

Ответ

```

2

```

3️⃣ Пример

Входящие данные

```

[[1,2],[2,3]]

```

Ответ

```

0

```

✅ Решение

Рассмотрим два интервала с самым ранним временем окончания. Допустим, более раннее время окончания — x, а более позднее — y, то есть х < у.

Если мы можем сохранить только один интервал, следует ли нам выбрать тот, который заканчивается на «x» или тот, который оканчивается на «y»? Чтобы избежать дублирования, мы всегда должны жадно выбирать интервал с более ранним временем окончания «x». Логику, стоящую за этим, можно описать следующим образом:

— Мы выбираем либо x, либо y. Назовем наш выбор k.
— Чтобы избежать пересечения, время начала следующего интервала, который мы выбираем, должно быть больше или равно k.
— Мы хотим максимизировать интервалы, которые мы используем (без пересечения), поэтому мы хотим максимизировать выбор для следующего интервала.
— Поскольку время начала следующего интервала должно быть больше или равно k, большее значение k никогда не сможет дать нам больше выбора, чем меньшее значение k.
— Таким образом, мы должны попытаться минимизировать k. Следовательно, нам всегда следует жадно выбирать x, поскольку x < y.

В общем, k равно времени окончания самого последнего сохраненного нами интервала.

Решение задачи мы начинаем с сортировки интервалов по времени окончания, чтобы мы могли обрабатывать их по порядку.
Поскольку мы отсортировали интервалы по времени окончания, «y» должно быть больше «k». Это дает нам два возможных варианта:

— Вариант 1, x >= k: мы можем смело использовать этот интервал, поскольку он не приведет к пересечению.
— Вариант 2, x < k: использование этого интервала приведет к пересечению. Как мы установили ранее, нам всегда следует брать интервалы с более ранним временем окончания. Поскольку y > k, мы должны удалить текущий интервал.

Посмотреть реализацию в блоге

?️ Оценка сложно**сти

По времени**
Для того чтобы найти ответ, нам достаточно один раз пройтись по исходному массиву со сложностью O(n). Однако предварительно мы еще делаем сортировку массива, сложность которой скорее всего равна O(n⋅logn).

Поэтому итоговая сложность по времени равна O(n⋅logn).

По памяти

Мы не создаем переменных, зависящих от длины входных данных, однако для сортировки также требуется выделение памяти. В разных языках используются разные алгоритмы, поэтому сложность по памяти будет варьироваться от O(logn) до O(n).

#arrays #medium