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

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

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

Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

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

1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0).

2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target].

3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его.

😎 Решение:

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int count = 0;
        int k = sum;
        unordered_map<int, int> h;
        preorder(root, 0, h, count, k);
        return count;
    }
    
    void preorder(TreeNode* node, int curr_sum, unordered_map<int, int>& h, int& count, int k) {
        if (!node) return;
        
        curr_sum += node->val;
        
        if (curr_sum == k) {
            count++;
        }
        
        count += h[curr_sum - k];
        
        h[curr_sum]++;
        
        preorder(node->left, curr_sum, h, count, k);
        preorder(node->right, curr_sum, h, count, k);
        
        h[curr_sum]--;
    }
};

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

Задача: 985. Sum of Even Numbers After Queries
Сложность: medium

Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi].

Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums.

Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос.

Пример:

Input: nums = [1], queries = [[4,0]]
Output: [0]

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

1⃣Инициализация переменных:
Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums.
Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums.

2⃣Обработка запросов:
Создать пустой массив result для хранения ответов на каждый запрос.
Для каждого запроса [val, index] из массива queries выполнить следующие действия:
Если значение nums[index] четное, вычесть его из evenSum.
Обновить nums[index] добавлением val.
Если новое значение nums[index] четное, добавить его к evenSum.
Добавить текущее значение evenSum в массив result.

3⃣Возврат результата:
Вернуть массив result, содержащий ответы на все запросы.

😎 Решение:

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int evenSum = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                evenSum += num;
            }
        }

        vector<int> result;
        for (const auto& query : queries) {
            int val = query[0], index = query[1];
            if (nums[index] % 2 == 0) {
                evenSum -= nums[index];
            }
            nums[index] += val;
            if (nums[index] % 2 == 0) {
                evenSum += nums[index];
            }
            result.push_back(evenSum);
        }
        
        return result;
    }
};

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

Задача: 968. Binary Tree Cameras
Сложность: hard

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

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

Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

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

1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.

2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.

3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.

😎 Решение:

class Solution {
public:
    int minCameraCover(TreeNode* root) {
        int ans[3];
        solve(root, ans);
        return min(ans[1], ans[2]);
    }

private:
    void solve(TreeNode* node, int* res) {
        if (!node) {
            res[0] = res[1] = 0;
            res[2] = 99999;
            return;
        }

        int L[3], R[3];
        solve(node->left, L);
        solve(node->right, R);

        res[0] = L[1] + R[1];
        res[1] = min(L[2] + min(R[1], R[2]), R[2] + min(L[1], L[2]));
        res[2] = 1 + min(L[0], min(L[1], L[2])) + min(R[0], min(R[1], R[2]));
    }
};

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

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

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

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

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

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freqMap;
        for (int num : arr) {
            freqMap[num]++;
        }
        
        vector<int> frequencies;
        for (auto& p : freqMap) {
            frequencies.push_back(p.second);
        }
        
        sort(frequencies.begin(), frequencies.end());
        
        int elementsRemoved = 0;
        for (int i = 0; i < frequencies.size(); ++i) {
            elementsRemoved += frequencies[i];
            if (elementsRemoved > k) {
                return frequencies.size() - i;
            }
        }
        
        return 0;
    }
};

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

Задача: 350. Intersection of Two Arrays II
Сложность: easy

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

Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

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

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

2⃣Нахождение пересечения:
Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик.

3⃣Возврат результата:
Верните массив пересечения.

😎 Решение:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> counts;
        vector<int> result;
        
        for (int num : nums1) {
            counts[num]++;
        }
        
        for (int num : nums2) {
            if (counts[num] > 0) {
                result.push_back(num);
                counts[num]--;
            }
        }
        
        return result;
    }
};

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

class Solution {
public:
    int reachTarget(int target) {
        target = abs(target);
        int position = 0;
        int steps = 0;
        while (position < target || (position - target) % 2 != 0) {
            steps++;
            position += steps;
        }
        return steps;
    }
};

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

Задача: 116. Populating Next Right Pointers in Each Node
Сложность: medium

Дано идеальное бинарное дерево. Нужно установить next-указатели так, чтобы каждый узел указывал на своего соседа справа. Если соседа нет — указатель должен быть nullptr.

