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

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

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

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

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

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

Стек наиболее часто встречающихся элементов

Всем привет!
Мы решили попробовать разбавить легкие и средние задачи — сложными 🙂
На самом деле эта задача лежала у меня в черновиках довольно долго. Настолько, что я успел несколько раз забыть как работает куча, а также за это время мы успели завести этот канал и несколько раз обновить блог (кстати, зацените новый формат. Кажется, стало немного симпатичнее).

Итак, задача по реализации модифицированного стека: который позволяет сперва доставать наиболее частотные элементы, а в случае наличия групп элементов с одинаковой частотой - работать как классический стек между этими группами.
На самом деле, наиболее приближенная задача из практических — Priority queue. Только в нашем случае вместо приоритетов — частоты, а вместо алгоритма FIFO - LIFO.

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

Сложность: 🤬 Сложная

ℹ️ Описание

Необходимо реализовать структуру данных, которая позволит сохранять и доставать целочисленные элементы. Для этого необходимо реализовать 3 функции:
1. Constructor() FreqStack конструктор, инициализирующий структуры данных.
2. FreqStack.Push(val int) метод структуры данных, позволяющий сохранить целочисленный элемент внутрь структуры данных FreqStack
3. FreqStack.Pop() int метод структуры данных, удаляющий и возвращающий элемент из структуры данных. Сперва извлекаются наиболее частотные элементы. При наличии групп эллементов, имеющих одинаковую частоту, извлекать элементы из групп с одинаковой частотой по принципу стека (LIFO)

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

— Добавляемые/извлекаемые элементы лежат в диапазоне от 0 до 1 000 000 000
— Максимальное количество вызовов функций Push и Pop - 20 000
— Гарантируется, что перед вызовом функции Pop в FreqStack будет как минимум один элемент

1️⃣ Пример

stack := Constructor()

stack.Push(5)
stack.Push(7)
stack.Push(5)
stack.Push(7)
stack.Push(4)
stack.Push(5)

Out:

stack.Pop() // 5
stack.Pop() // 7
stack.Pop() // 5
stack.Pop() // 4

Пояснение

— Первым извлекается элемент 5, так как он самый частотный в стеке. При этом извлекается та 5, которая была добавлена последней (по принципу стека)
— Вторым извлекается элемент 7, так как в стеке оба элемента 5 и 7 встречаются по 2 раза, но последняя 7 была добавлена позже, чем последняя 5 (5, которую мы добавили последним Push'ом мы извлекли первым вызовом Pop)
— Третьим элементом извлекается элемент 5, так как теперь это самый частотный элемент в стеке
— Четвертым извлекается элемент 4, так как теперь в стеке все элементы имеют одинаковую частоту (каждый элемент встречается один раз), а элемент 4 был добавлен в стек последним


✅ Решение

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

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

#heap #hard

Минимальное количество переворотов, чтобы сделать A | B == C

Привет, друзья.

Несмотря на выходный день, у нас вами разбор новой задачи. В этот раз рассматриваем тему битовых манипуляций.

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

ℹ️ Описание

Даны три целых положительных числа a, b и c.

Необходимо найти минимальное количество переворотов битов в a и b, чтобы результат операции a OR b (побитовая операция ИЛИ) был равен c. Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или c 0 на 1 в его двоичном представлении.

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

Значение каждого аргумента находится в диапазоне от 1 до 10^9

1️⃣ Пример

Входные данные: a = 2, b = 6, c = 5

Ответ: 3

2️⃣ Пример

Входные данные: a = 4, b = 2, c = 7

Ответ: 1

3️⃣ Пример

Входные данные: a = 1, b = 2, c = 3

Ответ: 0

✅ Решение

Чтобы решить задачу, нам необходимо представить числа a, b и c в двоичном виде и произвести их сравнение побитно. Недостающие биты в числах мы заполняем ведущими нулями.

Если бит числа c равен 1, это означает, что в a и b как минимум один бит на этой же позиции должен быть равен 1, чтобы условие a | b == c было истинным. Если же оба бита в a и b равны 0, то нам необходимо изменить любой из битов на единицу. Не важно какой именно бит, потому что это не меняет результат.

Если бит числа c равен 0, это означает, что биты и в числе a, и в числе b должны быть равны нулю, чтобы условие a | b == c было истинным. В этом случае нам нужно изменять биты в a и b только в том случае, если они равны 1.

❓ Как получить двоичное представление числа ❓

На самом деле число не нужно переводить в двоичную систему счисления. Достаточно воспользоваться небольшим математическим хаком.

- Чтобы получить младший бит числа в двоичном представлении (крайний справа) необходимо взять остаток от деления числа на 2. Это работает потому что у четных чисел младший бит всегда равен 0, а у нечетных — 1.

- Чтобы откинуть младший бит у числа достаточно разделить его на 2 без остатка. В таком случае мы получим новое число, которое в двоичном представлении равно предыдущему числу без младшего бита.

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

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

#bit_manipulation #medium

Вижу, многие не знают о том, что у нас есть блог.

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

Пары одинаковых строк и колонок

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

ℹ️ Описание

Дана матрица grid размером n x n, которая состоит из целых положительных чисел.

Посчитайте количество пар (r[i], c[j]), где строка r[i] равна колонке c[j]

Строка и колонка считаются равными, если они состоят из одинаковых элементов в одинаковом порядке.

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

— Размер n находится в диапазоне от 1 до 200
— Значение каждого элемента в матрице находится в диапазоне от 1 до 10^5

1️⃣ Пример

Входные данные: grid = [[3,2,1],[1,7,6],[2,7,7]]

Ответ: 1

Есть одна одинаковая пара:
— (Строка 2, Колонка 1): [2,7,7]

2️⃣ Пример

Входные данные: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]

