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

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

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

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

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

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