C/C++ | LeetCode

Задача: 1160. Find Words That Can Be Formed by Characters Сложность: easy Вам дан массив строк words и строка chars. Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз). Верните сумму длин всех хороших строк в words. Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

👨‍💻 Алгоритм: 1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0. 2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл. 3⃣Если good = true, добавьте длину слова к ans. Верните ans. 😎 Решение:

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> counts;
        for (char c : chars) {
            counts[c]++;
        }
        
        int ans = 0;
        for (string word : words) {
            unordered_map<char, int> wordCount;
            for (char c : word) {
                wordCount[c]++;
            }
            
            bool good = true;
            for (auto& [c, freq] : wordCount) {
                if (counts[c] < freq) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.size();
            }
        }
        
        return ans;
    }
};

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1262. Greatest Sum Divisible by Three Сложность: medium Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три. Пример:

Input: nums = [3,6,5,1,8]
Output: 18

👨‍💻 Алгоритм: 1⃣Найдите сумму всех элементов массива. 2⃣Если сумма делится на 3, то она и есть ответ. 3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2). Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2). 😎 Решение:

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        if (totalSum % 3 == 0) {
            return totalSum;
        }
        
        vector<int> mod1, mod2;
        for (int num : nums) {
            if (num % 3 == 1) {
                mod1.push_back(num);
            } else if (num % 3 == 2) {
                mod2.push_back(num);
            }
        }
        
        sort(mod1.begin(), mod1.end());
        sort(mod2.begin(), mod2.end());
        
        if (totalSum % 3 == 1) {
            int remove1 = mod1.empty() ? INT_MAX : mod1[0];
            int remove2 = mod2.size() < 2 ? INT_MAX : mod2[0] + mod2[1];
            return totalSum - min(remove1, remove2);
        } else {
            int remove2 = mod2.empty() ? INT_MAX : mod2[0];
            int remove1 = mod1.size() < 2 ? INT_MAX : mod1[0] + mod1[1];
            return totalSum - min(remove2, remove1);
        }
    }
};

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

Задача: 349. Intersection of Two Arrays Сложность: easy Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен быть уникальным, и вы можете вернуть результат в любом порядке. Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

👨‍💻 Алгоритм: 1⃣Создание множеств: Преобразуйте оба массива nums1 и nums2 в множества для получения уникальных элементов. 2⃣Нахождение пересечения: Найдите пересечение двух множеств. 3⃣Возврат результата: Преобразуйте пересечение обратно в массив и верните его. 😎 Решение:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        vector<int> result;
        for (int num : set1) {
            if (set2.find(num) != set2.end()) {
                result.push_back(num);
            }
        }
        return result;
    }
};

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1396. Design Underground System Сложность: medium Подземная железнодорожная система отслеживает время поездок пассажиров между различными станциями. Эти данные используются для вычисления среднего времени, необходимого для поездки от одной станции до другой. Реализуйте класс UndergroundSystem: - void checkIn(int id, string stationName, int t) Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t. Пассажир может быть зарегистрирован только в одном месте в одно и то же время. - void checkOut(int id, string stationName, int t) Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t. - double getAverageTime(string startStation, string endStation) Возвращает среднее время, необходимое для поездки от startStation до endStation. Среднее время вычисляется на основе всех предыдущих временных интервалов поездок от startStation до endStation, которые происходили непосредственно, т.е. регистрация на startStation с последующим выходом на endStation. Время, необходимое для поездки от startStation до endStation, может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime будет как минимум один пассажир, который уже совершил поездку от startStation до endStation. Вы можете предположить, что все вызовы методов checkIn и checkOut являются последовательными. Если пассажир регистрируется в момент времени t1, а затем выходит в момент времени t2, то t1 < t2. Все события происходят в хронологическом порядке. Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

👨‍💻 Алгоритм: 1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData. 2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData. 3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение. 😎 Решение:

class UndergroundSystem {
    unordered_map<string, pair<double, double>> journeyData;
    unordered_map<int, pair<string, int>> checkInData;

public:
    void checkIn(int id, string stationName, int t) {
        checkInData[id] = {stationName, t};
    }

    void checkOut(int id, string stationName, int t) {
        auto [startStation, startTime] = checkInData[id];
        checkInData.erase(id);
        string routeKey = startStation + "->" + stationName;
        double tripTime = t - startTime;
        journeyData[routeKey].first += tripTime;
        journeyData[routeKey].second += 1;
    }

    double getAverageTime(string startStation, string endStation) {
        auto [totalTime, trips] = journeyData[startStation + "->" + endStation];
        return totalTime / trips;
    }
};

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