Пример:

Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#]
Символ # означает конец уровня.

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

1⃣Используем очередь (queue<Node*>) для обхода дерева в ширину (BFS). Начинаем с корня.

2⃣На каждой итерации while, получаем size — количество узлов текущего уровня. Для всех узлов этого уровня:
Извлекаем узел из очереди.
Если это не последний узел уровня, устанавливаем node->next = Q.front().
Добавляем в очередь левого и правого потомков.

3⃣Повторяем, пока очередь не пуста.

😎 Решение:

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }

        queue<Node*> Q;
        Q.push(root);

        while (!Q.empty()) {
            int size = Q.size();

            for (int i = 0; i < size; i++) {
                Node* node = Q.front();
                Q.pop();

                if (i < size - 1) {
                    node->next = Q.front();
                }

                if (node->left != nullptr) {
                    Q.push(node->left);
                }

                if (node->right != nullptr) {
                    Q.push(node->right);
                }
            }
        }

        return root;
    }
};

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

class Solution {
public:
    string countOfAtoms(string formula) {
        stack<map<string, int>> stack;
        stack.push(map<string, int>());
        int n = formula.size();
        int i = 0;

        while (i < n) {
            if (formula[i] == '(') {
                stack.push(map<string, int>());
                i++;
            } else if (formula[i] == ')') {
                map<string, int> top = stack.top();
                stack.pop();
                i++;
                int start = i;
                while (i < n && isdigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? stoi(formula.substr(start, i - start)) : 1;
                for (const auto& [name, count] : top) {
                    stack.top()[name] += count * multiplicity;
                }
            } else {
                int start = i;
                i++;
                while (i < n && islower(formula[i])) {
                    i++;
                }
                string name = formula.substr(start, i - start);
                start = i;
                while (i < n && isdigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? stoi(formula.substr(start, i - start)) : 1;
                stack.top()[name] += multiplicity;
            }
        }

        map<string, int> countMap = stack.top();
        string result;
        for (const auto& [name, count] : countMap) {
            result += name;
            if (count > 1) {
                result += to_string(count);
            }
        }
        return result;
    }
};

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

Задача: 1125. Smallest Sufficient Team
Сложность: hard

В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.

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

Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.

Гарантируется, что ответ существует.

Пример:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],["algorithms","math","reactjs"],
["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

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

1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.

2⃣Динамическое программирование (DP):
Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1.
Установите dp[0] в 0 (базовый случай).
Для каждого skillsMask от 1 до 2^m - 1:
- для каждого человека i:
- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].
- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).

3⃣Формирование ответа:
Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду.

😎 Решение:

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = people.size(), m = req_skills.size();
        unordered_map<string, int> skillId;
        for (int i = 0; i < m; i++) {
            skillId[req_skills[i]] = i;
        }
        vector<int> skillsMaskOfPerson(n, 0);
        for (int i = 0; i < n; i++) {
            for (const string& skill : people[i]) {
                skillsMaskOfPerson[i] |= 1 << skillId[skill];
            }
        }
        vector<long> dp(1 << m, (1L << n) - 1);
        dp[0] = 0;
        for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
            for (int i = 0; i < n; i++) {
                int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
                if (smallerSkillsMask != skillsMask) {
                    long peopleMask = dp[smallerSkillsMask] | (1L << i);
                    if (__builtin_popcountll(peopleMask) < __builtin_popcountll(dp[skillsMask])) {
                        dp[skillsMask] = peopleMask;
                    }
                }
            }
        }
        long answerMask = dp[(1 << m) - 1];
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if ((answerMask >> i) & 1) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

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

Задача: 727. Minimum Window Subsequence
Сложность: hard

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

1⃣Используйте два указателя для определения текущего окна.

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

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

😎 Решение:

