C/C++ | LeetCode

База 1000+ реальных собеседований теперь встроена в easyoffer Смотрите, как другие кандидаты отвечают на вопросы, решают задачи и проходят этапы на реальных собеседованиях от топовых компаний. Подготовьтесь к своему собеседованию с двойной уверенностью. Напоминаем, что сегодня последний день Чёрной Пятницы 👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/

Задача: 1662. Check If Two String Arrays are Equivalent Сложность: easy Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае. Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку. Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

👨‍💻 Алгоритм: 1⃣Построение списка символов для word2: Создайте список list2 для хранения всех символов из массива строк word2. 2⃣Итерация по word1 и проверка соответствующих символов: Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2. 3⃣Возврат результата: Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают. 😎 Решение:

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        string list2;
        for (const string& s : word2) {
            list2 += s;
        }

        int index = 0;
        int list2Length = list2.size();

        for (const string& s : word1) {
            for (char c : s) {
                if (index >= list2Length || c != list2[index]) {
                    return false;
                }
                index++;
            }
        }

        return index == list2Length;
    }
};

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

Задача: 991. Broken Calculator Сложность: medium Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно: Умножить число на экране на 2, или Вычесть 1 из числа на экране. Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе. Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
};

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

Задача: 1033. Moving Stones Until Consecutive Сложность: medium На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть. Пример:

Input: a = 3, b = 5, c = 1
Output: [1,2]

👨‍💻 Алгоритм: 1⃣Сортировка позиций: Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z. 2⃣Вычисление минимальных ходов: Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0. Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1. В остальных случаях минимальное количество ходов равно 2. 3⃣Вычисление максимальных ходов: Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1). 😎 Решение:

vector<int> numMovesStones(int a, int b, int c) {
    vector<int> stones = {a, b, c};
    sort(stones.begin(), stones.end());
    int x = stones[0], y = stones[1], z = stones[2];
    int min_moves = (y - x <= 2 || z - y <= 2) ? ((y - x == 1 && z - y == 1) ? 0 : 1) : 2;
    int max_moves = (y - x - 1) + (z - y - 1);
    return {min_moves, max_moves};
}

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

Задача: 1339. Maximum Product of Splitted Binary Tree Сложность: medium Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным. Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после. Пример:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

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

class Solution {
    vector<int> allSums;
    
public:
    int maxProduct(TreeNode* root) {
        long totalSum = treeSum(root);
        long best = 0;
        for (long sum : allSums) {
            best = max(best, sum * (totalSum - sum));
        }
        return (int)(best % 1000000007);
    }
    
private:
    int treeSum(TreeNode* subroot) {
        if (!subroot) return 0;
        int leftSum = treeSum(subroot->left);
        int rightSum = treeSum(subroot->right);
        int totalSum = leftSum + rightSum + subroot->val;
        allSums.push_back(totalSum);
        return totalSum;
    }
};

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

Черная пятница на easyoffer Скидка 70% на PRO до 29 ноября. 👉 https://easyoffer.ru/

Задача: 860. Lemonade Change Сложность: easy На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5. Обратите внимание, что изначально у вас нет никакой сдачи. Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае. Пример:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

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

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

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

Задача: 1063. Number of Valid Subarrays Сложность: hard Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

class Solution {
public:
    int validSubarrays(vector<int>& nums) {
        int ans = 0;
        stack<int> st;
        
        for (int i = 0; i < nums.size(); i++) {
            while (!st.empty() && nums[i] < nums[st.top()]) {
                ans += (i - st.top());
                st.pop();
            }
            st.push(i);
        }
        
        while (!st.empty()) {
            ans += (nums.size() - st.top());
            st.pop();
        }
        
        return ans;
    }
};

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

Задача: 1005. Maximize Sum Of Array After K Negations Сложность: easy Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом. Пример:

Input: nums = [4,2,3], k = 1
Output: 5

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

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

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

Задача: 96. Unique Binary Search Trees Сложность: medium Дано число n. Нужно вычислить количество структурно уникальных бинарных деревьев поиска (BST), состоящих из n узлов с уникальными значениями от 1 до n. Пример:

