Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

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

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

1⃣Инициализировать счетчик нулей значением k для учета первого появления единицы.

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int count = k;
        for (int num : nums) {
            if (num == 1) {
                if (count < k) {
                    return false;
                }
                count = 0;
            } else {
                count++;
            }
        }
        return true;
    }
};

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

Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

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

Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.

Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

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

1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

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

3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost.

😎 Решение:

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        double totalCost = numeric_limits<double>::max();
        double currentTotalQuality = 0;
        vector<pair<double, int>> wageToQualityRatio;

        for (int i = 0; i < n; i++) {
            wageToQualityRatio.push_back({static_cast<double>(wage[i]) / quality[i], quality[i]});
        }

        sort(wageToQualityRatio.begin(), wageToQualityRatio.end());

        priority_queue<int> workers;

        for (auto& [ratio, q] : wageToQualityRatio) {
            workers.push(q);
            currentTotalQuality += q;

            if (workers.size() > k) {
                currentTotalQuality -= workers.top();
                workers.pop();
            }

            if (workers.size() == k) {
                totalCost = min(totalCost, currentTotalQuality * ratio);
            }
        }
        return totalCost;
    }
};

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

Задача: 81. Search in Rotated Sorted Array II
Сложность: medium

Дан отсортированный (возможно, с дубликатами) массив nums, подвергшийся ротации.
Нужно определить, содержится ли число target в этом массиве.
Необходимо минимизировать количество операций поиска.

Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

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

1⃣Используем модифицированный бинарный поиск с указателями start и end.

2⃣В каждой итерации:
Если nums[mid] == target, возвращаем true
Если nums[mid] == nums[start], бинарный поиск невозможен — сдвигаем start++
Определяем, находится ли nums[mid] и target в одной отсортированной половине:
Если да — продолжаем обычный бинарный поиск
Если нет — двигаем в нужную сторону, зная, что целевой элемент в другой части

3⃣Повторяем до start > end.

😎 Решение:

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return false;
        int end = n - 1;
        int start = 0;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return true;
            }

            if (!isBinarySearchHelpful(nums, start, nums[mid])) {
                start++;
                continue;
            }

            bool pivotArray = existsInFirst(nums, start, nums[mid]);
            bool targetArray = existsInFirst(nums, start, target);

            if (pivotArray ^ targetArray) {
                if (pivotArray) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                if (nums[mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return false;
    }

    bool isBinarySearchHelpful(vector<int>& nums, int start, int element) {
        return nums[start] != element;
    }

    bool existsInFirst(vector<int>& nums, int start, int element) {
        return nums[start] <= element;
    }
};

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

Задача: 868. Binary Gap
Сложность: easy

Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.

Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.

Пример:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

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

1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1.

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

3⃣Верните найденное максимальное расстояние.

😎 Решение:

class Solution {
public:
    int binaryGap(int N) {
        int A[32], t = 0;
        for (int i = 0; i < 32; ++i)
            if ((N >> i) & 1)
                A[t++] = i;

        int ans = 0;
        for (int i = 0; i < t - 1; ++i)
            ans = max(ans, A[i + 1] - A[i]);
        return ans;
    }
};

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

Задача: 227. Basic Calculator II
Сложность: medium

Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.
Целочисленное деление должно округляться к нулю.
Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval().

Пример:

Input: s = "3+2*2"
Output: 7

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

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

2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации.

3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки.

😎 Решение:

class Solution {
public:
    int calculate(string s) {
        int length = s.length();
        if (length == 0) return 0;
        int currentNumber = 0, lastNumber = 0, result = 0;
        char sign = '+';
        
        for (int i = 0; i < length; i++) {
            char currentChar = s[i];
            if (isdigit(currentChar)) {
                currentNumber = (currentNumber * 10) + (currentChar - '0');
            }
            if (!isdigit(currentChar) && !iswspace(currentChar) || i == length - 1) {
                if (sign == '+' || sign == '-') {
                    result += lastNumber;
                    lastNumber = (sign == '+') ? currentNumber : -currentNumber;
                } else if (sign == '*') {
                    lastNumber = lastNumber * currentNumber;
                } else if (sign == '/') {
                    lastNumber = lastNumber / currentNumber;
                }
                sign = currentChar;
                currentNumber = 0;
            }
        }
        result += lastNumber;
        return result;  
    }
};

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

Задача: 939. Minimum Area Rectangle
Сложность: medium

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

Пример:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

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

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

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

3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь.

😎 Решение:

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_set<string> pointSet;
        for (auto& point : points) {
            pointSet.insert(to_string(point[0]) + "," + to_string(point[1]));
        }
        
        int minArea = INT_MAX;
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2 && pointSet.count(to_string(x1) + "," + to_string(y2)) && pointSet.count(to_string(x2) + "," + to_string(y1))) {
                    minArea = min(minArea, abs(x2 - x1) * abs(y2 - y1));
                }
            }
        }
        
        return minArea == INT_MAX ? 0 : minArea;
    }
};

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

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

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000)

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