Ответ: 3

Есть три одинаковые пары:
— (Строка 0, Колонка 0): [3,1,2,2]
— (Строка 2, Колонка 2): [2,4,2,2]
— (Строка 3, Колонка 2): [2,4,2,2]

✅ Решение

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

Создаем карту подсчета строк:

Инициализируем пустую хеш-таблицу (объект в случае TypeScript) countMap, который будет хранить строки в виде ключей и их количество в виде значений.
Проходим по каждой строке матрицы. Для каждой строки создаем строковой ключ, конкатенируя все её элементы, разделенные точкой с запятой.
Если такой ключ уже существует в countMap, увеличиваем значение на единицу. В противном случае, устанавливаем значение равным единице.
Подсчет совпадающих столбцов:

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

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

#matrix #hash_table #medium

Максимальная глубина бинарного дерева

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

ℹ️ Описание

Найдите максимальную глубину бинарного дерева.

Максимальная глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

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

— Количество узлов в дереве может быть от 0 до 10000
— Значение каждого узла находится в диапазоне от -100 до 100

✅ Решение

Для решения задачи нам достаточно реализовать простой поиск в глубину DFS (Depth First Search).

Реализуем дополнительную рекурсивную функцию dfs, которая принимает на вход два аргумента:
— текущий узел дерева node
— текущую глубину погружения level

В качестве ответа функция будет возвращать максимальную глубину ветки дерева.

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

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

В самом конце нам остается вызвать из основной функции maxDepth наш dfs поиск, определив начальную глубину равную 0.

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

#tree #binary_tree #easy

Листоподобные деревья

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

ℹ️ Описание

Дано два бинарных дерева. Все листовые узлы дерева образуют последовательность значений.
Например, для дерева на картинке последовательность значений будет равна (6, 7, 4, 9, 8).

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

Напишите функцию, которая возвращает true тогда и только тогда, когда два заданных дерева являются листоподобными.

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

— Количество узлов в каждом дереве находится в диапазоне [1, 200]
— Узлы обоих деревьев имеют значения в диапазоне [0, 200]

✅ Решение

Для решения задачи нам необходимо собрать последовательность всех листовых узлов в обоих деревьях и сравнить их.

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

Функция осуществляет классический обход дерева в глубину DFS (Depth First Search) и когда встречает листовой узел (узел, у которого нет потомков), то добавляет его значение в строку sequence, разделяя значения точкой с запятой. Предварительно мы определяем переменную sequence, равную пустой строке, и управляем ее значением через замыкание.

Вместо строки можно было бы использовать массивы, но после вычисления массивом их пришлось бы сравнивать итерируясь по всем элементам, что дало бы дополнительных k операций. Строки же можно просто сравнить между самой через ==.

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

#tree #binary_tree #easy

Всем привет!