Input: n = 3
Output: 5

👨‍💻 Алгоритм: 1⃣Обозначим G(n) — количество уникальных BST, построенных из n узлов. Пусть F(i, n) — количество BST, в которых i является корнем. Тогда: G(n) = F(1, n) + F(2, n) + ... + F(n, n) 2⃣Для фиксированного i: в левой части — i - 1 узел, в правой — n - i. Т.е. F(i, n) = G(i - 1) * G(n - i) 3⃣Тогда: G(n) = ∑ G(i - 1) * G(n - i), i = 1..n Сохраняем значения G[0] = 1 и G[1] = 1, и далее строим по формуле. 😎 Решение:

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }

        return G[n];
    }
};

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

Задача: 743. Network Delay Time Сложность: medium Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1. Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int, int>>> graph;
        for (int i = 1; i <= n; ++i) {
            graph[i] = vector<pair<int, int>>();
        }
        for (auto& time : times) {
            graph[time[0]].emplace_back(time[1], time[2]);
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
        minHeap.emplace(0, k);
        unordered_map<int, int> minTime;
        for (int i = 1; i <= n; ++i) {
            minTime[i] = INT_MAX;
        }
        minTime[k] = 0;

        while (!minHeap.empty()) {
            auto [time, node] = minHeap.top(); minHeap.pop();
            for (auto& [neighbor, t] : graph[node]) {
                int newTime = time + t;
                if (newTime < minTime[neighbor]) {
                    minTime[neighbor] = newTime;
                    minHeap.emplace(newTime, neighbor);
                }
            }
        }

        int maxTime = *max_element(minTime.begin(), minTime.end());
        return maxTime == INT_MAX ? -1 : maxTime;
    }
};

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

Задача: 643. Maximum Average Subarray I Сложность: easy Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5. Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int currentSum = accumulate(nums.begin(), nums.begin() + k, 0);
        int maxSum = currentSum;
        
        for (int i = k; i < nums.size(); i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        return (double) maxSum / k;
    }
};

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

Задача: 476. Number Complement Сложность: easy Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении. Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение. Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

👨‍💻 Алгоритм: 1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1. 2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1. 3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask. 😎 Решение:

class Solution {
public:
    int findComplement(int num) {
        int bitmask = num;
        bitmask |= (bitmask >> 1);
        bitmask |= (bitmask >> 2);
        bitmask |= (bitmask >> 4);
        bitmask |= (bitmask >> 8);
        bitmask |= (bitmask >> 16);
        return bitmask ^ num;
    }
};

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

Задача: 244. Shortest Word Distance II Сложность: medium Необходимо реализовать структуру, которая быстро отвечает на запросы расстояния между двумя словами Пример:

Input: ["WordDistance", "shortest", "shortest"] [[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]] Output: [null, 3, 1]

👨‍💻 Алгоритм: 1⃣В конструкторе сохраняем словарь, где каждому слову сопоставляется список индексов, на которых оно встречается в массиве 2⃣При запросе shortest(word1, word2) получаем два списка индексов и двигаемся по ним двумя указателями, считая минимальное расстояние 3⃣Возвращаем минимальное абсолютное расстояние между индексами слов 😎 Решение:

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

class WordDistance {
public:
    WordDistance(std::vector<std::string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            locations[words[i]].push_back(i);
        }
    }

    int shortest(std::string word1, std::string word2) {
        const std::vector<int>& loc1 = locations[word1];
        const std::vector<int>& loc2 = locations[word2];
        int l1 = 0, l2 = 0, minDiff = INT_MAX;

        while (l1 < loc1.size() && l2 < loc2.size()) {
            minDiff = std::min(minDiff, std::abs(loc1[l1] - loc2[l2]));
            if (loc1[l1] < loc2[l2]) {
                ++l1;
            } else {
                ++l2;
            }
        }
        return minDiff;
    }

private:
    std::unordered_map<std::string, std::vector<int>> locations;
};

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

