Задача: 507. Perfect Number
Сложность: easy

Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело.

Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.

Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

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

1⃣Инициализация
Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0.

2⃣Поиск делителей и вычисление суммы
Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель.

3⃣Проверка на совершенное число
Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false.

😎 Решение:

 class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 0) return false;
        int sum = 0;
        for (int i = 1; i * i <= num; ++i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return sum - num == num;
    }
};

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

Задача: 907. Sum of Subarray Minimums
Сложность: medium

Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.

Пример:

Input: arr = [3,1,2,4]
Output: 17

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

1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.

2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным.

3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> left(n), right(n);
        stack<int> st;

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }
            left[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }

        while (!st.empty()) st.pop();

        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n - i : st.top() - i;
            st.push(i);
        }

        long long result = 0;
        for (int i = 0; i < n; ++i) {
            result = (result + (long long)arr[i] * left[i] * right[i]) % MOD;
        }

        return result;
    }
};

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

Задача: 1122. Relative Sort Array
Сложность: easy

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

1⃣Инициализация и подсчёт:
Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.
Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

2⃣Заполнение countMap и remaining:
Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

3⃣Формирование результирующего массива:
Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.
Отсортируйте массив remaining и добавьте его элементы в result.
Верните result в виде массива.

😎 Решение:

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> countMap;
        vector<int> remaining;
        vector<int> result;

        for (int value : arr2) {
            countMap[value] = 0;
        }

        for (int value : arr1) {
            if (countMap.count(value)) {
                countMap[value]++;
            } else {
                remaining.push_back(value);
            }
        }

        sort(remaining.begin(), remaining.end());

        for (int value : arr2) {
            for (int i = 0; i < countMap[value]; i++) {
                result.push_back(value);
            }
        }

        result.insert(result.end(), remaining.begin(), remaining.end());
        return result;
    }
};

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

Задача: 732. My Calendar III
Сложность: hard

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий.

2⃣Для каждого нового события обновите словари начала и конца событий.

3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

class MyCalendarThree {
public:
    MyCalendarThree() {}

    int book(int startTime, int endTime) {
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        for (const auto& [time, count] : events) {
            active += count;
            maxActive = max(maxActive, active);
        }
        
        return maxActive;
    }

private:
    map<int, int> events;
};

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

Задача: 477. Total Hamming Distance
Сложность: medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

int totalHammingDistance(vector<int>& nums)
{
    int ans = 0;

    if (nums.empty())
        return ans;

    for (int i = 0; i < nums.size() - 1; i++)
        for (int j = i + 1; j < nums.size(); j++)
            ans += __builtin_popcount(nums[i] ^ nums[j]);

    return ans;
}

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

Задача: 984. String Without AAA or BBB
Сложность: medium

Даны два целых числа a и b, верните любую строку s, такую что:

s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'.
Подстрока 'aaa' не встречается в s.
Подстрока 'bbb' не встречается в s.

Пример:

Input: a = 4, b = 1
Output: "aabaa"

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

1⃣Инициализация переменных:
Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно.

2⃣Создание строки:
Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'.
Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот.
Если оба символа возможны для добавления, выбирайте тот, которого осталось больше.

3⃣Добавление оставшихся символов:
После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались.

😎 Решение:

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string result;
        
        while (a > 0 || b > 0) {
            if (result.size() >= 2 && result[result.size() - 1] == result[result.size() - 2]) {
                if (result.back() == 'a') {
                    result.push_back('b');
                    b--;
                } else {
                    result.push_back('a');
                    a--;
                }
            } else {
                if (a >= b) {
                    result.push_back('a');
                    a--;
                } else {
                    result.push_back('b');
                    b--;
                }
            }
        }
        
        return result;
    }
};

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

Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium

Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.

Пример:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

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

1⃣Сортировка папок:
Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками.

2⃣Фильтрация вложенных папок:
Будем использовать переменную для отслеживания текущей родительской папки.

3⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список.

😎 Решение:

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        vector<string> result;
        string parent = "";
        
        for (const string& path : folder) {
            if (parent.empty() || path.find(parent + "/") != 0) {
                parent = path;
                result.push_back(path);
            }
        }
        
        return result;
    }
};

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

Задача: 228. Summary Ranges
Сложность: easy

Вам дан отсортированный массив уникальных целых чисел nums.
Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).
Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums.
Каждый диапазон [a,b] в списке должен быть представлен в формате:
"a->b" если a != b
"a" если a == b

Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

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

1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i].

2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики.

3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон.

😎 Решение:

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ranges;
        for (int i = 0; i < nums.size(); i++) {
            int start = nums[i];
            while (i + 1 < nums.size() && nums[i] + 1 == nums[i + 1]) {
                i++;
            }
            if (start != nums[i]) {
                ranges.push_back(to_string(start) + "->" + to_string(nums[i]));
            } else {
                ranges.push_back(to_string(start));
            }
        }
        return ranges;
    }
};

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

