Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"
Output: true

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

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 3 != 0) {
            return false;
        }

        stack<char> stk;
        for (char ch : s) {
            if (ch == 'c') {
                if (stk.size() < 2 || stk.top() != 'b') {
                    return false;
                }
                stk.pop();
                if (stk.top() != 'a') {
                    return false;
                }
                stk.pop();
            } else {
                stk.push(ch);
            }
        }

        return stk.empty();
    }
};

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

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

Дан массив nums, отсортированный по возрастанию и повернутый на некотором неизвестном индексе. Необходимо найти индекс элемента target. Если он не найден — вернуть -1. Решение должно работать за O(log n).

Пример:

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

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

1⃣Инициализируем границы бинарного поиска: left = 0, right = n-1.

2⃣В цикле проверяем значение в середине. Если совпадает с target — возвращаем индекс.

3⃣Определяем, какая половина массива отсортирована, и сужаем поиск к той части, где может находиться target.

😎 Решение:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            if (nums[m] == target) {
                return m;
            }
            if (nums[left] <= nums[m]) { // левая часть отсортирована
                if (nums[left] <= target && target < nums[m]) {
                    right = m - 1;
                } else {
                    left = m + 1;
                }
            } else { // правая часть отсортирована
                if (nums[m] < target && target <= nums[right]) {
                    left = m + 1;
                } else {
                    right = m - 1;
                }
            }
        }
        return -1;
    }
};

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

Задача: 1133. Largest Unique Number
Сложность: easy

Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.

Пример:

Input: nums = [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

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

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

2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа.

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

😎 Решение:

class Solution {
public:
    int largestUniqueNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        
        for (int num : nums) {
            count[num]++;
        }
        
        int result = -1;
        for (auto& entry : count) {
            if (entry.second == 1) {
                result = max(result, entry.first);
            }
        }
        
        return result;
    }
};

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

Задача: 249. Group Shifted Strings
Сложность: medium

Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

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

1⃣Для каждой строки вычисляем нормализованный ключ, сдвигая строку так, чтобы она начиналась с 'a'. Используем формулу (буква - сдвиг + 26) % 26 + 'a'.

2⃣Сохраняем строки в unordered_map, где ключом служит нормализованная строка, а значением — список всех строк, попадающих под эту группу.

3⃣Формируем результат из всех списков строк, сгруппированных по ключу, и возвращаем его.

😎 Решение:

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

class Solution {
public:
    char shiftLetter(char letter, int shift) {
        return (letter - shift + 26) % 26 + 'a';
    }
    
    string getHash(string& s) {
        int shift = s[0];
        string hashKey;
        for (char letter : s) {
            hashKey += shiftLetter(letter, shift);
        }
        return hashKey;
    }
    
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> mapHashToList;
        for (string& str : strings) {
            string hashKey = getHash(str);
            mapHashToList[hashKey].push_back(str);
        }

        vector<vector<string>> groups;
        for (auto& it : mapHashToList) {
            groups.push_back(it.second);
        }

        return groups;
    }
};

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

Задача: 722. Remove Comments
Сложность: medium

Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.

Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.

Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.

2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.

3⃣После обработки всех строк добавьте непустые строки из buffer в результат.

😎 Решение:

vector<string> removeComments(vector<string>& source) {
    bool inBlock = false;
    string buffer;
    vector<string> result;
    
    for (const string& line : source) {
        int i = 0;
        if (!inBlock) buffer.clear();
        while (i < line.size()) {
            if (!inBlock && i + 1 < line.size() && line[i] == '/' && line[i + 1] == '*') {
                inBlock = true;
                i++;
            } else if (inBlock && i + 1 < line.size() && line[i] == '*' && line[i + 1] == '/') {
                inBlock = false;
                i++;
            } else if (!inBlock && i + 1 < line.size() && line[i] == '/' && line[i + 1] == '/') {
                break;
            } else if (!inBlock) {
                buffer.push_back(line[i]);
            }
            i++;
        }
        if (!inBlock && !buffer.empty()) {
            result.push_back(buffer);
        }
    }
    return result;
}

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

Задача: 1199. Minimum Time to Build Blocks
Сложность: hard

Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.

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

Изначально есть только один рабочий.

Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.

2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.

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

😎 Решение:

#include <vector>
#include <queue>

class Solution {
public:
    int minBuildTime(std::vector<int>& blocks, int split) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq(blocks.begin(), blocks.end());
        
        while (pq.size() > 1) {
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
            pq.push(split + y);
        }
        
        return pq.top();
    }
};

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

Задача: 869. Reordered Power of 2
Сложность: medium

Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.

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

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.

😎 Решение:

class Solution {
public:
    bool reorderedPowerOf2(int N) {
        string A = to_string(N);
        sort(A.begin(), A.end());
        for (int i = 0; i < 30; ++i) {
            string B = to_string(1 << i);
            sort(B.begin(), B.end());
            if (A == B) return true;
        }
        return false;
    }
};

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

Задача: 83. Remove Duplicates from Sorted List
Сложность: easy

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

