C/C++ | LeetCode

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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