C/C++ | LeetCode

Задача: 907. Sum of Subarray Minimums Сложность: medium Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7. Пример:

Input: arr = [3,1,2,4]
Output: 17

👨‍💻 Алгоритм: 1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива. 2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным. 3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7. 😎 Решение:

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> left(n), right(n);
        stack<int> st;

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }
            left[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }

        while (!st.empty()) st.pop();

        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n - i : st.top() - i;
            st.push(i);
        }

        long long result = 0;
        for (int i = 0; i < n; ++i) {
            result = (result + (long long)arr[i] * left[i] * right[i]) % MOD;
        }

        return result;
    }
};

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

Задача: 507. Perfect Number Сложность: easy Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело. Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false. Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

👨‍💻 Алгоритм: 1⃣Инициализация Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0. 2⃣Поиск делителей и вычисление суммы Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель. 3⃣Проверка на совершенное число Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false. 😎 Решение:

 class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 0) return false;
        int sum = 0;
        for (int i = 1; i * i <= num; ++i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return sum - num == num;
    }
};

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

Задача: 229. Majority Element II Сложность: medium Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз. Пример:

Input: nums = [3,2,3]
Output: [3]

👨‍💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int count1 = 0, count2 = 0;
        int candidate1 = INT_MIN, candidate2 = INT_MIN;
        
        for (int n : nums) {
            if (candidate1 == n) {
                count1++;
            } else if (candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int n : nums) {
            if (candidate1 == n) count1++;
            if (candidate2 == n) count2++;
        }
        
        vector<int> result;
        int n = nums.size();
        if (count1 > n / 3) result.push_back(candidate1);
        if (count2 > n / 3) result.push_back(candidate2);
        
        return result;
    }
};

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

Задача: 956. Tallest Billboard Сложность: hard Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0. Пример:

Input: rods = [1,2,3,6]
Output: 6

👨‍💻 Алгоритм: 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);
    }
};

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

Задача: 1099. Two Sum Less Than K Сложность: easy Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1. Пример:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

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

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int answer = -1;
        int count[1001] = {};
        for (int num : nums) {
            count[num]++;
        }
        int lo = 1;
        int hi = 1000;
        while (lo <= hi) {
            if (lo + hi >= k || count[hi] == 0) {
                hi--;
            } else {
                if (count[lo] > (lo < hi ? 0 : 1)) {
                    answer = max(answer, lo + hi);
                }
                lo++;
            }
        }
        return answer;
    }
};

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

Задача: 101. Symmetric Tree Сложность: easy Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра). Пример:

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

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) { return isMirror(root, root); }
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        return (t1->val == t2->val) && isMirror(t1->right, t2->left) &&
               isMirror(t1->left, t2->right);
    }
};

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

🔥Стажировки и вакансии для IT специалистов - Вакансии которых нет на джоб-агрегаторах - Только прямые контакты HR в Telegram 🤖 ML & DS 👩‍💻 DevOps 👨‍✈️ ИБ & OSINT 👣 Go 👩‍💻 Mobile 👩‍💻 C# 👩‍💻 Node.js 👩‍💻 Python 🔎 QA 👩‍💻 Java 👩‍💻 UX/UI 👩‍💻 Frontend 🖼️ PHP 📋 Analyst 💼 1C 🖥 SQL 👩‍💻 IT HR Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.

Задача: 127. Word Ladder Сложность: hard Дано: beginWord, endWord и wordList. Найдите длину кратчайшей цепочки преобразования из beginWord в endWord, где каждое слово отличается ровно одной буквой, и каждое промежуточное слово должно быть в wordList. Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" → "hot" → "dot" → "dog" → "cog" — цепочка из 5 слов