У меня есть небольшое хобби - я люблю коллекционировать профессиональную литературу. Громко сказано, на пара полок с Таненбаумом, «Философией Java» и прочими томами служили украшением моего домашнего рабочего места, пока я не перешел на кочевой образ жизни 🙂 Правда, если быть честным, большинство книг я прочел едва ли наполовину, но все же 🙂

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

Начну с себя: одна из лучших книг в моей коллекции — «Designing Data-Intensive Applications» Мартина Клеппмана (она же всем известная «книжка с кабанчиком», она же «Высоконагруженные приложения. Программирование, масштабирование, поддержка»).

Однозначно рекомендую к прочтению. Конечно, одна эта книга не позволит вам с нуля разработать свою распределённую базу данных, но она поможет углубиться в проблематику работы с данными и осознать, что никаких гарантий не существует (особенно в распределённых системах) и насколько сложно и дорого поддерживать хотя бы иллюзию этих гарантий.

Самая длинная подстрока, являющаяся валидной скобочной последовательностью

Всем привет!
Сегодня продолжаем одновременно 2 начинания: решать сложные задачи и решать задачи на валидные скобочные последовательности 🙂

Как я уже говорил ранее, классическая задача на валидацию скобочной последовательности считается легкой только из-за их мейнстримности: это чуть ли не первая задача, которую решают на алгоритмах, когда проходят стек. А как часто она попадается на интервью, страшно представить.

Но, на самом деле, эта задача не из простых и, стоит хоть немного отойти от классической формулировки, и из легкой она превращается в сложную. Так и в сегодняшней вариации — даже несмотря на то, что оптимальное решение использует все тот же самый стек (да и алгоритм в итоге очень несложный), догадался я до него не с первого раза.

Сложность: 🤬 Сложная

ℹ️ Описание

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

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

— Длина каждой строки от 0 до 30 000 символов
— Строка состоит из символов '(' и ')'

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

s := "(()"

Ответ

2

Самая длинная правильная скобочная последовательность — ().

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

s := ")()())"

Ответ

4

Самая длинная правильная скобочная последовательность - ()().

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

s := ""

Ответ

0

✅ Решение

Можно попробовать пойти с помощью брутфорса — взять всю строку (как самую длинную возможную подстроку) и проверить её на валидность. После уменьшить длину подстроки на единицу и проверить на валидность 2 возможные подстроки длиной n-1. Потом ещё на единицу и проверить три возможные подстроки длиной n-2. И так далее, пока не наткнёмся на первую валидную подстроку. Но такое решение будет слишком долгим — на LeetCode вы даже не сможете пройти все тест-кейсы из-за таймаута.

Чтобы найти более оптимальное решение, можно переформулировать задачу: самая длинная подстрока с валидной скобочной последовательностью — это максимальное расстояние между двумя невалидными подстроками. Осталось придумать, как с помощью стека мы можем вырезать все валидные подстроки из оригинальной строки, и задача будет решена 🙂

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

#stack #hard

Преобразование строки в целое число (atoi)

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

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

ℹ️ Описание

Реализуйте функцию myAtoi(string s), которая преобразует строку в 32-битное знаковое целое число.

Функция должна следовать следующим правилам при чтении строки:

— Пропустить любые ведущие пробелы
— Проверить наличие знака (+ или -)
— Читать следующие символы до тех пор, пока они составляют последовательность цифр.
— Преобразовать эти цифры в целое число.
— Если первая непустая последовательность символов не является допустимым целым числом, вернуть 0.
— Если полученное значение превышает диапазон 32-битного знакового целого числа, вернуть INT_MAX (2^31 - 1) или INT_MIN (-2^31).

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

— Длина строки находится в диапазоне от 0 до 200
— Строка s состоит из английских букв (как заглавных, так и строчных), цифр, пробелов и знаков «+», «-» и «.»

1️⃣ Пример

Входные данные: "42"
Ответ: 42

2️⃣ Пример

Входные данные: " -42"
Ответ: -42

3️⃣ Пример

Входные данные: "4193 with words"
Ответ: 4193

4️⃣ Пример

Входные данные: "words and 987"
Ответ: 0

5️⃣ Пример

Входные данные: "-91283472332"
Ответ: -2147483648

✅ Решение

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

В первую очередь нужно пропустить все ведущие пробелы в строке. Для этого запустим цикл типа while и будем увеличивать переменную index для определения позиции, откуда надо начинать преобразование числа.