Задача: 68. Text Justification Сложность: hard Дан массив слов words и ширина строки maxWidth. Необходимо вернуть текст, в котором строки выровнены по ширине с равномерным распределением пробелов, кроме последней строки — она выравнивается по левому краю. Пример:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
arduino[
   "This    is    an",
   "example  of text",
   "justification.  "
]

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

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        int i = 0;
        while (i < words.size()) {
            vector<string> currentLine = getWords(i, words, maxWidth);
            i += currentLine.size();
            ans.push_back(createLine(currentLine, i, words, maxWidth));
        }
        return ans;
    }

private:
    vector<string> getWords(int i, vector<string>& words, int maxWidth) {
        vector<string> currentLine;
        int currLength = 0;
        while (i < words.size() && currLength + words[i].size() <= maxWidth) {
            currentLine.push_back(words[i]);
            currLength += words[i].size() + 1;
            i++;
        }
        return currentLine;
    }

    string createLine(vector<string>& line, int i, vector<string>& words, int maxWidth) {
        int baseLength = -1;
        for (const string& word : line) {
            baseLength += word.size() + 1;
        }
        int extraSpaces = maxWidth - baseLength;

        // Последняя строка или строка с одним словом
        if (line.size() == 1 || i == words.size()) {
            string res = join(line, " ");
            res += string(extraSpaces, ' ');
            return res;
        }

        int wordCount = line.size() - 1;
        int spacesPerWord = extraSpaces / wordCount;
        int needsExtraSpace = extraSpaces % wordCount;

        for (int j = 0; j < needsExtraSpace; j++) {
            line[j] += " ";
        }
        for (int j = 0; j < wordCount; j++) {
            line[j] += string(spacesPerWord, ' ');
        }

        return join(line, " ");
    }

    string join(vector<string>& line, const string& delimeter) {
        if (line.empty()) return "";
        string res = line[0];
        for (int i = 1; i < line.size(); i++) {
            res += delimeter + line[i];
        }
        return res;
    }
};

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

Задача: 689. Maximum Sum of 3 Non-Overlapping Subarrays Сложность: hard Дан целочисленный массив nums и целое число k. Найдите три непересекающихся подмассива длины k с максимальной суммой и верните их. Верните результат в виде списка индексов, представляющих начальную позицию каждого интервала (нумерация с 0). Если существует несколько ответов, верните лексикографически наименьший. Пример:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

👨‍💻 Алгоритм: 1⃣Предположим, что фиксирован j. Нам нужно узнать на интервалах i∈[0,j−k] и l∈[j+k,len(W)−1], где наибольшее значение W[i] (и соответственно W[l]) встречается первым (то есть, с наименьшим индексом). 2⃣Мы можем решить эту задачу с помощью динамического программирования. Например, если мы знаем, что i - это место, где наибольшее значение W[i] встречается первым на [0,5], то на [0,6] первое появление наибольшего W[i] должно быть либо i, либо 6. Если, скажем, 6 лучше, тогда мы устанавливаем best = 6. В конце left[z] будет первым вхождением наибольшего значения W[i] на интервале i∈[0,z], а right[z] будет таким же, но на интервале i∈[z,len(W)−1]. 3⃣Это означает, что для некоторого выбора j, кандидат на ответ должен быть (left[j - k], j, right[j + k]). Мы выбираем кандидата, который дает максимальное значение W[i] + W[j] + W[l]. 😎 Решение:

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        vector<int> W(nums.size() - k + 1);
        int currSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            currSum += nums[i];
            if (i >= k) {
                currSum -= nums[i - k];
            }
            if (i >= k - 1) {
                W[i - k + 1] = currSum;
            }
        }

        vector<int> left(W.size());
        int best = 0;
        for (int i = 0; i < W.size(); i++) {
            if (W[i] > W[best]) best = i;
            left[i] = best;
        }

        vector<int> right(W.size());
        best = W.size() - 1;
        for (int i = W.size() - 1; i >= 0; i--) {
            if (W[i] >= W[best]) best = i;
            right[i] = best;
        }
        
        vector<int> ans = {-1, -1, -1};
        for (int j = k; j < W.size() - k; j++) {
            int i = left[j - k], l = right[j + k];
            if (ans[0] == -1 || W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]]) {
                ans = {i, j, l};
            }
        }
        return ans;
    }
};

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

