C/C++ | LeetCode

Задача: 528. Random Pick with Weight Сложность: medium Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i. Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w). Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%). Пример:

    
        Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
{}
    

👨‍💻 Алгоритм: 1⃣ Инициализация и предобработка весов: В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно. Также в конструкторе сохраните общую сумму весов totalSum. 2⃣ Генерация случайного числа и выбор индекса: В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum. Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу. 3⃣ Возврат результата: Верните найденный индекс. 😎 Решение:

    
        class Solution {
private:
    vector<int> prefixSums;
    int totalSum;

public:
    Solution(vector<int>& w) {
        int prefixSum = 0;
        for (int weight : w) {
            prefixSum += weight;
            prefixSums.push_back(prefixSum);
        }
        totalSum = prefixSum;
    }

    int pickIndex() {
        double target = totalSum * ((double) rand() / RAND_MAX);
        for (int i = 0; i < prefixSums.size(); ++i) {
            if (target < prefixSums[i]) {
                return i;
            }
        }
        return prefixSums.size() - 1;
    }
};{}
    

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

Задача: 39. Combination Sum Сложность: medium Дан массив уникальных чисел candidates и целевое число target. Нужно вернуть все уникальные комбинации чисел из candidates, сумма которых равна target. Одно и то же число можно использовать неограниченное количество раз. Пример:

    
        Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
{}
    

👨‍💻 Алгоритм: 1⃣Используем рекурсивный бэктрекинг: если остаток суммы remain == 0 — комбинация найдена, добавляем в результат. 2⃣Если remain < 0 — выходим из текущей ветки (комбинация невалидна). 3⃣Для каждой позиции i от start до конца candidates, пробуем включить элемент в комбинацию, вызываем рекурсию с уменьшенным remain, и откатываемся (pop_back) после вызова. 😎 Решение:

    
        class Solution {
public:
    void backtrack(int remain, vector<int>& comb, int start,
                   const vector<int>& candidates,
                   vector<vector<int>>& results) {
        if (remain == 0) {
            results.push_back(comb);
            return;
        } else if (remain < 0) {
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            comb.push_back(candidates[i]);
            backtrack(remain - candidates[i], comb, i, candidates, results);
            comb.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> comb;

        backtrack(target, comb, 0, candidates, results);
        return results;
    }
};{}
    

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

Задача: 710. Random Pick with Blacklist Сложность: hard Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список. Пример:

    
        Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]{}
    

👨‍💻 Алгоритм: 1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список. 2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка. 3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение. 😎 Решение:

    
        class Solution {
public:
    Solution(int n, std::vector<int>& blacklist) {
        bound = n - blacklist.size();
        std::unordered_set<int> blackset(blacklist.begin(), blacklist.end());
        int whitelist = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (blackset.count(whitelist)) {
                    whitelist++;
                }
                map[b] = whitelist;
                whitelist++;
            }
        }
    }
    
    int pick() {
        int r = rand() % bound;
        return map.count(r) ? map[r] : r;
    }
    
private:
    std::unordered_map<int, int> map;
    int bound;
};{}
    

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