Задача: 937. Reorder Data in Log Files
Сложность: medium

Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.

Пример:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

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

1⃣Разделить журналы на буквенные и цифровые.

2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.

3⃣Вернуть окончательный результат.

😎 Решение:

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        auto compare = [](const string& log1, const string& log2) {
            int pos1 = log1.find(' '), pos2 = log2.find(' ');
            bool isDigit1 = isdigit(log1[pos1 + 1]), isDigit2 = isdigit(log2[pos2 + 1]);
            
            if (!isDigit1 && !isDigit2) {
                string s1 = log1.substr(pos1 + 1), s2 = log2.substr(pos2 + 1);
                if (s1 != s2) return s1 < s2;
                return log1 < log2;
            }
            return isDigit1 ? false : true;
        };
        stable_sort(logs.begin(), logs.end(), compare);
        return logs;
    }
};

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

Задача: 339. Nested List Weight Sum
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.
Верните сумму каждого целого числа в nestedList, умноженного на его глубину.

Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

1⃣Инициализация и вызов рекурсивной функции:
Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1.

2⃣Рекурсивное исследование списка:
В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной.

3⃣Возврат результата:
Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.

😎 Решение:

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }
    
private:
    int dfs(const vector<NestedInteger>& list, int depth) {
        int total = 0;
        for (const auto& nested : list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth;
            } else {
                total += dfs(nested.getList(), depth + 1);
            }
        }
        return total;
    }
};

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

Задача: 1512. Number of Good Pairs
Сложность: easy

Дан массив целых чисел nums, верните количество хороших пар.

Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.

Пример:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерируйте i от 0 до nums.length:
Итерируйте j от i + 1 до nums.length:
Если nums[i] == nums[j], увеличьте ans на 1.

3⃣Верните ans.

😎 Решение:

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] == nums[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

1⃣Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге.

2⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.

3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.

😎 Решение:

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int mod = 1e9 + 7;
        int max_pos = min(arrLen - 1, steps);
        vector<int> dp(max_pos + 1, 0);
        dp[0] = 1;
        for (int step = 0; step < steps; ++step) {
            vector<int> new_dp(max_pos + 1, 0);
            for (int i = 0; i <= max_pos; ++i) {
                new_dp[i] = dp[i] % mod;
                if (i > 0) new_dp[i] = (new_dp[i] + dp[i - 1]) % mod;
                if (i < max_pos) new_dp[i] = (new_dp[i] + dp[i + 1]) % mod;
            }
            dp = new_dp;
        }
        return dp[0];
    }
};

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

#include <vector>
#include <string>

class CombinationIterator {
private:
    std::vector<std::string> combinations;

public:
    CombinationIterator(std::string characters, int combinationLength) {
        int n = characters.size();
        int k = combinationLength;
        for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
            if (__builtin_popcount(bitmask) == k) {
                std::string curr;
                for (int j = 0; j < n; ++j) {
                    if (bitmask & (1 << (n - j - 1))) {
                        curr.push_back(characters[j]);
                    }
                }
                combinations.push_back(curr);
            }
        }
    }

    std::string next() {
        std::string res = combinations.back();
        combinations.pop_back();
        return res;
    }

    bool hasNext() {
        return !combinations.empty();
    }
};

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

Задача: 1021. Remove Outermost Parentheses
Сложность: easy

Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.

Пример:

Input: s = "(()())(())"
Output: "()()()"

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

1⃣Инициализация переменных:
Создайте пустую строку для хранения результата.
Используйте счетчик для отслеживания уровня вложенности скобок..

2⃣Обработка строки:
Итерируйте по каждому символу строки.
Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат.
Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат.

3⃣Возврат результата:
Верните результат, содержащий строку без крайних скобок из каждой примитивной строки.

😎 Решение:

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result;
        int level = 0;
        
        for (char c : s) {
            if (c == '(') {
                if (level > 0) {
                    result += c;
                }
                level++;
            } else {
                level--;
                if (level > 0) {
                    result += c;
                }
            }
        }
        
        return result;
    }
};

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

Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium

В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.

Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.

Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.

Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

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

1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.

2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.

3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.

😎 Решение:

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }

private:
    vector<int> parent;
    vector<int> rank;
};