Задача: 1335. Minimum Difficulty of a Job Schedule Сложность: hard Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i). Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день. Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i]. Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1. Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

👨‍💻 Алгоритм: 1⃣Определение состояния: Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней. 2⃣Функция перехода состояния: Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i ]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i ]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i ]) для всех j > i. 3⃣Базовый случай: Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач. 😎 Решение:

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        if (n < d) {
            return -1;
        }

        vector<vector<int>> mem(n, vector<int>(d + 1, -1));
        return minDiff(0, d, jobDifficulty, mem);
    }

private:
    int minDiff(int i, int daysRemaining, vector<int>& jobDifficulty, vector<vector<int>>& mem) {
        if (mem[i][daysRemaining] != -1) {
            return mem[i][daysRemaining];
        }

        if (daysRemaining == 1) {
            int res = 0;
            for (int j = i; j < jobDifficulty.size(); j++) {
                res = max(res, jobDifficulty[j]);
            }
            return res;
        }

        int res = INT_MAX;
        int dailyMaxJobDiff = 0;
        for (int j = i; j < jobDifficulty.size() - daysRemaining + 1; j++) {
            dailyMaxJobDiff = max(dailyMaxJobDiff, jobDifficulty[j]);
            res = min(res, dailyMaxJobDiff + minDiff(j + 1, daysRemaining - 1, jobDifficulty, mem));
        }
        mem[i][daysRemaining] = res;
        return res;
    }
};

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

Задача: 1192. Critical Connections in a Network Сложность: hard Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть. Критическое соединение — это соединение, удаление которого сделает невозможным достижение некоторыми серверами других серверов. Верните все критические соединения в сети в любом порядке. Пример:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

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

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        formGraph(n, connections);
        dfs(0, 0);
        
        vector<vector<int>> result;
        for (auto& conn : connDict) {
            result.push_back({conn.first.first, conn.first.second});
        }
        return result;
    }

private:
    unordered_map<int, vector<int>> graph;
    unordered_map<int, int> rank;
    map<pair<int, int>, bool> connDict;
    
    void formGraph(int n, vector<vector<int>>& connections) {
        for (int i = 0; i < n; ++i) {
            graph[i] = vector<int>();
            rank[i] = -1;
        }
        for (auto& edge : connections) {
            int u = edge[0], v = edge[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
            connDict[{min(u, v), max(u, v)}] = true;
        }
    }
    
    int dfs(int node, int discoveryRank) {
        if (rank[node] != -1) {
            return rank[node];
        }
        
        rank[node] = discoveryRank;
        int minRank = discoveryRank + 1;
        
        for (int neighbor : graph[node]) {
            if (rank[neighbor] != -1 && rank[neighbor] == discoveryRank - 1) {
                continue;
            }
            
            int recursiveRank = dfs(neighbor, discoveryRank + 1);
            
            if (recursiveRank <= discoveryRank) {
                connDict.erase({min(node, neighbor), max(node, neighbor)});
            }
            
            minRank = min(minRank, recursiveRank);
        }
        
        return minRank;
    }
};

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

Задача: 650. 2 Keys Keyboard Сложность: medium На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз. Пример:

Input: n = 3
Output: 3

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

int minSteps(int n) {
    if (n == 1) return 0;
    vector<int> dp(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        dp[i] = i;
        for (int j = 1; j <= i / 2; ++j) {
            if (i % j == 0) {
                dp[i] = min(dp[i], dp[j] + i / j);
            }
        }
    }
    return dp[n];
}

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

Задача: 257. Binary Tree Paths Сложность: easy Дано бинарное дерево. Нужно вернуть все возможные пути от корня до листьев, где путь представлен как строка вида "1->2->5". Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

class Solution {
public:
    void construct_paths(TreeNode* root, string path, vector<string>& paths) {
        if (root) {
            path += to_string(root->val);
            if (!root->left && !root->right) {
                paths.push_back(path);
            } else {
                path += "->";
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        construct_paths(root, "", paths);
        return paths;
    }
};

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