1⃣Итерируем по числу, по 8 бит за раз. Извлекаем байт с помощью n & 0xff.

2⃣Каждый байт переворачиваем с помощью вспомогательной функции reverseByte, которая использует битовые маски и мемоизацию для ускорения.

3⃣Полученные байты сдвигаем на соответствующие позиции в результирующем числе и суммируем.

😎 Решение:

class Solution {
public:
    uint32_t reverseByte(uint32_t byte, map<uint32_t, uint32_t> cache) {
        if (cache.find(byte) != cache.end()) {
            return cache[byte];
        }
        uint32_t value = (byte * 0x0202020202 & 0x010884422010) % 1023;
        cache.emplace(byte, value);
        return value;
    }

    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0, power = 24;
        map<uint32_t, uint32_t> cache;
        while (n != 0) {
            ret += reverseByte(n & 0xff, cache) << power;
            n = n >> 8;
            power -= 8;
        }
        return ret;
    }
};

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

Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium

Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.

Если общего элемента нет, верните -1.

Пример:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

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

1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.

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

3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.

😎 Решение:

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int> pos(n, 0);
        int cur_max = 0, cnt = 0;
        
        while (true) {
            for (int i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (mat[i][pos[i]] != cur_max) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt == n) {
                    return cur_max;
                }
            }
        }
    }
};

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

Задача: 917. Reverse Only Letters
Сложность: easy

Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания.

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1⃣Создать массив для хранения только английских букв из строки s.

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

class Solution {
public:
    string reverseOnlyLetters(string s) {
        vector<char> letters;
        for (char c : s) {
            if (isalpha(c)) {
                letters.push_back(c);
            }
        }
        reverse(letters.begin(), letters.end());
        string result;
        int idx = 0;
        for (char c : s) {
            if (isalpha(c)) {
                result += letters[idx++];
            } else {
                result += c;
            }
        }
        return result;
    }
};

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

Задача: 640. Solve the Equation
Сложность: medium

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='.

2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений.

3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

class Solution {
public:
    string solveEquation(string equation) {
        auto parse = [](const string& s) {
            int coeff = 0, constPart = 0, sign = 1, num = 0;
            int i = 0;
            while (i < s.size()) {
                if (s[i] == '+') {
                    sign = 1;
                    i++;
                } else if (s[i] == '-') {
                    sign = -1;
                    i++;
                } else if (isdigit(s[i])) {
                    num = 0;
                    while (i < s.size() && isdigit(s[i])) {
                        num = num * 10 + (s[i] - '0');
                        i++;
                    }
                    if (i < s.size() && s[i] == 'x') {
                        coeff += sign * num;
                        i++;
                    } else {
                        constPart += sign * num;
                    }
                } else if (s[i] == 'x') {
                    coeff += sign;
                    i++;
                }
            }
            return make_pair(coeff, constPart);
        };

        auto [leftCoeff, leftConst] = parse(equation.substr(0, equation.find('=')));
        auto [rightCoeff, rightConst] = parse(equation.substr(equation.find('=') + 1));

        int coeff = leftCoeff - rightCoeff;
        int constPart = rightConst - leftConst;

        if (coeff == 0) {
            return constPart == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + to_string(constPart / coeff);
    }
};

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

Задача: 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 {
    fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
        val toDeleteSet = to_delete.toSet()
        val forest = mutableListOf<TreeNode?>()

        fun processNode(node: TreeNode?): TreeNode? {
            if (node == null) return null

            node.left = processNode(node.left)
            node.right = processNode(node.right)

            if (toDeleteSet.contains(node.`val`)) {
                node.left?.let { forest.add(it) }
                node.right?.let { forest.add(it) }
                return null
            }
            return node
        }

        val root = processNode(root)
        if (root != null) forest.add(root)

        return forest
    }
}

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

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

