Algorithmics: хакаем алгоритмические собесы

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


➡️ Оптимальное решение

#medium #trie #binary_search

Система поиска подсказок

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

Классические задачи для префиксного дерева включают поиск по префиксу: например, нахождение конкретного слова или подготовка автодополнений (саджестов) по заданным префиксам.

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

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

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

ℹ️ Описание

Дан массив строк products, представляющий доступные названия продуктов, и строка searchWord, представляющая искомое слово, вводимое пользователем.

Реализуйте функцию, которая возвращает массив массивов, где:
— Каждый подмассив содержит список подсказок для соответствующего префикса строки searchWord. Первый подмассив соответствует префиксу из первого символа строки searchWord, второй — префиксу из первых двух символов, и так далее.
— Каждый подмассив включает до трех продуктов из products, отсортированных в лексикографическом порядке.
— Если для какого-либо префикса не найдено совпадений, соответствующий подмассив должен быть пустым.

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

— 1 <= products.length <= 1000 — количество продуктов.
— 1 <= products[i].length <= 3000 — длина каждой строки продукта.
— 1 <= searchWord.length <= 1000 — длина строки поиска.
— Все строки состоят только из строчных латинских букв.

1️⃣ Пример

Продукты: products = ["mobile","mouse","moneypot","monitor","mousepad"]

Искомое слово: searchWord = "mouse"

Ответ:

[
    ["mobile","moneypot","monitor"], // список подсказок для префикса "m"
    ["mobile","moneypot","monitor"], // список подсказок для префикса "mo"
    ["mouse","mousepad"], // список подсказок для префикса "mou"
    ["mouse","mousepad"], // список подсказок для префикса "mous"
    ["mouse","mousepad"], // список подсказок для префикса "mouse"
]

2️⃣ Пример

Продукты: products = ["havana"]

Искомое слово: searchWord = "havana"

Ответ:

[
    ["havana"], // список подсказок для префикса "h"
    ["havana"], // список подсказок для префикса "ha"
    ["havana"], // список подсказок для префикса "hav"
    ["havana"], // список подсказок для префикса "hava"
    ["havana"], // список подсказок для префикса "havan"
    ["havana"], // список подсказок для префикса "havana"
]

✅ Реализация

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

➡️ Решение через преобразование в префиксное дерево

Задача разделяется на 2 подзадачи:

— Имплементировать структуру данных Trie и преобразовать входящий массив
— Имплементировать метод Closest, который по префиксу вернет массив подсказок.

Помимо этого есть несколько решений по оптимизации: например, можно обходить дерево с самого большого возможного префикса. Тогда можно реализовать "всплытие" подсказок и избежать лишних обходов в глубину. Или же можно пожертвовать памятью и для каждого узла дерева сохранять набор подсказок в момент добавления нового слов.

➡️ Решение через бинарный поиск

Префиксное дерево (Trie)

Префиксное дерево, или Trie (произносится как «три») — это структура данных, которая позволяет эффективно хранить и искать строки по их префиксам. В отличие от других деревьев, в Trie каждый узел может содержать символ строки, а путь от корневого узла до любого узла представляет собой префикс какого-либо слова, хранимого в дереве. Важно помнить, что конечное слово в данной структуре не обязательно будет оканчиваться листовой нодой, так как слово целиком может являться префиксом другого слова, Поэтому, помимо прочего, ноды должны содержать признак того, являются ли они окончанием какого-либо из слов.

Вот пример структуры узла Trie.

type TrieNode = {
    children: { [key: string]: TrieNode };
    isEndOfWord: boolean;
}

type TrieNode struct {
    Children    map[rune]*TrieNode
    IsEndOfWord bool
}

Каждый узел имеет мапу children, где ключом является символ, а значением — следующий узел, представляющий символ в этом слове. Узел isEndOfWord помечает конец слова.

Простыми словами, если мы хотим добавить слова «cat» в дерево, нам нужно разбить его посимвольно и каждый символ будет представлять собой отдельную ноду. Иерархия нод будет выстроена в соответствии с порядком слов, то есть в нашем примере: «c» -> «a» -> «t».

Вот так можно визуализировать префиксное дерево, в котором содержаться слова cat, car, cart, care, dog, dot, и dove:

           (root)
         /        \
        c          d
       /           |
      a            o    
     / \         / | \
   t*   r*      g* t* v
       / \            |
     e*  t*           e*

### Пример работы с Trie

Допустим, мы хотим сохранить слова «cat» и «car». Префиксное дерево будет выглядеть следующим образом:

1. Корневой узел содержит ссылки на узлы c, которые ведут к поддереву для символа a.
2. Узел a ветвится на узлы t и r, представляющие слова «cat» и «car».
3. В узлах t и r флаг isEndOfWord установлен в true, указывая, что здесь заканчиваются слова.

### Основные операции в Trie