После этого нам нужно проверить присутствует ли в строке определение знака числа. Для этого заведем переменную sign.

— Если встречаем в строке символ +, то устанавливаем значение sign равным 1.
— Если встречаем в строке символ -, то устанавливаем значение sign равным -1.
— Если в строке присутствовал знак числа, то еще необходимо увеличить index на единицу.

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

— Если char < "0" или char > "9", то символ не является числом. Как только мы встретили не числовой символ в строке, то дальнейший разбор необходимо прекратить.
—Если смвол является числом, то его необходимо добавить к результирующему числу. Для этого надо воспользоваться следующей формулой res = res * 10 + char - '0'. Это позволяет прибавить цифру справа к существующему числу.

После этих операций необходимо проверить, превысило ли число минимальное или максимальное значение.

— Если превышено максимальное значение, то в качестве ответа надо вернуть максимальное.
— Если превышено минимальное значение, то в качестве ответа надо вернуть минимальное.

В заключение, в ответе нужно вернуть res умноженный на знак sign.

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

#string #medium

Вес Хэмминга

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

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

Примеры

1️⃣ Число 5

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

2️⃣ Число 13

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

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

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

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

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

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

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

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 в двоичном представлении числа. Этот бит также иногда называют младшим установленным битом.

Побитовые сдвиги: Основы и Применение

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

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

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

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

Пример

1010 << 1 = 10100

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

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

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

Пример

1010 >> 1 = 0101 = 101

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

---------

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

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

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

Количество установленных битов

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

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

ℹ️ Описание

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

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

— Значение n находится в диапазоне от 1 до 2^31 - 1

1️⃣ Пример

Входные данные: n = 11

Ответ: 3

Объяснение: В двоичном представлении число имеет в общей сложности три установленных бита — 1011.

2️⃣ Пример

Входные данные: n = 128

Ответ: 1

Объяснение: В двоичном представлении число имеет в общей сложности один установленный бит — 10000000.

3️⃣ Пример

Входные данные: n = 2147483645

Ответ: 30

Объяснение: В двоичном представлении число имеет в общей сложности тридцать установленных битов — 1111111111111111111111111111101.

✅ Решение через подсчет популяции (Pop Count)

В качестве первого решения рассмотрим наиболее интуитивно понятный способ — буквально посчитать, сколько есть единиц в двоичном представлении числа. Такой способ называется подсчетом популяции, он же — pop count. Однако, чтобы не приводить каким-то специальным способом число в двоичное представление, а потом итерироваться по каждому биту, мы, как всегда, воспользуемся хитростью.

Из условия задачи мы знаем, что n может иметь значения в диапазоне от 1 до 2^31 - 1. Это означает, что мы рассматриваем 32-битные числа. То есть число n содержит максимум 32 бита.
Теперь возьмем для примера число 13 и представим его в двоичном виде.

13 -> 1101

Чтобы понять, равен ли определенный бит в числе единице, этот бит нужно умножить на 1 и посмотреть на результат. Если результат равен 1, то и бит тоже равен 1. В противном случае бит равен нулю.
Это определяется правилами побитового умножения. Если в одном операнде всегда стоит единица, то результат операции может быть равен единице только в том случае, если второй операнд тоже равен 1.

0 & 1 = 0
1 & 1 = 1

Это означает, что мы можем пройтись по каждому из 32 битов числа n и умножить его побитово на 1. Если результат равен единице, то мы можем увеличить счетчик установленных битов на 1. После подсчета всех 32 битов мы получим количество установленных битов в счетчике.

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

Мы заведем маску mask, которая на самом деле является целым числом, и счетчик count. Начальное значение mask будет равно 1. Теперь посмотрим на наглядный пример решения.

Представим наше число 13 и маску в двоичном виде и проведем между ними побитовое умножение.

1101 & 0001 = 0001 = 1

В качестве результата получилось положительное число, то есть в первом бите числа n находится единица. Увеличиваем счетчик установленных битов count на 1. Теперь сдвинем единицу в маске на одну позицию влево и сделаем то же самое.

1101 & 0010 = 0000 = 0

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

1101 & 0100 = 0100 = 4

Так в ответе мы получили 4, а не 0, это означает, что на месте единицы в маске в числе n бит также равен единице. Увеличиваем счетчик установленных битов count на 1.