Сколько приложений нужно вашей команде для работы? Всего один сервис — Битрикс24! А внутри десятки инструментов для совместной работы и бизнеса. Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 1048. Longest String Chain Сложность: easy Вам дан массив слов, каждое из которых состоит из строчных английских букв. СловоА является предшественником словаВ тогда и только тогда, когда мы можем вставить ровно одну букву в любое место словаА, не меняя порядка остальных символов, чтобы оно стало равно словуВ. Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов. Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });
        
        unordered_map<string, int> dp;
        int longestChain = 1;
        
        for (const string& word : words) {
            dp[word] = 1;
            for (int i = 0; i < word.length(); i++) {
                string predecessor = word.substr(0, i) + word.substr(i + 1);
                if (dp.find(predecessor) != dp.end()) {
                    dp[word] = max(dp[word], dp[predecessor] + 1);
                }
            }
            longestChain = max(longestChain, dp[word]);
        }
        
        return longestChain;
    }
};

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 1136. Parallel Courses Сложность: medium Вам дано целое число n, которое указывает, что есть n курсов, обозначенных от 1 до n. Вам также дан массив relations, где relations[i] = [prevCoursei, nextCoursei], представляющий собой зависимость между курсами: курс prevCoursei должен быть пройден до курса nextCoursei. За один семестр вы можете взять любое количество курсов, при условии, что вы прошли все необходимые предварительные курсы в предыдущем семестре для тех курсов, которые вы собираетесь взять. Верните минимальное количество семестров, необходимых для прохождения всех курсов. Если нет способа пройти все курсы, верните -1. Пример:

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

👨‍💻 Алгоритм: 1⃣Постройте направленный граф из зависимостей (relations). 2⃣Реализуйте функцию dfsCheckCycle для проверки наличия цикла в графе. 3⃣Реализуйте функцию dfsMaxPath для вычисления длины самого длинного пути в графе. Если цикл найден, верните -1. Иначе верните длину самого длинного пути. 😎 Решение:

class Solution {
public:
    int minimumSemesters(int N, vector<vector<int>>& relations) {
        vector<vector<int>> graph(N + 1);
        for (auto& relation : relations) {
            graph[relation[0]].push_back(relation[1]);
        }

        vector<int> visited(N + 1, 0);
        for (int node = 1; node <= N; ++node) {
            if (dfsCheckCycle(node, graph, visited) == -1) {
                return -1;
            }
        }

        vector<int> visitedLength(N + 1, 0);
        int maxLength = 1;
        for (int node = 1; node <= N; ++node) {
            int length = dfsMaxPath(node, graph, visitedLength);
            maxLength = max(length, maxLength);
        }
        return maxLength;
    }

private:
    int dfsCheckCycle(int node, vector<vector<int>>& graph, vector<int>& visited) {
        if (visited[node] != 0) {
            return visited[node];
        } else {
            visited[node] = -1;
        }
        for (int endNode : graph[node]) {
            if (dfsCheckCycle(endNode, graph, visited) == -1) {
                return -1;
            }
        }
        visited[node] = 1;
        return 1;
    }

    int dfsMaxPath(int node, vector<vector<int>>& graph, vector<int>& visitedLength) {
        if (visitedLength[node] != 0) {
            return visitedLength[node];
        }
        int maxLength = 1;
        for (int endNode : graph[node]) {
            int length = dfsMaxPath(endNode, graph, visitedLength);
            maxLength = max(length + 1, maxLength);
        }
        visitedLength[node] = maxLength;
        return maxLength;
    }
};

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

Задача: 941. Valid Mountain Array Сложность: easy Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Пример:

Input: arr = [2,1]
Output: false

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

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if (arr.size() < 3) return false;
        
        int i = 1;
        while (i < arr.size() && arr[i] > arr[i - 1]) i++;
        
        if (i == 1 || i == arr.size()) return false;
        
        while (i < arr.size() && arr[i] < arr[i - 1]) i++;
        
        return i == arr.size();
    }
};

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