1. Добавление слова — добавление слова в Trie выполняется за O(N), где N — длина слова. Мы последовательно проходим каждый символ слова и либо создаем новый узел, если он не существует, либо переходим к существующему.

2. Поиск слова — поиск также выполняется за O(N). Для поиска слова достаточно пройти по каждому символу слова. Если на каком-то этапе путь отсутствует, значит, слово не найдено.

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

### Преимущества и недостатки Trie

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

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

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

#trie

Максимальная сумма парных элементов связного списка

Продолжаем изучение связанных списков и сегодня у нас новая задача.

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

ℹ️ Описание

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

Парный элемент для i'го считается элемент с индексом n - i - 1, где 0 <= i <= n / 2 - 1. То есть, для первого элемента списка парным будет считаться последний элемент списка, для второго - предпоследний и так далее.

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

— Список всегда имеет четное количество элементов
— Количество элементов лежит в диапазоне от 2 до 100 000
— Значение элемента лежит в диапазоне от 1 до 100 000

1️⃣ Пример

Элементы списка: [5,4,2,1]

Ответ: 6

Пояснение: В списке есть 2 пары элементов: [5, 1] и [4, 2]. Сумма обоих пар равна 6.

2️⃣ Пример

Входные данные: [4,2,2,3]

Ответ: 7

Пояснение: В списке есть 2 пары элементов: [4, 3] и [2, 2]. Максимальная сумма равна 7.

3️⃣ Пример

Входные данные: [1,100000]

Ответ: 100001

✅ Реализация

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

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

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

➡️ Решение через преобразование в массив

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

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

— currentListElement — будем перемещать по списку последовательно.
— oddElementList — будем двигать через два элемента за раз. В связном списке это делается следующим образом:

oddElementList = oddElementList.Next.Next

Таким образом, когда указатель oddElementList достигнет конца списка, указатель currentListElement будет указывать на начало второй половины нашего списка.

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

➡️ Решение через стек

Итак, оптимальное решение

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

Чтобы быстро находить пары, можно создать вспомогательный список, развернутый в обратном порядке. Для изменения порядка списка можно написать простую функцию reverseList (изменение происходит in-place без создания нового списка).

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

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

➡️ Оптимальное решение

#medium #linked_list

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

Привет, друзья. Теперь мы с вами закрепим теорию, которую узучили ранее и реализуем связанный список с нуля.

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

ℹ️ Описание

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

Узел в односвязном списке должен иметь два атрибута: val и next.

val — значение текущего узла
next — указатель/ссылка на следующий узел

Если вы хотите использовать двусвязный список, вам понадобится еще один атрибут prev, чтобы указать на предыдущий узел в связанном списке.
Учтите, что отсчет порядка узлов в связанном списке начинается с нуля.

Реализуйте класс MyLinkedList:

— MyLinkedList() инициализирует объект MyLinkedList.
— int get(int index) метод позволяет получить значение узла в списке по его индексу. Если индекс неверный, метод должен возвращать -1.
— void addAtHead(int val) метод позволяет добавлять узел со значением val в начало списка.
— void addAtTail(int val) метод позволяет добавлять узел со значением val в конец списка.
— void addAtIndex(int index, int val) метод позволяет добавлять узел со значением val на место элемента с индексом index. Если индекс равен длине связанного списка, узел будет добавлен в его конец. Если индекс больше длины списка, то его добавлять не нужно.
— void deleteAtIndex(int index) метод позволяет удалить элемент под индексом index из списка.

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

— Значения каждого элемента списка находятся в диапазоне от 0 до 1000
— В списке может быть от 0 до 1000 элементов

1️⃣ Пример

// псевдокод
myLinkedList = MyLinkedList();
myLinkedList.addAtHead(1);        // [1]
myLinkedList.addAtTail(3);        // [1, 3]
myLinkedList.addAtIndex(1, 2);    // [1, 2, 3]
myLinkedList.get(1);              // 2
myLinkedList.deleteAtIndex(1);    // [1, 3]
myLinkedList.get(1);              // 3

✅ Реализация односвязного списка

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

Для начала опишем простой класс MyLinkedList с инициализирующим конструктором и создадим пустые методы-заглушки.

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

export class MyLinkedList {
    head: MyLinkedListNode | null;
    size: number;

    constructor() {
        this.head = null;
        this.size = 0;
    }

    get(index: number): number {
        return 0
    }

    addAtIndex(index: number, val: number): void {}

    addAtHead(val: number): void {}

    addAtTail(val: number): void {}

    deleteAtIndex(index: number): void {}
}

Здесь мы сразу описали тип MyLinkedListNode для одной ноды списка и сам класс.

Во-первых, в классе мы завели переменную head, которая по умолчанию равна null. Это и есть ссылка на голову списка, то есть на его первый элемент.