using namespace std;

class MyHeapNode {
public:
    int row;
    int column;
    int value;

    MyHeapNode(int v, int r, int c) : value(v), row(r), column(c) {}
};

class MyHeapComparator {
public:
    bool operator()(const MyHeapNode& x, const MyHeapNode& y) const {
        return x.value > y.value;
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int N = matrix.size();

        priority_queue<MyHeapNode, vector<MyHeapNode>, MyHeapComparator> minHeap;

        for (int r = 0; r < min(N, k); r++) {
            minHeap.push(MyHeapNode(matrix[r][0], r, 0));
        }

        MyHeapNode element = minHeap.top();
        while (k-- > 0) {
            element = minHeap.top();
            minHeap.pop();
            int r = element.row, c = element.column;

            if (c < N - 1) {
                minHeap.push(MyHeapNode(matrix[r][c + 1], r, c + 1));
            }
        }

        return element.value;
    }
};

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

Задача: 1469. Find All The Lonely Nodes
Сложность: easy

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

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

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void DFS(TreeNode* root, bool isLonely, vector<int>& ans) {
        if (root == NULL) {
            return;
        }
        
        if (isLonely) {
            ans.push_back(root->val);
        }
        
        DFS(root->left, root->right == NULL, ans);
        DFS(root->right, root->left == NULL, ans);
    }
    
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> ans;
        DFS(root, false, ans);
        return ans;
    }
};

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

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

Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
    vector<vector<int>> memo;
    int done;
    int n;
    const int MOD = 1000000007;
    unordered_map<int, vector<int>> hatsToPeople;
    
public:
    int numberWays(vector<vector<int>>& hats) {
        n = hats.size();
        
        for (int i = 0; i < n; i++) {
            for (int hat: hats[i]) {
                hatsToPeople[hat].push_back(i);
            }
        }
        
        done = (1 << n) - 1;
        memo = vector<vector<int>>(41, vector<int>(done, -1));
        
        return dp(1, 0);
    }
    
private:
    int dp(int hat, int mask) {
        if (mask == done) {
            return 1;
        }
        
        if (hat > 40) {
            return 0;
        }
        
        if (memo[hat][mask] != -1) {
            return memo[hat][mask];
        }
        
        int ans = dp(hat + 1, mask);
        
        if (hatsToPeople.count(hat)) {
            for (int person: hatsToPeople[hat]) {
                if ((mask & (1 << person)) == 0) {
                    ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD;
                }
            }
        }
        
        memo[hat][mask] = ans;
        return ans;
    }
};

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

Задача: 776. Split BST
Сложность: medium

Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.

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

Верните массив из двух корней двух поддеревьев в порядке.

Пример:

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

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

1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое.

2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