1101 & 1000 = 1000 = 8

По такой же логике мы понимаем, что в старшем бите числа `n` также находится единица. Таким образом мы получили count = 3, то есть в числе n = 13 три установленных бита.

Остался последний вопрос. Как сдвигать единицу в маске? Для этого мы воспользуемся операцией побитового сдвига влево <<.

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

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

По времени

Так как мы знаем, что число n занимает максимум 32 бита, нам необходимо сделать 32 проверки в цикле. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

#bit_manipulation #easy

✅ Решение через смену младшего установленного бита

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

Вместо проверки каждого бита числа мы неоднократно обращаем наименее значимый единичный бит числа на 0 и добавляем 1 к нашему счетчику. При этом число n мы заменяем на полученный результат побитового умножения.

Как только число n становится равным 0, мы знаем, что в нем больше не осталось единиц. Это означает, что в нашем счетчике count содержится правильное количество единиц, которые были в битовом представлении числа n.

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

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

По времени

В худшем случае все биты n являются единичными и мы имеем максимум 32 бита. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

#bit_manipulation #easy

Подсчет битов

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

ℹ️ Описание

Дано число n.

Верните массив ans длиною n + 1, в котором значение каждого i-го элемента равно количеству единиц в двоичном представлении i.
При этом i находится в диапазоне от 0 до n.

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

— Значение n находится в диапазоне от 1 до 10^5

1️⃣ Пример

Входные данные: n = 2

Ответ: [0, 1, 1]

Объяснение:

Двоичные представления чисел.

0 --> 0
1 --> 1
2 --> 10

2️⃣ Пример

Входные данные: n = 5

Ответ: [0, 1, 1, 2, 1, 2]

Объяснение:

Двоичные представления чисел.

0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

✅ Решение через подсчет популяции (Pop Count)

В качестве решения можно воспользоваться способом подсчета популяции из задачи «Количество установленных битов».

Достаточно вызвать метод hammingWeight для подсчета веса Хэмминга в цикле от 0 до n.

const hammingWeight = (n: number): number => {
    let count = 0

    while (n != 0) {
        count++
        n &= n - 1
    }

    return count
}

export const countBitsPopCount = (n: number): number[] => {
    const res: number[] = []

    for (let i = 0; i <= n; i++) {
        res.push(hammingWeight(i))
    }

    return res
}

✅ Решение через динамическое программирование

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

F(x) = F(x/2) + (x mod 2)

Это формула обозначает, что для получения количества единиц в битовом представлении числа x достаточно взять количество единиц в битовом представлении числа x/2 и прибавить к нему остаток от деления числа x на 2.

Теперь перефразируем эту формулу в битовых выражениях:

операция x / 2 эквивалентна битовому сдвигу на единицу вправо, то есть x >> 1
операция x mod 2 эквивалентна получению младшего бита, то есть x & 1

Общая идея

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

Мы запускаем цикл подсчета единиц для каждого числа от 0 до n и каждый результат запоминаем в результирующий массив res. При этом на каждой итерации мы можем опираться на результаты вычислений предыдущих итераций и получать значение для i >> 1 из результирующего массива, так как оно уже было рассчитано раньше.

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

#bit_manipulation #easy

Односвязный список (Singly Linked List)

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

Вот пример типичной структуры узла односвязного списка.

type MyLinkedListNode = {
    val: number;
    next: MyLinkedListNode | null;
}

type MyLinkedListNode struct {
    Val  int
    Next *MyLinkedListNode
}

У связанных списков всегда есть первый элемент списка, который называется head (голова) и последний элемент — tail (хвост). Чтобы предоставить весь список достаточно иметь ссылку на его голову, так как путем последовательного перебора узлов черерз next можно проитерироваться по всему списку.

В нашем примере ниже в качестве головного выступает элемент со значением 1. От него можно перейти по ссылке к следующему элементу со значением 2 и уже от него к хвостовому элементу со значением 3.

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

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

2. Еще проще работает удаление первого элемента и тоже за константное время. Для удаления достаточно переписать ссылку на head ссылкой на head.next. Соответственно, это тоже работает за константное время.

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

4. Все операции в связном списке имеют константную сложность по памяти, так как для их выполнения достаточно оперировать ссылками на элементы.

#linked_list

Пример односвязного списка

#linked_list