C/C++ | LeetCode

Задача: 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;
    }
};

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

Задача: 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;
        });
    }
};

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

Задача: 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;
    }
};

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

Задача: 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]);
    }
};

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

Задача: 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;
    }
};

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

"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы Дело в том, что онлайн школы создают инкубаторных айтишников, которые в реальных условиях попросту зависнут. Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера: ⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти 🧠 Ai-чница – способы превратить нейросети в заработок $$$ 💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями 4️⃣ Войти в IT – тонны бесплатного обучения для прогеров 😄 IT индус – сборник айти мемов

Задача: 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;
    }
};

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

Айтишники, это вам — в телеграм есть комьюнити по каждому направлению в IT Там есть буквально всё: чаты для общения, тонны материала(книги, курсы, ресурсы и гайды), свежие новости и конечно же мемы Выбирайте своё направление: 💩 Frontend 🐍 Python 🐧 Linux 👩‍💻 С/С++ 👩‍💻 C# 🤔 Хакинг & ИБ 📱 GitHub 🖥 SQL 👩‍💻 Сисадмин 🤟 DevOps ⚙️ Backend 🖥 Data Science 🧑‍💻 Java 🐞 Тестирование 🖥 PM / PdM 👩‍💻 GameDev 🧑‍💻 Golang 🤵‍♂️ IT-Митапы 🧑‍💻 PHP 💻 WebDev 🖥 Моб. Dev 🖥Анали.(SA&BA) 👩‍💻 Дизайн 🖥 Нейросети 💛 1C 🤓 Книги IT ➡️ Сохраняйте в закладки

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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]));
    }
};

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

Задача: 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;
    }
};

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

Задача: 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]--;
    }
};

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной 📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 1268. Search Suggestions System Сложность: medium Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord. Пример:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

👨‍💻 Алгоритм: 1⃣Отсортируйте массив продуктов. 2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу. 3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса. 😎 Решение:

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        vector<vector<string>> result;
        string prefix = "";
        for (char c : searchWord) {
            prefix += c;
            vector<string> suggestions;
            for (const string& product : products) {
                if (product.find(prefix) == 0) {
                    suggestions.push_back(product);
                    if (suggestions.size() == 3) break;
                }
            }
            result.push_back(suggestions);
        }
        return result;
    }
};

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

Задача: 786. K-th Smallest Prime Fraction Сложность: medium Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k. Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j]. Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j]. Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

👨‍💻 Алгоритм: 1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей. 2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью. 3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби. 😎 Решение:

#include <queue>
#include <vector>

class Solution {
public:
    std::vector<int> kthSmallestPrimeFraction(std::vector<int>& arr, int k) {
        auto comp = [&arr](std::pair<int, int>& a, std::pair<int, int>& b) {
            return arr[a.first] * arr[b.second] > arr[a.second] * arr[b.first];
        };
        
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(comp)> pq(comp);
        
        for (int i = 0; i < arr.size() - 1; i++) {
            pq.emplace(i, arr.size() - 1);
        }
        
        for (int i = 0; i < k - 1; i++) {
            auto [numeratorIndex, denominatorIndex] = pq.top();
            pq.pop();
            if (denominatorIndex - 1 > numeratorIndex) {
                pq.emplace(numeratorIndex, denominatorIndex - 1);
            }
        }
        
        auto [numeratorIndex, denominatorIndex] = pq.top();
        return {arr[numeratorIndex], arr[denominatorIndex]};
    }
};

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

Задача: 44. Wildcard Matching Сложность: hard Дана входная строка s и шаблон p, реализуйте сопоставление с шаблоном с поддержкой символов: ? — соответствует любому одиночному символу * — соответствует любой последовательности символов (включая пустую) Сопоставление должно покрывать всю строку. Пример:

Input: s = "aa", p = "a" Output: false

👨‍💻 Алгоритм: 1⃣Удалить дубликаты звёздочек (** → *), т.к. они не дают дополнительной информации 2⃣Реализовать рекурсивную функцию helper, используя мемоизацию, чтобы избежать повторных вычислений 3⃣Обрабатывать шаблон по следующим правилам: Если p[i] == s[i] или p[i] == '?' → рекурсивно перейти к следующей паре Если p[i] == '*' → два варианта: пропустить * или сопоставить с символом строки Иначе — несовпадение 😎 Решение:

class Solution {
public:
    unordered_map<string, bool> dp;
    string p;
    string s;

    string remove_duplicate_stars(string p) {
        string new_string = "";
        for (auto &c : p) {
            if (new_string.empty() || c != '*')
                new_string += c;
            else if (new_string.back() != '*')
                new_string += c;
        }
        return new_string;
    }

    bool helper(int si, int pi) {
        string key = to_string(si) + "," + to_string(pi);
        if (dp.count(key)) return dp[key];
        
        if (pi == p.size())
            dp[key] = (si == s.size());
        else if (si == s.size())
            dp[key] = (pi + 1 == p.size() && p[pi] == '*');
        else if (p[pi] == s[si] || p[pi] == '?')
            dp[key] = helper(si + 1, pi + 1);
        else if (p[pi] == '*')
            dp[key] = helper(si, pi + 1) || helper(si + 1, pi);
        else
            dp[key] = false;

        return dp[key];
    }

    bool isMatch(string s, string p) {
        dp.clear();
        this->s = s;
        this->p = remove_duplicate_stars(p);
        return helper(0, 0);
    }
};

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

Задача: 955. Delete Columns to Make Sorted II Сложность: medium Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки. Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length. Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

👨‍💻 Алгоритм: 1⃣Определить количество строк n и длину каждой строки m. Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов. 2⃣Итеративно проверить каждую пару соседних строк для всех столбцов. Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления. 3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным. Вернуть количество удаленных столбцов. 😎 Решение:

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size();
        int m = strs[0].length();
        vector<bool> deleteCount(m, false);
        
        auto isSorted = [&]() {
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < m; j++) {
                    if (deleteCount[j]) continue;
                    if (strs[i][j] > strs[i + 1][j]) return false;
                    if (strs[i][j] < strs[i + 1][j]) break;
                }
            }
            return true;
        };
        
        while (!isSorted()) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i][j] > strs[i + 1][j]) {
                        deleteCount[j] = true;
                        break;
                    }
                }
                if (deleteCount[j]) break;
            }
        }
        
        return count(deleteCount.begin(), deleteCount.end(), true);
    }
};

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