Задача: 344. Reverse String
Сложность: easy

Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.

Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.

Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

👨‍💻 Алгоритм:

1⃣Инициализация указателей:
Установите два указателя: один на начало массива (left), другой на конец массива (right).

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

3⃣Завершение работы:
Повторяйте шаг 2 до тех пор, пока левый указатель не станет больше или равен правому.

😎 Решение:

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 113. Path Sum II
Сложность: medium

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

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]]

👨‍💻 Алгоритм:

1⃣Функция recurseTree принимает текущий узел, оставшуюся сумму и текущий путь pathNodes. Она исследует дерево рекурсивно.

2⃣Если текущий узел — лист и его значение равно оставшейся сумме, сохраняем копию пути в pathsList.

3⃣Поскольку значения могут быть отрицательными, важно обходить всё дерево — независимо от текущей суммы.

😎 Решение:

class Solution {
public:
    void recurseTree(TreeNode* node, int remainingSum, vector<int>& pathNodes,
                     vector<vector<int>>& pathsList) {
        if (node == NULL) {
            return;
        }

        pathNodes.push_back(node->val);

        if (remainingSum == node->val && node->left == NULL && node->right == NULL) {
            pathsList.push_back(vector<int>(pathNodes));
        } else {
            this->recurseTree(node->left, remainingSum - node->val, pathNodes, pathsList);
            this->recurseTree(node->right, remainingSum - node->val, pathNodes, pathsList);
        }

        pathNodes.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> pathsList;
        vector<int> pathNodes;
        this->recurseTree(root, sum, pathNodes, pathsList);
        return pathsList;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 526. Beautiful Arrangement
Сложность: medium

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

👨‍💻 Алгоритм:

1⃣ Инициализация и подготовка массива:
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.

2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.

😎 Решение:

class Solution {
public:
    int count = 0;
    
    int countArrangement(int N) {
        vector<int> nums(N);
        iota(nums.begin(), nums.end(), 1);
        permute(nums, 0);
        return count;
    }
    
    void permute(vector<int>& nums, int l) {
        if (l == nums.size()) {
            count++;
        }
        for (int i = l; i < nums.size(); ++i) {
            swap(nums[i], nums[l]);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                permute(nums, l + 1);
            }
            swap(nums[i], nums[l]);
        }
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 397. Integer Replacement
Сложность: medium

К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.

Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

👨‍💻 Алгоритм:

1⃣Начните с данного числа n и выполните одну из следующих операций:
Если n четное, замените n на n / 2.
Если n нечетное, замените n на n + 1 или n - 1.

2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов.

3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат.

😎 Решение:

class Solution {
public:
    int integerReplacement(int n) {
        unordered_map<long, int> memo;
        return helper(n, memo);
    }
    
    int helper(long n, unordered_map<long, int>& memo) {
        if (n == 1) return 0;
        if (memo.count(n)) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + helper(n / 2, memo);
        } else {
            memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo));
        }
        
        return memo[n];
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 205. Isomorphic Strings
Сложность: easy

Даны две строки s и t, определить, являются ли они изоморфными.
Строки считаются изоморфными, если символы одной строки можно взаимно однозначно сопоставить символам другой строки, сохраняя порядок.

Пример:

Input: s = "egg", t = "add" Output: true

👨‍💻 Алгоритм:

1⃣Создаём два словаря (или массивы) mapping_s_t и mapping_t_s для хранения отображений символов s → t и t → s.

2⃣Проходим по строкам:
Если сопоставление ещё не задано — сохраняем его.
Если уже задано — проверяем корректность: mapping_s_t[s[i]] должно быть t[i], и наоборот.

3⃣Если обнаружена ошибка в отображении — возвращаем false. В противном случае — true.

😎 Решение:

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int mappingDictStoT[256] = {0};
        int mappingDictTtoS[256] = {0};

        for (int i = 0; i < s.length(); ++i) {
            char c1 = s[i];
            char c2 = t[i];
            if (mappingDictStoT[c1] == 0 && mappingDictTtoS[c2] == 0) {
                mappingDictStoT[c1] = c2;
                mappingDictTtoS[c2] = c1;
            }
            else if (!(mappingDictStoT[c1] == c2 &&
                       mappingDictTtoS[c2] == c1)) {
                return false;
            }
        }

        return true;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 71. Simplify Path
Сложность: medium

Дан абсолютный путь в стиле Unix. Требуется упростить его до канонического вида, убрав . (текущий каталог), .. (на уровень выше), пустые сегменты и повторяющиеся слэши.

Пример:

Input: path = "/home/" Output: "/home"

👨‍💻 Алгоритм:

1⃣Разделить строку path по символу '/' — получим массив строк, где каждая строка — компонент пути

2⃣Пройтись по компонентам:
если компонент "." или "" — пропускаем
если ".." — удалить верхний элемент из стека, если он есть
иначе — добавить компонент в стек (как имя директории)

3⃣Собрать итоговый путь из стека, добавив '/' перед каждым элементом.
Если стек пуст — путь это просто "/"

😎 Решение:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        stringstream ss(path);
        string temp;

        while (getline(ss, temp, '/')) {
            if (temp == "..") {
                if (!stack.empty()) stack.pop_back();
            } else if (temp != "." && !temp.empty()) {
                stack.push_back(temp);
            }
        }

        string res = "";
        for (const auto& str : stack) {
            res += "/" + str;
        }

        return res.empty() ? "/" : res;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

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

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

👨‍💻 Алгоритм:

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> toDeleteSet(to_delete.begin(), to_delete.end());
        vector<TreeNode*> forest;

        root = processNode(root, toDeleteSet, forest);
        if (root) {
            forest.push_back(root);
        }

        return forest;
    }

private:
    TreeNode* processNode(TreeNode* node, unordered_set<int>& toDeleteSet, vector<TreeNode*>& forest) {
        if (!node) return nullptr;

        node->left = processNode(node->left, toDeleteSet, forest);
        node->right = processNode(node->right, toDeleteSet, forest);

        if (toDeleteSet.count(node->val)) {
            if (node->left) forest.push_back(node->left);
            if (node->right) forest.push_back(node->right);
            return nullptr;
        }

        return node;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1017. Convert to Base -2
Сложность: medium

Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".

Пример:

Input: n = 2
Output: "110"

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте пустую строку для хранения двоичного представления числа.
Используйте цикл для вычисления каждой цифры числа в базе -2.

2⃣Вычисление цифр:
В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2.
Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1.
Добавляйте остаток в начало строки.

3⃣Возврат результата:
Верните строку, представляющую число в базе -2. Если строка пустая, верните "0".

😎 Решение:

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        string res = "";
        while (n != 0) {
            int remainder = n % -2;
            n /= -2;
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res = to_string(remainder) + res;
        }
        return res;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

👨‍💻 Алгоритм:

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

#include <unordered_map>
#include <string>

class MapSum {
    std::unordered_map<std::string, int> map;
public:
    MapSum() {}
    void insert(std::string key, int val) {
        map[key] = val;
    }
    int sum(std::string prefix) {
        int ans = 0;
        for (const auto& pair : map) {
            if (pair.first.find(prefix) == 0) {
                ans += pair.second;
            }
        }
        return ans;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 651. 4 Keys Keyboard
Сложность: medium

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста.

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:

public class Solution {
    public int MaxA(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++) {
                dp[i] = Math.Max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }
        return dp[n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

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

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

👨‍💻 Алгоритм:

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : log(bound) / log(x);
        int b = y == 1 ? bound : log(bound) / log(y);
        unordered_set<int> powerfulIntegers;

        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = pow(x, i) + pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.insert(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }

        return vector<int>(powerfulIntegers.begin(), powerfulIntegers.end());
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1232. Check If It Is a Straight Line
Сложность: easy

Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.

Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

👨‍💻 Алгоритм:

1⃣Определение наклона:
Вычисляем наклон между первыми двумя точками и используем его как эталон.

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

3⃣Если все наклоны совпадают, то все точки лежат на одной прямой.

😎 Решение:

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        
        for (const auto& point : coordinates) {
            int x = point[0], y = point[1];
            if ((x1 - x0) * (y - y0) != (y1 - y0) * (x - x0)) {
                return false;
            }
        }
        return true;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

👨‍💻 Алгоритм:

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int biggest = 0;
        int secondBiggest = 0;
        for (int num : nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else if (num > secondBiggest) {
                secondBiggest = num;
            }
        }
        return (biggest - 1) * (secondBiggest - 1);
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 72. Edit Distance
Сложность: medium

Даны две строки word1 и word2. Нужно найти минимальное количество операций (вставка, удаление, замена), чтобы преобразовать word1 в word2.

Пример:

Input: word1 = "horse", word2 = "ros"
Output: 3
Пояснение:
horse → rorse (замена h на r)
rorse → rose (удаление r)
rose → ros (удаление e)

👨‍💻 Алгоритм:

1⃣Используем рекурсивный подход с кэшированием: minDistance(i, j) — минимальная стоимость преобразования word1[0..i-1] в word2[0..j-1]

2⃣Базовые случаи:
если i == 0, нужно вставить j символов
если j == 0, нужно удалить i символов

3⃣Рекурсия:
если символы совпадают → переходим к предыдущим
иначе:
вставка (i, j-1)
удаление (i-1, j)
замена (i-1, j-1)
→ берём минимум из трёх и добавляем 1

😎 Решение:

class Solution {
public:
    vector<vector<int>> memo;

    int minDistance(string word1, string word2) {
        memo.resize(word1.length() + 1, vector<int>(word2.length() + 1, -1));
        return minDistanceRecur(word1, word2, word1.size(), word2.size());
    }

    int minDistanceRecur(string &word1, string &word2, int word1Index, int word2Index) {
        if (word1Index == 0) return word2Index;
        if (word2Index == 0) return word1Index;

        if (memo[word1Index][word2Index] != -1)
            return memo[word1Index][word2Index];

        int minEditDistance = 0;

        if (word1[word1Index - 1] == word2[word2Index - 1]) {
            minEditDistance = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
        } else {
            int insertOp = minDistanceRecur(word1, word2, word1Index, word2Index - 1);
            int deleteOp = minDistanceRecur(word1, word2, word1Index - 1, word2Index);
            int replaceOp = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
            minEditDistance = 1 + min(insertOp, min(deleteOp, replaceOp));
        }

        memo[word1Index][word2Index] = minEditDistance;
        return minEditDistance;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

👨‍💻 Алгоритм:

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

2⃣Проверка на коллинеарность:
Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны.

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1207. Unique Number of Occurrences
Сложность: easy

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

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

👨‍💻 Алгоритм:

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        unordered_set<int> freqSet;
        for (auto& pair : freq) {
            freqSet.insert(pair.second);
        }
        return freq.size() == freqSet.size();
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

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

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

Пример:

Input: root = [3,9,20,null,null,15,7] Output: 3

👨‍💻 Алгоритм:

1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2⃣Для данной задачи подойдёт несколько способов.

3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

class Solution {
  public:
    int maxDepth(TreeNode *root) {
      if (root == NULL) {
        return 0;
      }
      return max(1 + maxDepth(root -> left), 1 + maxDepth(root -> right));
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива.

3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива.

😎 Решение:

int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int maxLength = 0;
    for (int i = nums1.size() - 1; i >= 0; i--) {
        for (int j = nums2.size() - 1; j >= 0; j--) {
            if (nums1[i] == nums2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }
    return maxLength;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм:

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval {
public:
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
        vector<Interval> intervals;
        for (const auto& employee : schedule) {
            intervals.insert(intervals.end(), employee.begin(), employee.end());
        }
        
        sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });
        
        vector<Interval> merged;
        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back().end < interval.start) {
                merged.push_back(interval);
            } else {
                merged.back().end = max(merged.back().end, interval.end);
            }
        }
        
        vector<Interval> freeTime;
        for (int i = 1; i < merged.size(); ++i) {
            if (merged[i].start > merged[i-1].end) {
                freeTime.push_back(Interval(merged[i-1].end, merged[i].start));
            }
        }
        
        return freeTime;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 112. Path Sum
Сложность: easy

Дан корень бинарного дерева и целое число targetSum. Верните true, если существует путь от корня до листового узла, сумма значений по которому равна targetSum.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true

👨‍💻 Алгоритм:

1⃣Инициализация: создаём два стека — один для узлов (node_stack), второй для текущей оставшейся суммы (sum_stack). Начинаем с корня и суммы sum - root->val.

2⃣Обход: в цикле извлекаем узел и соответствующую сумму. Если узел — лист, и сумма равна 0, возвращаем true.

3⃣Добавляем потомков узла в стек, уменьшая текущую сумму на их значения.

😎 Решение:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;

        std::stack<TreeNode*> node_stack;
        std::stack<int> sum_stack;

        node_stack.push(root);
        sum_stack.push(sum - root->val);

        while (!node_stack.empty()) {
            TreeNode* node = node_stack.top(); node_stack.pop();
            int curr_sum = sum_stack.top(); sum_stack.pop();

            if (!node->left && !node->right && curr_sum == 0) {
                return true;
            }

            if (node->right) {
                node_stack.push(node->right);
                sum_stack.push(curr_sum - node->right->val);
            }

            if (node->left) {
                node_stack.push(node->left);
                sum_stack.push(curr_sum - node->left->val);
            }
        }

        return false;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 436. Find Right Interval
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

👨‍💻 Алгоритм:

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<vector<int>> endIntervals = intervals;
        unordered_map<vector<int>, int> hash;
        for (int i = 0; i < intervals.size(); ++i) {
            hash[intervals[i]] = i;
        }
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });
        sort(endIntervals.begin(), endIntervals.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });
        int j = 0;
        vector<int> res(intervals.size());
        for (int i = 0; i < endIntervals.size(); ++i) {
            while (j < intervals.size() && intervals[j][0] < endIntervals[i][1]) {
                j++;
            }
            res[hash[endIntervals[i]]] = j == intervals.size() ? -1 : hash[intervals[j]];
        }
        return res;
    }
};

Ставь 👍 и забирай 📚 Базу знаний