👨‍💻 Алгоритм: 1⃣Преобразование слов: Для каждого слова из wordList формируем промежуточные состояния, заменяя по одной букве на *. Например, "hot" → "*ot", "h*t", "ho*". Сохраняем в unordered_map<string, vector<string>> allComboDict. 2⃣BFS: Стартуем с beginWord, кладем в очередь (beginWord, 1) — слово и уровень. Храним visited, чтобы не зациклиться. На каждом шаге: генерируем все промежуточные состояния *ot, h*t, ... смотрим в allComboDict, какие слова подходят добавляем их в очередь с level + 1 если встречаем endWord — возвращаем level + 1 3⃣Если очередь опустела, а endWord не найден — возвращаем 0. 😎 Решение:

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

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int L = beginWord.size();
        unordered_map<string, vector<string>> allComboDict;

        for (string word : wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.substr(0, i) + '*' + word.substr(i + 1);
                allComboDict[newWord].push_back(word);
            }
        }

        queue<pair<string, int>> Q;
        Q.push({beginWord, 1});
        unordered_map<string, bool> visited;
        visited[beginWord] = true;

        while (!Q.empty()) {
            auto [word, level] = Q.front();
            Q.pop();

            for (int i = 0; i < L; i++) {
                string newWord = word.substr(0, i) + '*' + word.substr(i + 1);

                for (string& adjacentWord : allComboDict[newWord]) {
                    if (adjacentWord == endWord) return level + 1;
                    if (!visited[adjacentWord]) {
                        visited[adjacentWord] = true;
                        Q.push({adjacentWord, level + 1});
                    }
                }
            }
        }

        return 0;
    }
};

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

Задача: 897. Increasing Order Search Tree Сложность: easy Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла. Пример:

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

👨‍💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 3⃣Вернуть новый корень дерева (первый элемент списка). 😎 Решение:

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

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        vector<TreeNode*> nodes;
        
        inorder(root, nodes);
        
        for (int i = 0; i < nodes.size() - 1; ++i) {
            nodes[i]->left = nullptr;
            nodes[i]->right = nodes[i + 1];
        }
        
        nodes.back()->left = nullptr;
        nodes.back()->right = nullptr;
        return nodes.front();
    }
    
    void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
        if (node == nullptr) return;
        inorder(node->left, nodes);
        nodes.push_back(node);
        inorder(node->right, nodes);
    }
};

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

Задача: 641. Design Circular Deque Сложность: medium Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

👨‍💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:

class MyCircularDeque {
public:
    MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        deque[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return deque[front];
    }

    int getRear() {
        if (isEmpty()) return -1;
        return deque[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

private:
    vector<int> deque;
    int front;
    int rear;
    int size;
    int capacity;
};

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

Задача: 954. Array of Doubled Pairs Сложность: medium Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае. Пример:

Input: arr = [3,1,3,6]
Output: false

👨‍💻 Алгоритм: 1⃣Подсчитать частоту каждого элемента в массиве. Отсортировать массив по абсолютным значениям элементов. 2⃣Для каждого элемента в отсортированном массиве: Проверить, можно ли сопоставить его с элементом, равным его удвоенному значению. Уменьшить счетчик обоих элементов в словаре частот. 3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false. 😎 Решение:

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int num : arr) {
            count[num]++;
        }
        sort(arr.begin(), arr.end(), [](int a, int b) { return abs(a) < abs(b); });
        for (int num : arr) {
            if (count[num] == 0) continue;
            if (count[2 * num] == 0) return false;
            count[num]--;
            count[2 * num]--;
        }
        return true;
    }
};

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