Во-вторых, нельзя просто так получить размер связанного списка, так как для подсчета количества нод нужно обойти весь список от его головы до хвоста. Чтобы упростить нам жизнь и дальнейшие вычисления мы завели внутреннюю переменную size в классе, которая инициализируется нулем при создании класса и показывает размер списка. При выполнении операций добавления переменная будет увеличиваться на 1, а при удалении - уменьшаться на 1.

🔸Получение элемента из списка

Метод предназначен для получения значения узла по указанному индексу.

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, возвращается -1, так как такой индекс недопустим.

Далее необходимо пройти по списку от его головы и найти элемент с нужным индексом. Для этого мы запускаем цикл, который выполняется до тех пор, пока i < index. Инициализируем переменную curr, которая изначально равна head то есть ссылке на первый элемент списка. Далее на каждой итерации цикла в переменную curr записывается ссылка на следующий элемент в списке через curr.next.

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

🔸Добавление элемента в список по индексу

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

Следующим шагом увеличиваем внутреннюю переменную size на единицу, так происходит добавление элемента.

Если индекс равен 0, то происходит вставка в начало списка. Это означает, что нам достаточно создать новый элемент, указать в его next ссылку на текущий head списка и заменить текущий head новым элементом, после чего выйти из функции.

Если же индекс не равен 0, то нам нужно добавить элемент перед тем, который находится на позиции равной index. Мы выделили отдельный внутренний метод findPrevNode. Вызвав этот метод мы получаем предшествующий переданному индексу узел prev. Если такой узел существует, то нам достаточно в next нового элемента добавить ссылку из prev.next, а в prev.next положить ссылку на новый элемент. Таким образом новый элемент встраивается в цепочку узлов списка на заданную позицию.

🔸Добавление элемента в начало списка

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в начало. Для этого просто вызовем метод с нулевым индексом this.addAtIndex(0, val)

🔸Добавление элемента в конец списка

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в конец. Для этого просто вызовем метод с индексом равным длине списка this.addAtIndex(this.size, val)

🔸Удаление элемента

В первую очередь нужно проверить корректность индекса. Если индекс меньше 0 или больше или равен размеру списка, метод завершает работу, так как такой индекс некорректен.

Далее необходимо уменьшить значение переменной size на единицу, так как происходит удаление.

Если индекс равен нулю, значит происходит удаление первого элемента. В этом случае достаточно изменить head списка на head.next.

Если же индекс не равен нулю, то нужно сначала найти элемент, который находится перед удаляемым. Затем нужно проставить ссылку с предыдущего на следующий элемент prev.next = prev.next.next.

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

#linked_list #medium

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

Удаление первого элемента списка

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

Удаление элемента из середины списка

1. Находим узел, который предшествует удаляемому узлу, проходя по списку, начиная с головы (head). Это нужно для того, чтобы изменить ссылку на следующий элемент.
2. Изменяем ссылку в предшествующем узле на следующий узел удаляемого узла (то есть пропускаем узел, который хотим удалить).
3. Освобождаем память для удаляемого узла.

Удаление последнего элемента списка

1. Если список пуст, ничего не делаем.
2. Если в списке один элемент (то есть это и есть голова), то просто удаляем этот элемент, присвоив указателю головы null/nil.
3. Если элементов больше одного, проходим по списку, находя предпоследний элемент.
4. Устанавливаем в поле next предпоследнего элемента значение null/nil, таким образом удаляя ссылку на последний элемент.

Рассмотрим, как добавлять элементы в связный список.

Добавление нового узла в середину списка

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

1. Создаем новый узел с желаемым значением.
2. Находим позицию в списке, на которую мы добавляем новый элемент. Для этого перебором нужно дойти от начала списка до элемента со значением 2.
3. Меняем ссылку next в элементе со значением 1 на новый элемент.
4. В новом элементе добавляем в next ссылку на элемент с со значением 3.

Добавление нового узла в начало списка

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

Добавление нового узла в конец списка

1. Создаем новый узел с желаемым значением.
2. Проходим по списку от начала (head) до последнего узла, используя ссылки next, пока не найдем узел, у которого поле next равно null/nil.
3. В поле next последнего узла записываем ссылку на новый узел.

#linked_list

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

#linked_list

Односвязный список (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

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

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

ℹ️ Описание

Дано число 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

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

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

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

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

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

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

По времени

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

По памяти

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

#bit_manipulation #easy

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

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

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

ℹ️ Описание

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

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

— Значение 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

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

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

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

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

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

Пример

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)

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

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

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

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

Преобразование строки в целое число (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

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

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

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

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

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

ℹ️ Описание

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

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

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

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

s := "(()"

Ответ

2

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

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

s := ")()())"

Ответ

4

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

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

s := ""

Ответ

0

✅ Решение

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

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

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

#stack #hard

Всем привет!

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

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

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

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