class Solution {
public:
    string minWindow(string s1, string s2) {
        if (s1.empty() || s2.empty()) {
            return "";
        }

        unordered_map<char, int> dictT;
        for (char c : s2) {
            dictT[c]++;
        }

        int required = dictT.size();
        int l = 0, r = 0, formed = 0;
        unordered_map<char, int> windowCounts;
        int ans[3] = {INT_MAX, 0, 0};

        while (r < s1.size()) {
            char c = s1[r];
            windowCounts[c]++;

            if (dictT.count(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1[l];

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.count(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == INT_MAX ? "" : s1.substr(ans[1], ans[0]);
    }
};

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

Задача: 508. Most Frequent Subtree Sum
Сложность: medium

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

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

Пример:

Input: root = [5,2,-3]
Output: [2,-3,4]

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

1⃣Инициализация переменных
Инициализируйте переменные sumFreq для хранения частоты всех сумм поддеревьев. Инициализируйте maxFreq для хранения максимальной частоты. Создайте массив maxFreqSums для хранения всех сумм поддеревьев, частота которых равна максимальной.

2⃣Обход дерева и вычисление сумм
Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

3⃣Сборка результата
Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎 Решение:

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>

using namespace std;

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

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int, int> sumFreq;
        int maxFreq = 0;
        
        function<int(TreeNode*)> subtreeSum = [&](TreeNode* node) {
            if (!node) return 0;
            int leftSum = subtreeSum(node->left);
            int rightSum = subtreeSum(node->right);
            int currSum = node->val + leftSum + rightSum;
            sumFreq[currSum]++;
            maxFreq = max(maxFreq, sumFreq[currSum]);
            return currSum;
        };
        
        subtreeSum(root);
        vector<int> result;
        for (const auto& [sum, freq] : sumFreq) {
            if (freq == maxFreq) {
                result.push_back(sum);
            }
        }
        return result;
    }
};

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

Задача: 935. Knight Dialer
Сложность: medium

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


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

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

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

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

class Solution {
public:
    int knightDialer(int n) {
        int MOD = 1000000007;
        vector<vector<int>> moves = {
            {4, 6},
            {6, 8},
            {7, 9},
            {4, 8},
            {0, 3, 9},
            {},
            {0, 1, 7},
            {2, 6},
            {1, 3},
            {2, 4}
        };
        
        vector<int> dp(10, 1);
        
        for (int step = 1; step < n; step++) {
            vector<int> newDp(10, 0);
            for (int i = 0; i < 10; i++) {
                for (int move : moves[i]) {
                    newDp[move] = (newDp[move] + dp[i]) % MOD;
                }
            }
            dp = newDp;
        }
        
        return accumulate(dp.begin(), dp.end(), 0, [&](int sum, int count) {
            return (sum + count) % MOD;
        });
    }
};

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.

😎 Решение:

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        size_t m = mat.size();
        size_t n = mat[0].size();

        map<int, priority_queue<int, vector<int>, greater<int>>> diagonals;

        for (size_t row = 0; row < m; row++) {
            for (size_t col = 0; col < n; col++) {
                diagonals[row - col].push(mat[row][col]);
            }
        }

        for (size_t row = 0; row < m; row++) {
            for (size_t col = 0; col < n; col++) {
                mat[row][col] = diagonals[row - col].top();
                diagonals[row - col].pop();
            }
        }

        return mat;
    }
};

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

Задача: 990. Satisfiability of Equality Equations
Сложность: medium

Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.

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

Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

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

1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.

2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.

3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.

😎 Решение:

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFind uf(26);
        
        for (const auto& eq : equations) {
            if (eq[1] == '=') {
                int x = eq[0] - 'a';
                int y = eq[3] - 'a';
                uf.unionSet(x, y);
            }
        }
        
        for (const auto& eq : equations) {
            if (eq[1] == '!') {
                int x = eq[0] - 'a';
                int y = eq[3] - 'a';
                if (uf.connected(x, y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
private:
    class UnionFind {
    public:
        UnionFind(int n) : parent(n) {
            iota(parent.begin(), parent.end(), 0);
        }
        
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        void unionSet(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
        
        bool connected(int x, int y) {
            return find(x) == find(y);
        }
        
    private:
        vector<int> parent;
    };
};

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 986. Interval List Intersections
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

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

1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

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

3⃣Возврат результата:
Вернуть список пересечений.

😎 Решение:

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        
        while (i < firstList.size() && j < secondList.size()) {
            int start = max(firstList[i][0], secondList[j][0]);
            int end = min(firstList[i][1], secondList[j][1]);
            
            if (start <= end) {
                result.push_back({start, end});
            }
            
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        
        return result;
    }
};

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