Пример:

Input: head = [1,1,2]
Output: [1,2]

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

1⃣Начинаем с текущего узла current = head и двигаемся по списку, пока current и current->next не равны NULL.

2⃣Если current->val == current->next->val, это дубликат — пропускаем next, сдвигая current->next = current->next->next.

3⃣Если значения различаются — просто переходим к следующему узлу: current = current->next.

😎 Решение:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* current = head;
        while (current != NULL && current->next != NULL) {
            if (current->next->val == current->val) {
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }
        return head;
    }
};

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

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

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением.

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

😎 Решение:

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int numsSize = nums.size();
        
        if (numsSize <= 4) return 0;
        
        sort(nums.begin(), nums.end());
        
        int minDiff = INT_MAX;
        
        for (int left = 0, right = numsSize - 4; left < 4; left++, right++) {
            minDiff = min(minDiff, nums[right] - nums[left]);
        }
        
        return minDiff;
    }
};

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

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy

Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника.

Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты.

Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

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

1⃣Инициализация переменных:
Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0.

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

3⃣Вычисление среднего значения:
Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности.

😎 Решение:

class Solution {
public:
    double average(vector<int>& salary) {
        int minSalary = INT_MAX;
        int maxSalary = INT_MIN;
        int sum = 0;

        for (int sal : salary) {
            sum += sal;
            minSalary = min(minSalary, sal);
            maxSalary = max(maxSalary, sal);
        }

        return (sum - minSalary - maxSalary) / static_cast<double>(salary.size() - 2);
    }
};

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

Задача: 22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных круглых скобок.

Пример:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

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

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

2⃣Добавляем открытую скобку, если их количество меньше n.

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

😎 Решение:

class Solution { 
public: 
    vector<string> res; 
 
    void dfs(string cur, int open, int close, int n) 
    { 
        if (cur.length() == 2 * n) 
        { 
            if (open == close) res.push_back(cur); 
            return; 
        } 
 
        if (open < n) dfs(cur + "(", open + 1, close, n); 
        if (open > close) dfs(cur + ")", open, close + 1, n); 
    } 
 
    vector<string> generateParenthesis(int n) { 
        dfs("", 0, 0, n); 
        return res; 
    } 
};

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

Задача: 976. Largest Perimeter Triangle
Сложность: easy

Дан целочисленный массив nums. Верните наибольший периметр треугольника с ненулевой площадью, образованный из трех этих длин. Если невозможно образовать треугольник с ненулевой площадью, верните 0.

Пример:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

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

1⃣Отсортируйте массив nums в порядке возрастания.

2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника.

3⃣Если не удалось найти такие значения, верните 0.

😎 Решение:

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = A.size() - 3; i >= 0; --i)
            if (A[i] + A[i + 1] > A[i + 2])
                return A[i] + A[i + 1] + A[i + 2];
        return 0;
    }
};

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

Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard

Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

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

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

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

😎 Решение:

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

class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        stack<TreeNode*> stk;
        for (int i = 0; i < S.size();) {
            int level = 0;
            while (i < S.size() && S[i] == '-') {
                level++;
                i++;
            }
            
            int value = 0;
            while (i < S.size() && isdigit(S[i])) {
                value = value * 10 + (S[i] - '0');
                i++;
            }
            
            TreeNode* node = new TreeNode(value);
            if (level == stk.size()) {
                if (!stk.empty()) {
                    stk.top()->left = node;
                }
            } else {
                while (level != stk.size()) {
                    stk.pop();
                }
                stk.top()->right = node;
            }
            stk.push(node);
        }
        
        while (stk.size() > 1) {
            stk.pop();
        }
        
        return stk.top();
    }
};

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

Задача: 94. Binary Tree Inorder Traversal
Сложность: easy

Дан корень бинарного дерева.
Верните обход значений его узлов в симметричном порядке (inorder):
лево → корень → право

Пример:

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

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

1⃣Определим вспомогательную функцию helper, которая выполняет рекурсивный обход дерева.

2⃣Если текущий узел root не равен NULL,
сначала вызываем helper(root->left), затем добавляем root->val,
после чего вызываем helper(root->right).

3⃣Используем вектор res для хранения результата обхода.

😎 Решение:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root, res);
        return res;
    }

    void helper(TreeNode* root, vector<int>& res) {
        if (root != NULL) {
            helper(root->left, res);
            res.push_back(root->val);
            helper(root->right, res);
        }
    }
};

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

Задача: 88. Merge Sorted Array
Сложность: easy

Даны два отсортированных массива nums1 и nums2,
а также числа m и n, обозначающие количество значимых элементов в них.
Необходимо слить nums2 в nums1, получив отсортированный массив на месте.
nums1 имеет размер m + n, где последние n элементов — нули-заполнители.

Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

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

1⃣Создаем копию первых m элементов nums1 → nums1Copy.
Инициализируем два указателя p1 = 0, p2 = 0 — для чтения nums1Copy и nums2.