class Solution {
public:
    int earliestAcq(vector<vector<int>>& logs, int n) {
        sort(logs.begin(), logs.end());
        UnionFind uf(n);
        int groupCount = n;
        
        for (const auto& log : logs) {
            int timestamp = log[0];
            int friendA = log[1];
            int friendB = log[2];
            if (uf.unionSets(friendA, friendB)) {
                groupCount--;
            }
            if (groupCount == 1) {
                return timestamp;
            }
        }
        
        return -1;
    }
};

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        int N = rectangles.size();
        set<int> Xvals, Yvals;

        for (const auto& rec : rectangles) {
            Xvals.insert(rec[0]);
            Xvals.insert(rec[2]);
            Yvals.insert(rec[1]);
            Yvals.insert(rec[3]);
        }

        vector<int> imapx(Xvals.begin(), Xvals.end());
        vector<int> imapy(Yvals.begin(), Yvals.end());

        unordered_map<int, int> mapx, mapy;
        for (int i = 0; i < imapx.size(); ++i) mapx[imapx[i]] = i;
        for (int i = 0; i < imapy.size(); ++i) mapy[imapy[i]] = i;

        vector<vector<bool>> grid(imapx.size(), vector<bool>(imapy.size()));
        for (const auto& rec : rectangles)
            for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
                for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
                    grid[x][y] = true;

        long ans = 0;
        for (int x = 0; x < grid.size(); ++x)
            for (int y = 0; y < grid[0].size(); ++y)
                if (grid[x][y])
                    ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);

        ans %= 1'000'000'007;
        return ans;
    }
};

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

Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium

Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.

Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.

Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

1⃣Переберите все возможные начальные элементы первой и второй части последовательности, проверяя, чтобы не было ведущих нулей.

2⃣Для каждой пары начальных элементов проверяйте, можно ли продолжить последовательность Фибоначчи, создавая следующую часть, которая должна быть суммой двух предыдущих частей.

3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.

😎 Решение:

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        int N = S.length();
        for (int i = 0; i < min(10, N); ++i) {
            if (S[0] == '0' && i > 0) break;
            long a = stol(S.substr(0, i + 1));
            if (a >= INT_MAX) break;

            for (int j = i + 1; j < min(i + 10, N); ++j) {
                if (S[i + 1] == '0' && j > i + 1) break;
                long b = stol(S.substr(i + 1, j - i));
                if (b >= INT_MAX) break;

                vector<int> fib = {(int)a, (int)b};
                int k = j + 1;
                while (k < N) {
                    long nxt = (long)fib[fib.size() - 2] + fib[fib.size() - 1];
                    if (nxt > INT_MAX) break;
                    string nxtS = to_string(nxt);
                    if (S.substr(k).find(nxtS) == 0) {
                        k += nxtS.length();
                        fib.push_back((int)nxt);
                    } else {
                        break;
                    }
                }
                if (fib.size() >= 3) return fib;
            }
        }
        return {};
    }
};

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

class TopVotedCandidate {
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        this->times = times;
        unordered_map<int, int> counts;
        int leader = -1;

        for (int person : persons) {
            counts[person]++;
            if (counts[person] >= counts[leader]) {
                leader = person;
            }
            leaders.push_back(leader);
        }
    }

    int q(int t) {
        auto it = upper_bound(times.begin(), times.end(), t);
        return leaders[it - times.begin() - 1];
    }

private:
    vector<int> times;
    vector<int> leaders;
};

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

Задача: 977. Squares of a Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке.

Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

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

1⃣Создайте массив квадратов каждого элемента.

2⃣Отсортируйте массив квадратов.

3⃣Верните отсортированный массив квадратов.

😎 Решение:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        size_t n = nums.size();
        vector<int> ans(n);
        for (size_t i = 0; i < n; i++) {
            ans[i] = nums[i] * nums[i];
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке.

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

class Solution {
    fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
        val toDeleteSet = to_delete.toSet()
        val forest = mutableListOf<TreeNode?>()

        fun processNode(node: TreeNode?): TreeNode? {
            if (node == null) return null

            node.left = processNode(node.left)
            node.right = processNode(node.right)

            if (toDeleteSet.contains(node.`val`)) {
                node.left?.let { forest.add(it) }
                node.right?.let { forest.add(it) }
                return null
            }
            return node
        }

        val root = processNode(root)
        if (root != null) forest.add(root)

        return forest
    }
}

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

Задача: 929. Unique Email Addresses
Сложность: easy

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2

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

1⃣Создать множество для хранения уникальных обработанных адресов электронной почты.

2⃣Для каждого адреса в emails:
Разделить адрес на локальное и доменное имя по символу '@'.
Обработать локальное имя:
Удалить все точки '.'.
Обрезать часть после символа '+'.
Объединить обработанное локальное имя и доменное имя.
Добавить результат в множество уникальных адресов.

3⃣Вернуть количество уникальных адресов в множестве.

😎 Решение:

class Solution {
    public int numUniqueEmails(String[] emails) {
        Set<String> uniqueEmails = new HashSet<>();
        for (String email : emails) {
            String[] parts = email.split("@");
            String local = parts[0].split("\\+")[0].replace(".", "");
            uniqueEmails.add(local + "@" + parts[1]);
        }
        return uniqueEmails.size();
    }
}

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