Задача: 433. Minimum Genetic Mutation Сложность: medium Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Алгоритм: 1⃣Инициализируем очередь и множество seen. Помещаем в них startGene. Начинаем BFS по возможным мутациям. 2⃣Для каждой строки из очереди проверяем, достигли ли endGene. Если нет, генерируем все возможные односимвольные мутации и добавляем допустимые в очередь. 3⃣Если очередь опустела, а endGene не найден — возвращаем -1. 😎 Решение:

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> queue;
        unordered_set<string> seen;
        queue.push(start);
        seen.insert(start);
        
        int steps = 0;
        while (!queue.empty()) {
            int nodesInQueue = queue.size();
            
            for (int j = 0; j < nodesInQueue; j++) {
                string node = queue.front();
                queue.pop();

                if (node == end) {
                    return steps;
                }
                
                for (char c: "ACGT") {
                    for (int i = 0; i < node.size(); i++) {
                        string neighbor = node;
                        neighbor[i] = c;
                        if (!seen.count(neighbor) && find(bank.begin(), bank.end(), neighbor) != bank.end()) {
                            queue.push(neighbor);
                            seen.insert(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
};

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

Задача: 1345. Jump Game IV Сложность: hard Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива. За один шаг вы можете прыгнуть с индекса i на индекс: - i + 1, где: i + 1 < arr.length. - i - 1, где: i - 1 >= 0. - j, где: arr[i] == arr[j] и i != j. Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива. Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени. Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

👨‍💻 Алгоритм: 1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов. 2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя. 3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь. 😎 Решение:

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1) return 0;

        unordered_map<int, vector<int>> graph;
        for (int i = 0; i < n; i++) {
            graph[arr[i]].push_back(i);
        }

        vector<int> curs = {0};
        unordered_set<int> visited = {0};
        int step = 0;

        while (!curs.empty()) {
            vector<int> nex;

            for (int node : curs) {
                if (node == n - 1) return step;

                for (int child : graph[arr[node]]) {
                    if (visited.find(child) == visited.end()) {
                        visited.insert(child);
                        nex.push_back(child);
                    }
                }

                graph[arr[node]].clear();

                if (node + 1 < n && visited.find(node + 1) == visited.end()) {
                    visited.insert(node + 1);
                    nex.push_back(node + 1);
                }
                if (node - 1 >= 0 && visited.find(node - 1) == visited.end()) {
                    visited.insert(node - 1);
                    nex.push_back(node - 1);
                }
            }

            curs = nex;
            step++;
        }

        return -1;
    }
};

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

Задача: 126. Word Ladder II Сложность: hard Найдите все кратчайшие пути преобразования от beginWord до endWord, изменяя по одной букве за раз, так чтобы каждое промежуточное слово было из wordList. Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

👨‍💻 Алгоритм: 1⃣Используем BFS, чтобы построить граф уровней (adjList) от beginWord до всех достижимых слов. Каждое слово связано с соседними словами, отличающимися на одну букву. 2⃣Удаляем слова из wordList после каждого уровня, чтобы избежать повторных посещений и гарантировать, что пути будут минимальной длины. 3⃣После BFS используем обратный backtracking от endWord к beginWord, используя построенный adjList, чтобы восстановить все возможные кратчайшие пути. 😎 Решение:

class Solution {
public:
    unordered_map<string, vector<string>> adjList;
    vector<string> currPath;
    vector<vector<string>> shortestPaths;

    vector<string> findNeighbors(string &word, unordered_set<string> &wordList) {
        vector<string> neighbors;
        for (int i = 0; i < word.size(); i++) {
            char oldChar = word[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != oldChar) {
                    word[i] = c;
                    if (wordList.count(word)) neighbors.push_back(word);
                }
            }
            word[i] = oldChar;
        }
        return neighbors;
    }

    void backtrack(string &source, string &destination) {
        if (source == destination) {
            shortestPaths.push_back(vector<string>(currPath.rbegin(), currPath.rend()));
            return;
        }
        for (string& neighbor : adjList[source]) {
            currPath.push_back(neighbor);
            backtrack(neighbor, destination);
            currPath.pop_back();
        }
    }

    void bfs(string &beginWord, unordered_set<string> &wordList) {
        queue<string> q;
        q.push(beginWord);
        unordered_set<string> visited;
        visited.insert(beginWord);

        while (!q.empty()) {
            int size = q.size();
            unordered_set<string> thisLevelVisited;

            for (int i = 0; i < size; i++) {
                string currWord = q.front();
                q.pop();
                vector<string> neighbors = findNeighbors(currWord, wordList);

                for (string& neighbor : neighbors) {
                    if (!visited.count(neighbor)) {
                        if (!thisLevelVisited.count(neighbor)) {
                            q.push(neighbor);
                            thisLevelVisited.insert(neighbor);
                        }
                        adjList[neighbor].push_back(currWord);
                    }
                }
            }
            for (const string& word : thisLevelVisited) {
                wordList.erase(word);
                visited.insert(word);
            }
        }
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return {};
        bfs(beginWord, wordSet);
        currPath = {endWord};
        backtrack(endWord, beginWord);
        return shortestPaths;
    }
};

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

Задача: 997. Find the Town Judge Сложность: easy В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае. Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if (trust.empty() && n == 1) return 1;

        vector<int> trust_count(n + 1, 0);
        vector<int> trusted_by(n + 1, 0);

        for (const auto& t : trust) {
            trust_count[t[0]]++;
            trusted_by[t[1]]++;
        }

        for (int i = 1; i <= n; ++i) {
            if (trust_count[i] == 0 && trusted_by[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }
};

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

Задача: 1043. Partition Array for Maximum Sum Сложность: medium Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число. Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

👨‍💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение:

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n, 0);
        
        for (int i = 0; i < n; ++i) {
            int max_val = 0;
            for (int j = 1; j <= k; ++j) {
                if (i - j + 1 >= 0) {
                    max_val = max(max_val, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = max(dp[i], dp[i - j] + max_val * j);
                    } else {
                        dp[i] = max(dp[i], max_val * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
};

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

Задача: 863. All Nodes Distance K in Binary Tree Сложность: medium Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла. Ответ можно вернуть в любом порядке. Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя). 2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь. 3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS. 😎 Решение:

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        addParent(root, nullptr);
        
        vector<int> answer;
        unordered_set<TreeNode*> visited;
        
        dfs(target, k, visited, answer);
        return answer;
    }
    
private:
    void addParent(TreeNode* cur, TreeNode* parent) {
        if (cur) {
            cur->parent = parent;
            addParent(cur->left, cur);
            addParent(cur->right, cur);
        }
    }
    
    void dfs(TreeNode* cur, int distance, unordered_set<TreeNode*>& visited, vector<int>& answer) {
        if (!cur || visited.count(cur)) return;
        visited.insert(cur);
        if (distance == 0) {
            answer.push_back(cur->val);
            return;
        }
        dfs(cur->parent, distance - 1, visited, answer);
        dfs(cur->left, distance - 1, visited, answer);
        dfs(cur->right, distance - 1, visited, answer);
    }
};

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

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

Задача: 503. Next Greater Element II Сложность: medium Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums. Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа. Пример:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

👨‍💻 Алгоритм: 1⃣Инициализация Создайте массив res той же длины, что и nums, и заполните его значениями -1. 2⃣Поиск следующего большего элемента Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл. 3⃣Возврат результата Верните массив res. 😎 Решение:

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (nums[(i + j) % n] > nums[i]) {
                    res[i] = nums[(i + j) % n];
                    break;
                }
            }
        }
        
        return res;
    }
};

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

Задача: 487. Max Consecutive Ones II Сложность: medium Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля. Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

👨‍💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.size(); ++left) {
            int numZeroes = 0;
            for (int right = left; right < nums.size(); ++right) {
                if (nums[right] == 0) {
                    numZeroes++;
                }
                if (numZeroes <= 1) {
                    longestSequence = max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
};

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

Задача: 474. Ones and Zeroes Сложность: medium Дан массив двоичных строк strs и два целых числа m и n. Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц. Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y. Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int findMaxForm(std::vector<std::string>& strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.size()); ++i) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; ++j) {
                if ((i & (1 << j)) != 0) {
                    auto count = countZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    ++len;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = std::max(maxlen, len);
        }
        return maxlen;
    }

    std::vector<int> countZeroesOnes(const std::string& s) {
        std::vector<int> c(2, 0);
        for (char ch : s) {
            ++c[ch - '0'];
        }
        return c;
    }
};

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