Задача: 729. My Calendar I
Сложность: medium

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

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

1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий.

2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.

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

😎 Решение:

class MyCalendar {
public:
    MyCalendar() {}

    bool book(int start, int end) {
        for (const auto& event : events) {
            if (start < event[1] && end > event[0]) {
                return false;
            }
        }
        events.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> events;
};

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

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

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

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

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

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

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

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

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

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

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

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

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