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

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

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

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