2⃣Используем один указатель p для записи в nums1.
Пока p < m + n, на каждой итерации сравниваем nums1Copy[p1] и nums2[p2].

3⃣Меньшее из значений записываем в nums1[p]. Увеличиваем соответствующий указатель.
Если один из массивов исчерпан, продолжаем с оставшегося.

😎 Решение:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums1Copy(nums1.begin(), nums1.begin() + m);
        int p1 = 0;
        int p2 = 0;

        for (int p = 0; p < m + n; p++) {
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
};

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

Задача: 16. 3Sum Closest
Сложность: medium

Дан массив целых чисел nums и целое число target.
Найди такую тройку чисел в массиве, сумма которых наиболее близка к target, и верни эту сумму.
Гарантируется, что только одно решение существует.

Пример:

Input: nums = [-1,2,1,-4], target = 1
Output: 2

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

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

2⃣Для каждого числа nums[i], зафиксировать его и искать пару чисел в подмассиве справа с помощью двух указателей (front, back), чтобы сумма тройки была ближе всего к target.

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

😎 Решение:

class Solution { 
public: 
    int threeSumClosest(vector<int>& nums, int target) { 
        sort(nums.begin(), nums.end()); 
        int sum = nums[0] + nums[1] + nums[2]; 
        int sum1 = 0; 
        
        for (int i = 0; i < nums.size(); i++) { 
            int front = i + 1; 
            int back = nums.size() - 1; 
            
            while (front < back) { 
                sum1 = nums[i] + nums[front] + nums[back]; 
                
                if (abs(sum1 - target) <= abs(sum - target)) { 
                    sum = sum1; 
                } 
                
                if (sum1 > target)  
                    back--; 
                else if (sum1 < target)  
                    front++; 
                else 
                    return sum1; 
            } 
        } 
        return sum; 
    } 
};

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

Задача: 267. Palindrome Permutation II
Сложность: medium

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

1⃣Подсчёт частоты символов
Создаем хеш-таблицу частот. Если количество символов с нечетной частотой больше 1 — палиндром невозможен.

2⃣Формирование первой половины
Из каждого символа берём его частоту пополам и формируем строку half. Символ с нечетной частотой (если есть) сохраняем как центральный.

3⃣Генерация палиндромов
С помощью backtracking создаём все уникальные перестановки строки half, дополняем их зеркально. Если есть центральный символ — добавляем его в середину.

😎 Решение:

class Solution {
private:
    void backtrack(string& half, vector<bool>& used, string& path, string& mid, vector<string>& res) {
        if (path.size() == half.size()) {
            string rev = path;
            reverse(rev.begin(), rev.end());
            res.push_back(path + mid + rev);
            return;
        }

        for (int i = 0; i < half.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(half[i]);
            backtrack(half, used, path, mid, res);
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;

        int oddCount = 0;
        string mid = "", half = "";
        for (auto& [ch, count] : freq) {
            if (count % 2 != 0) {
                oddCount++;
                mid = ch;
            }
            half += string(count / 2, ch);
        }

        if (oddCount > 1) return {};

        sort(half.begin(), half.end());
        vector<string> res;
        vector<bool> used(half.size(), false);
        string path;
        backtrack(half, used, path, mid, res);
        return res;
    }
};

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

Задача: 380. Insert Delete GetRandom O(1)
Сложность: medium

Реализуйте класс RandomizedSet:
RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.

Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

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

1⃣Создать словарь для хранения значений и их индексов, а также список для хранения значений.

2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.

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

😎 Решение:

using namespace std;

class RandomizedSet {
public:
    RandomizedSet() {}

    bool insert(int val) {
        if (dict.find(val) != dict.end()) {
            return false;
        }
        dict[val] = list.size();
        list.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (dict.find(val) == dict.end()) {
            return false;
        }
        int index = dict[val];
        int lastElement = list.back();
        list[index] = lastElement;
        dict[lastElement] = index;
        list.pop_back();
        dict.erase(val);
        return true;
    }

    int getRandom() {
        int randomIndex = rand() % list.size();
        return list[randomIndex];
    }

private:
    unordered_map<int, int> dict;
    vector<int> list;
};

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

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

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

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

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
public:
    int maxTime = INT_MIN;
    
    void DFS(vector<int> adjList[], vector<int>& informTime, int curr, int time) {
        maxTime = max(maxTime, time);
        for (int adjacent : adjList[curr]) { 
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<int> adjList[n];
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].push_back(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
};

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

Задача: 531. Lonely Pixel I
Сложность: medium

Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей.
Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей.

Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

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

1⃣ Подсчёт количества чёрных пикселей в строках и столбцах:
Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1.

2⃣ Поиск одиночных чёрных пикселей:
Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1.

3⃣ Возврат результата:
Верните answer.

😎 Решение:

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = picture.size();
        int m = picture[0].size();
        
        vector<int> rowCount(n, 0);
        vector<int> columnCount(m, 0);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    columnCount[j]++;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && columnCount[j] == 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
};

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

Задача: 1539. Kth Missing Positive Number
Сложность: easy

Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение:

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
};

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