Задача: 1474. Delete N Nodes After M Nodes of a Linked List Сложность: easy Вам дано начало связанного списка и два целых числа m и n. Пройдите по связанному списку и удалите некоторые узлы следующим образом: Начните с головы как текущего узла. Сохраните первые m узлов, начиная с текущего узла. Удалите следующие n узлов. Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка. Верните голову изменённого списка после удаления указанных узлов. Пример:

Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List  (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.

👨‍💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка. Инициализируйте lastMNode на голову связанного списка. 2⃣Итерация по списку: Итеративно удаляйте n узлов после m узлов, продолжая до конца списка. Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел. Продолжайте итерацию по n узлам. 3⃣Удаление узлов: Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов. 😎 Решение:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* deleteNodes(ListNode* head, int m, int n) {
        ListNode* currentNode = head;
        ListNode* lastMNode = head;

        while (currentNode) {
            int mCount = m, nCount = n;

            while (currentNode && mCount > 0) {
                lastMNode = currentNode;
                currentNode = currentNode->next;
                mCount--;
            }

            while (currentNode && nCount > 0) {
                currentNode = currentNode->next;
                nCount--;
            }

            lastMNode->next = currentNode;
        }
        return head;
    }
};

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

Задача: 951. Flip Equivalent Binary Trees Сложность: medium Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае. Пример:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

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

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

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2) return false;
        if (root1->val != root2->val) return false;
        
        return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) ||
               (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
    }
};

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

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 47 000 ₽ за успешного кандидата 📞Поддержка на всех этапах 📅Свободное расписание 📊Удобные инструменты для работы Приводите новых курьеров и получайте в среднем 250 000 ₽ в месяц! Зарегистрироваться #реклама eda.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 423. Reconstruct Original Digits from English Сложность: medium Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания. Пример:

Input: s = "owoztneoer"
Output: "012"

👨‍💻 Алгоритм: 1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа. 2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры. 3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат. 😎 Решение:

class Solution {
public:
    string originalDigits(string s) {
        vector<int> count(26, 0);
        for(char letter: s) {
            count[letter - 'a']++;
        }

        vector<int> out(10, 0);
        out[0] = count['z' - 'a'];
        out[2] = count['w' - 'a'];
        out[4] = count['u' - 'a'];
        out[6] = count['x' - 'a'];
        out[8] = count['g' - 'a'];
        out[3] = count['h' - 'a'] - out[8];
        out[5] = count['f' - 'a'] - out[4];
        out[7] = count['s' - 'a'] - out[6];
        out[9] = count['i' - 'a'] - out[5] - out[6] - out[8];
        out[1] = count['n' - 'a'] - out[7] - 2 * out[9];

        string output;
        for(int i = 0; i < 10; i++)
            for (int j = 0; j < out[i]; j++)
                output += to_string(i);
        return output;
    }
};

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

Я поставил целью сбора скромные 300 тыс. рублей, но ребята, вы накидали больше млн. всего за 1 день. Это просто невероятно! Благодаря вашей поддержке, я смогу привлечь еще больше людей для разработки сайта и обработки собеседований. Ваш вклад сделает проект качественнее и ускорит его выход! Огромное вам спасибо! Краудфандинг будет продолжаться еще 31 день и все кто поддержать проект сейчас, до его выхода, смогут получить: 🚀 PRO-тариф на 1 год, по цене месячной подписки на релизе. ➕ Доступ к закрытому бета-тесту easyoffer 2.0 (середина–конец мая) Поддержать проект можно здесь: https://planeta.ru/campaigns/easyoffer Огромное спасибо за вашу поддержку! 🤝

🎉 Краудфандинг easyoffer 2.0 стартовал! Друзья, с этого момента вы можете поддержать проект и получить существенный бонус: 🚀 PRO-тариф на 1 год, по цене месячной подписки на релизе. ➕ Доступ к закрытому бета-тесту easyoffer 2.0 (середина–конец мая) Поддержать проект можно здесь: https://planeta.ru/campaigns/easyoffer 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 910. Smallest Range II Сложность: medium Вам дан целочисленный массив nums и целое число k. Для каждого индекса i, где 0 <= i < nums.length, измените nums[i] на nums[i] + k или nums[i] - k. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после изменения значений в каждом индексе. Пример:

Input: nums = [1], k = 0
Output: 0

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

class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int minVal = nums[0];
        int maxVal = nums[n - 1];
        int result = maxVal - minVal;

        for (int i = 0; i < n - 1; i++) {
            int high = max(nums[i] + k, maxVal - k);
            int low = min(nums[i + 1] - k, minVal + k);
            result = min(result, high - low);
        }

        return result;
    }
};

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

Нанимаете аутсорс, подрядчиков, фрилансеров? Попробуйте Битрикс24 Коллабы – платформа для эффективной работы с подрядчиками. Тут обсуждения превращаются в задачи, а видео созвон можно собрать одной кнопкой. Любой проект можно разложить по полочкам с понятным ТЗ и обозначенными сроками. Работайте в Битрикс24 и создавайте Коллабы с подрядчиками. Начать #реклама 16+ collabs.bitrix24.ru О рекламодателе