😎 Решение:

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode*> splitBST(TreeNode* root, int target) {
        if (!root) {
            return {nullptr, nullptr};
        }

        if (root->val > target) {
            auto left = splitBST(root->left, target);
            root->left = left[1];
            return {left[0], root};
        } else {
            auto right = splitBST(root->right, target);
            root->right = right[0];
            return {root, right[1]};
        }
    }
};

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<unordered_set<int>> components;
        unordered_set<int> visited;
        
        auto dfs = [&](int node) {
            stack<int> stk;
            stk.push(node);
            unordered_set<int> component;
            while (!stk.empty()) {
                int u = stk.top();
                stk.pop();
                if (!visited.count(u)) {
                    visited.insert(u);
                    component.insert(u);
                    for (int v = 0; v < n; ++v) {
                        if (graph[u][v] == 1 && !visited.count(v)) {
                            stk.push(v);
                        }
                    }
                }
            }
            components.push_back(component);
        };
        
        for (int i = 0; i < n; ++i) {
            if (!visited.count(i)) {
                dfs(i);
            }
        }
        
        vector<int> infectedInComponent(components.size(), 0);
        vector<int> nodeToComponent(n, -1);
        
        for (int i = 0; i < components.size(); ++i) {
            for (int node : components[i]) {
                nodeToComponent[node] = i;
                if (find(initial.begin(), initial.end(), node) != initial.end()) {
                    infectedInComponent[i]++;
                }
            }
        }
        
        int minInfected = INT_MAX;
        int resultNode = *min_element(initial.begin(), initial.end());
        
        for (int node : initial) {
            int componentIdx = nodeToComponent[node];
            if (infectedInComponent[componentIdx] == 1) {
                int componentSize = components[componentIdx].size();
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize;
                    resultNode = node;
                }
            }
        }
        
        return resultNode;
    }
};

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

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

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums, secondLen, firstLen));
    }
    
private:
    int maxSumNonOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<int> max_first(n, 0);
        for (int i = firstLen - 1; i < n; ++i) {
            max_first[i] = max((i > 0 ? max_first[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
        }
        
        vector<int> max_second(n, 0);
        for (int i = secondLen - 1; i < n; ++i) {
            max_second[i] = max((i > 0 ? max_second[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
        }
        
        int max_sum = 0;
        for (int i = firstLen + secondLen - 1; i < n; ++i) {
            max_sum = max(max_sum, max_first[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
        }
        
        return max_sum;
    }
};

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

Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

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

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* random;

    Node(int _val) {
        val = _val;
        left = nullptr;
        right = nullptr;
        random = nullptr;
    }
};

class NodeCopy {
public:
    int val;
    NodeCopy* left;
    NodeCopy* right;
    NodeCopy* random;

    NodeCopy(int _val) {
        val = _val;
        left = nullptr;
        right = nullptr;
        random = nullptr;
    }
};

class Solution {
    unordered_map<Node*, NodeCopy*> newOldPairs;

    NodeCopy* deepCopy(Node* root) {
        if (!root) return nullptr;
        NodeCopy* newRoot = new NodeCopy(root->val);
        newRoot->left = deepCopy(root->left);
        newRoot->right = deepCopy(root->right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }

    void mapRandomPointers(Node* oldNode) {
        if (!oldNode) return;
        NodeCopy* newNode = newOldPairs[oldNode];
        if (newNode) {
            newNode->random = newOldPairs[oldNode->random];
            mapRandomPointers(oldNode->left);
            mapRandomPointers(oldNode->right);
        }
    }

public:
    NodeCopy* copyRandomBinaryTree(Node* root) {
        NodeCopy* newRoot = deepCopy(root);
        mapRandomPointers(root);
        return newRoot;
    }
};

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

Задача: 334. Increasing Triplet Subsequence
Сложность: medium

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.

😎 Решение:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first_num = INT_MAX;
        int second_num = INT_MAX;
        
        for (int n : nums) {
            if (n <= first_num) {
                first_num = n;
            } else if (n <= second_num) {
                second_num = n;
            } else {
                return true;
            }
        }
        return false;
    }
};

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

Задача: №29. Divide Two Integers
Сложность: medium

Учитывая два целых числа dividend и divisor, выполните целочисленное деление без использования операторов *, / и %. Округление результата должно быть в сторону нуля. Если результат выходит за пределы 32-битного диапазона знаковых целых чисел — верните INT_MAX или INT_MIN.

Пример:

Input: dividend = 10, divisor = 3 Output: 3

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

1⃣Выполняем деление как есть, используя dividend / divisor, но предварительно кастуем к long long, чтобы избежать переполнения.

2⃣Проверяем результат: если он превышает диапазон [-2^31, 2^31 - 1], возвращаем соответствующую границу.

3⃣Возвращаем результат, округлённый к нулю.

😎 Решение:

class Solution {
public:
  int divide(int dividend, int divisor) {
    long long result = (long long)dividend / divisor;

    if(result > INT_MAX) return INT_MAX;
    if(result < INT_MIN) return INT_MIN;

    return result;
  }
};

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