Задача: 680. Valid Palindrome II Сложность: easy Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее. Пример:

    
        Input: s = "aba"
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом. 2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов. 3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true 😎 Решение:

    
        class Solution {
    bool checkPalindrome(const string& s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
public:
    bool validPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        
        while (i < j) {
            if (s[i] != s[j]) {
                return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
};{}
    

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

Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример:

    
        Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0{}
    

👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:

    
        class Solution {
public:
    int depthFirstSearch(int n, int k, int rootVal) {
        if (n == 1) return rootVal;
        int totalNodes = 1 << (n - 1);
        if (k > totalNodes / 2) {
            int nextRootVal = rootVal == 0 ? 1 : 0;
            return depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
        } else {
            int nextRootVal = rootVal == 0 ? 0 : 1;
            return depthFirstSearch(n - 1, k, nextRootVal);
        }
    }

    int kthGrammar(int n, int k) {
        return depthFirstSearch(n, k, 0);
    }
};{}
    

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

Задача: 171. Excel Sheet Column Number Сложность: easy Дана строка columnTitle, представляющая название столбца в Excel (например, "A", "AB", "ZY"). Нужно вернуть соответствующий номер столбца. Пример:

    
        Input: "A" → Output: 1
{}
    

👨‍💻 Алгоритм: 1⃣Представим строку как число в 26-ричной системе счисления, где A = 1, B = 2, ..., Z = 26. 2⃣Проходим по строке слева направо, на каждом шаге умножая результат на 26 и прибавляя значение текущего символа (s[i] - 'A' + 1). 3⃣Таким образом, "AB" = 1×26 + 2 = 28. 😎 Решение:

    
        class Solution {
public:
    int titleToNumber(string s) {
        int result = 0;
        for (char c : s) {
            result = result * 26 + (c - 'A' + 1);
        }
        return result;
    }
};{}
    

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

Задача: 906. Super Palindromes Сложность: hard Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию. Пример:

    
        Input: left = "4", right = "1000"
Output: 4{}
    

👨‍💻 Алгоритм: 1⃣Найти все палиндромы до корня из right. 2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right]. 3⃣Подсчитать количество таких суперпалиндромов. 😎 Решение:

    
        class Solution {
public:
    bool isPalindrome(long long x) {
        string s = to_string(x);
        return s == string(s.rbegin(), s.rend());
    }

    int superpalindromesInRange(string left, string right) {
        long long leftNum = stoll(left);
        long long rightNum = stoll(right);
        int count = 0;

        for (int i = 1; i < 100000; i++) {
            string s = to_string(i);
            long long palin1 = stoll(s + string(s.rbegin(), s.rend()));
            long long palin2 = stoll(s + string(s.rbegin() + 1, s.rend()));

            if (palin1 * palin1 > rightNum) {
                break;
            }
            if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
                count++;
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
                count++;
            }
        }

        return count;
    }
};{}
    

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

Задача: 771. Jewels and Stones Сложность: medium Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

    
        Input: jewels = "aA", stones = "aAAbbbb"
Output: 3{}
    

👨‍💻 Алгоритм: 1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям. 2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels. 3⃣Если символ содержится в множестве, увеличьте счетчик. В конце верните значение счетчика, которое будет количеством камней, являющихся драгоценностями. 😎 Решение:

    
        class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int ans = 0;
        for (char s : S)
            for (char j : J)
                if (j == s) {
                    ans++;
                    break;
                }
        return ans;
    }
};{}
    

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

Задача: 685. Redundant Connection II Сложность: hard В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей. Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi. Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве. Пример:

    
        Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]{}
    

👨‍💻 Алгоритм: 1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра. 2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл. 3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов. 😎 Решение:

    
        class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        unordered_map<int, int> parent;
        vector<vector<int>> candidates;
        for (auto& edge : edges) {
            if (parent.count(edge[1])) {
                candidates.push_back({parent[edge[1]], edge[1]});
                candidates.push_back(edge);
            } else {
                parent[edge[1]] = edge[0];
            }
        }

        int root = orbit(1, parent).node;
        if (candidates.empty()) {
            auto cycle = orbit(root, parent).seen;
            vector<int> ans = {0, 0};
            for (auto& edge : edges) {
                if (cycle.count(edge[0]) && cycle.count(edge[1])) {
                    ans = edge;
                }
            }
            return ans;
        }

        unordered_map<int, vector<int>> children;
        for (auto& p : parent) {
            children[p.second].push_back(p.first);
        }

        vector<bool> seen(N + 1, false);
        seen[0] = true;
        stack<int> stk;
        stk.push(root);
        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            if (!seen[node]) {
                seen[node] = true;
                for (int c : children[node]) {
                    stk.push(c);
                }
            }
        }
        for (bool b : seen) {
            if (!b) {
                return candidates[0];
            }
        }
        return candidates[1];
    }

private:
    struct OrbitResult {
        int node;
        unordered_set<int> seen;
        OrbitResult(int n, unordered_set<int> s) : node(n), seen(s) {}
    };

    OrbitResult orbit(int node, unordered_map<int, int>& parent) {
        unordered_set<int> seen;
        while (parent.count(node) && !seen.count(node)) {
            seen.insert(node);
            node = parent[node];
        }
        return OrbitResult(node, seen);
    }
};{}
    

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

Задача: 717. 1-bit and 2-bit Characters Сложность: easy У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным. Пример:

    
        Input: bits = [1,0,0]
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте индекс для итерации по массиву. 2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1. 3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат. 😎 Решение:

    
        bool isOneBitCharacter(vector<int>& bits) {
    int i = 0;
    while (i < bits.size() - 1) {
        i += bits[i] + 1;
    }
    return i == bits.size() - 1;
}{}
    

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