C/C++ | LeetCode

Kanalga Telegram’da o‘tish

Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv

Ko'proq ko'rsatish

Tarmoq:easyoffer Rossiya153 311 Texnologiyalar & Aralashmalar24 000

3 238

Obunachilar

+424 soatlar

+127 kunlar

+230 kunlar

243

Post ko'rishlar

~ 13124 soatlar

~ 15948 soatlar

7.50%

Muloqot nisbati

Ma'lumot yo'q

Kuniga postlar

Ads index

beta

Postlar arxiv

3 238

Задача: 1802. Maximum Value at a Given Index in a Bounded Array Сложность: medium Даны три положительных целых числа: n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям: - nums.length == n - nums[i] является положительным целым числом, где 0 <= i < n. - abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1. - Сумма всех элементов массива nums не превышает maxSum. - nums[index] максимально возможен. Верните значение nums[index] в построенном массиве. Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае. Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

👨‍💻 Алгоритм: 1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value. 2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1. 3⃣Верните left по завершении бинарного поиска. 😎 Решение:

class Solution {
private:
    long getSum(int index, int value, int n) {
        long count = 0;
        if (value > index) {
            count += (long)(value + value - index) * (index + 1) / 2;
        } else {
            count += (long)(value + 1) * value / 2 + index - value + 1;
        }
        if (value >= n - index) {
            count += (long)(value + value - n + 1 + index) * (n - index) / 2;
        } else {
            count += (long)(value + 1) * value / 2 + n - index - value;
        }
        return count - value;
    }

public:
    int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (getSum(index, mid, n) <= maxSum) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

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

3 238

Задача: 892. Surface Area of 3D Shapes Сложность: easy Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности. Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

int surfaceArea(vector<vector<int>>& grid) {
    int n = grid.size();
    int area = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2;
            }
            if (i > 0) {
                area -= min(grid[i][j], grid[i-1][j]) * 2;
            }
            if (j > 0) {
                area -= min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return area;
}

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

3 238

Задача: 931. Minimum Falling Path Sum Сложность: medium Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1). Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

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

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> dp(matrix[0]);
        
        for (int i = 1; i < n; ++i) {
            vector<int> newDp(n, 0);
            for (int j = 0; j < n; ++j) {
                newDp[j] = matrix[i][j] + min({dp[j], j > 0 ? dp[j - 1] : INT_MAX, j < n - 1 ? dp[j + 1] : INT_MAX});
            }
            dp = newDp;
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};

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

3 238

Задача: 210. Course Schedule II Сложность: medium Дано число numCourses и список пар prerequisites, где каждая пара [a, b] означает: чтобы взять курс a, нужно сначала пройти курс b. Верните один из возможных порядков прохождения курсов. Если пройти все курсы невозможно (из-за циклов) — верните пустой массив. Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]

👨‍💻 Алгоритм: 1⃣Построение графа и подготовка к DFS Создаем список смежности adjList, где adjList[b] содержит все курсы, зависящие от b. Каждый курс помечаем цветом: WHITE = 1 — не посещён GRAY = 2 — в процессе обработки BLACK = 3 — полностью обработан 2⃣Обход в глубину (DFS) и детектирование цикла Для каждого непосещённого узла запускаем dfs. Если во время обхода обнаруживаем цикл (возврат к GRAY узлу), значит, пройти курсы невозможно. 3⃣Формирование ответа После завершения DFS по всем узлам формируем порядок курсов из стека (или массива) topologicalOrder, инвертируя его. 😎Решение:

cppКопироватьРедактироватьclass Solution {
public:
    int WHITE = 1;
    int GRAY = 2;
    int BLACK = 3;

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        bool isPossible = true;
        map<int, int> color;
        map<int, vector<int>> adjList;
        vector<int> topologicalOrder;

        for (int i = 0; i < numCourses; i++) color[i] = WHITE;

        for (vector<int> relation : prerequisites) {
            int dest = relation[0];
            int src = relation[1];
            adjList[src].push_back(dest);
        }

        for (int i = 0; i < numCourses && isPossible; i++) {
            if (color[i] == WHITE) {
                dfs(i, color, adjList, isPossible, topologicalOrder);
            }
        }

        vector<int> order;
        if (isPossible) {
            order.resize(numCourses);
            for (int i = 0; i < numCourses; i++) {
                order[i] = topologicalOrder[numCourses - i - 1];
            }
        }
        return order;
    }

    void dfs(int node, map<int, int>& color, map<int, vector<int>>& adjList,
             bool& isPossible, vector<int>& topologicalOrder) {
        if (!isPossible) return;
        color[node] = GRAY;

        for (int neighbor : adjList[node]) {
            if (color[neighbor] == WHITE) {
                dfs(neighbor, color, adjList, isPossible, topologicalOrder);
            } else if (color[neighbor] == GRAY) {
                isPossible = false;
            }
        }

        color[node] = BLACK;
        topologicalOrder.push_back(node);
    }
};

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

3 238

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти Вот отсортированная база с тонной материала (постепенно пополняется): (363 видео, 87 книги) — Python (415 видео, 68 книги) — Frontend (143 видео, 33 книги) — ИБ/Хакинг (352 видео, 89 книги) — С/С++/C# (343 видео, 87 книги) — Java/QA (176 видео, 32 книги) — Git/Linux (174 видео, 91 книги) — DevOps (167 видео, 53 книги) — PHP/1С (227 видео, 83 книги) — SQL/БД (114 видео, 77 книги) — Сисадмин (107 видео, 43 книги) — BA/SA (181 видео, 32 книги) — Go/Rust (167 видео, 43 книги) — Kotlin/Swift (112 видео, 24 книги) — Flutter (137 видео, 93 книги) — DS/ML (113 видео, 82 книги) — GameDev (183 видео, 37 книги) — Дизайн (136 видео, 33 книги) — PM/HR Скачивать ничего не нужно — все выложили в Telegram

3 238

Задача: 678. Valid Parenthesis String Сложность: medium Создайте карту, которая позволяет выполнять следующие действия: Отображает строковый ключ на заданное значение. Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке. Реализуйте класс MapSum: Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой. Следующие правила определяют допустимую строку: Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'. Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('. Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'. '*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "". Пример:

Input: s = "()"
Output: true
Example 2:

👨‍💻 Алгоритм: 1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString. 2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true. 3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid. 😎 Решение:

class Solution {
public: 
    bool checkValidString(string s) {
        vector<vector<int>> memo(s.size(), vector<int>(s.size(), -1));
        return isValidString(0, 0, s, memo);
    }
private: 
    bool isValidString(int index, int openCount, const string & str, vector < vector < int >> & memo) {
        if (index == str.size()) {
            return openCount == 0;
        }

        if (memo[index][openCount] != -1) {
            return memo[index][openCount];
        }

        bool isValid = false;
        if (str[index] == '*') {
            isValid |= isValidString(index + 1, openCount + 1, str, memo);
            if (openCount) {
                isValid |= isValidString(index + 1, openCount - 1, str, memo);
            }
            isValid |= isValidString(index + 1, openCount, str, memo);
        } else {
            if (str[index] == '(') {
                isValid = isValidString(index + 1, openCount + 1, str, memo);
            } else if (openCount) {
                isValid = isValidString(index + 1, openCount - 1, str, memo);
            }
        }

        return memo[index][openCount] = isValid;
    }
};

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

3 238

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label Сложность: medium Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]). Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве. Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i. Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов. Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

👨‍💻 Алгоритм: 1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X. 2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями. 3⃣Начните обход в глубину (DFS). 😎 Решение:

class Solution {
public:
    vector<int> dfs(int node, int parent, unordered_map<int, vector<int>>& adj, string& labels, vector<int>& ans) {
        vector<int> nodeCounts(26, 0);
        nodeCounts[labels[node] - 'a'] = 1;

        for (int child : adj[node]) {
            if (child == parent) {
                continue;
            }
            vector<int> childCounts = dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }

    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        unordered_map<int, vector<int>> adj;
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        vector<int> ans(n, 0);
        dfs(0, -1, adj, labels, ans);
        return ans;
    }
};

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

3 238

Задача: 1061. Lexicographically Smallest Equivalent String Сложность: medium Даны две строки одинаковой длины s1 и s2, а также строка baseStr. Мы говорим, что символы s1[i] и s2[i] эквивалентны. Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности. Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2. Пример:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

👨‍💻 Алгоритм: 1⃣Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов. 2⃣Итеративно обрабатывайте каждый символ от 0 до 25: Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar. Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr. 3⃣Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar. 😎 Решение:

class Solution {
public:
    void DFS(int src, array<array<int, 26>, 26>& adjMatrix, array<int, 26>& visited, vector<int>& component, int& minChar) {
        visited[src] = 1;
        component.push_back(src);
        minChar = min(minChar, src);
        for (int i = 0; i < 26; i++) {
            if (adjMatrix[src][i] && !visited[i]) {
                DFS(i, adjMatrix, visited, component, minChar);
            }
        }
    }

    string smallestEquivalentString(string s1, string s2, string baseStr) {
        array<array<int, 26>, 26> adjMatrix = {0};
        for (int i = 0; i < s1.size(); i++) {
            adjMatrix[s1[i] - 'a'][s2[i] - 'a'] = 1;
            adjMatrix[s2[i] - 'a'][s1[i] - 'a'] = 1;
        }
        array<int, 26> mappingChar;
        iota(mappingChar.begin(), mappingChar.end(), 0);
        array<int, 26> visited = {0};
        for (int c = 0; c < 26; c++) {
            if (!visited[c]) {
                vector<int> component;
                int minChar = 27;
                DFS(c, adjMatrix, visited, component, minChar);
                for (int vertex : component) {
                    mappingChar[vertex] = minChar;
                }
            }
        }
        string ans;
        for (char c : baseStr) {
            ans += (char)(mappingChar[c - 'a'] + 'a');
        }
        return ans;
    }
};

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

3 238

Задача: 1342. Number of Steps to Reduce a Number to Zero Сложность: easy Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля. На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1. Пример:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

👨‍💻 Алгоритм: 1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2. 2⃣Если число нечетное (number % 2 == 1), вычтите из него 1. 3⃣После выполнения каждого из этих действий увеличивайте счетчик шагов на 1, чтобы в конце вернуть его значение. 😎 Решение:

int numberOfSteps(int num) {
    int steps = 0;
    while (num != 0) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num -= 1;
        }
        steps++;
    }
    return steps;
}

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

3 238

Задача: 285. Inorder Successor in BST Сложность: medium Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null. Преемник узла p — это узел с наименьшим ключом, который больше p.val. Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

👨‍💻 Алгоритм: 1⃣Определение переменных класса: Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть. 2⃣Обработка двух случаев: В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента. Правый дочерний элемент существует: - присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве. Правый дочерний элемент не существует: - определите функцию inorderCase2 и передайте ей узел и узел p. - выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла. - когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции. - наконец, верните inorderSuccessorNode как результат. 3⃣Итерация и обновление: В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент. 😎 Решение:

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    TreeNode* previous;
    TreeNode* inorderSuccessorNode;

public:
    Solution() : previous(nullptr), inorderSuccessorNode(nullptr) {}

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (p->right != nullptr) {
            TreeNode* leftmost = p->right;
            while (leftmost->left != nullptr) {
                leftmost = leftmost->left;
            }
            inorderSuccessorNode = leftmost;
        } else {
            inorderCase2(root, p);
        }
        return inorderSuccessorNode;
    }

private:
    void inorderCase2(TreeNode* node, TreeNode* p) {
        if (node == nullptr) {
            return;
        }

        inorderCase2(node->left, p);

        if (previous == p && inorderSuccessorNode == nullptr) {
            inorderSuccessorNode = node;
            return;
        }

        previous = node;

        inorderCase2(node->right, p);
    }
};

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

3 238

Задача: 642. Design Search Autocomplete System Сложность: hard Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        root = new TrieNode();
        current = root;
        for (int i = 0; i < sentences.size(); ++i) {
            add(sentences[i], times[i]);
        }
    }

    vector<string> input(char c) {
        if (c == '#') {
            add(currentPrefix, 1);
            currentPrefix = "";
            current = root;
            return {};
        }

        currentPrefix += c;
        if (current->children.find(c) == current->children.end()) {
            current->children[c] = new TrieNode();
        }
        current = current->children[c];
        return search(current);
    }

private:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        unordered_map<string, int> count;
    };

    TrieNode* root;
    TrieNode* current;
    string currentPrefix;

    void add(const string& sentence, int times) {
        TrieNode* node = root;
        for (char c : sentence) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
            node->count[sentence] += times;
        }
    }

    vector<string> search(TrieNode* node) {
        priority_queue<pair<int, string>> pq;
        for (const auto& p : node->count) {
            pq.push({p.second, p.first});
            if (pq.size() > 3) {
                pq.pop();
            }
        }

        vector<string> result(pq.size());
        for (int i = pq.size() - 1; i >= 0; --i) {
            result[i] = pq.top().second;
            pq.pop();
        }
        return result;
    }
};
        this.prefix += c;
        let node = this.root;
        for (const char of this.prefix) {
            if (!node.children.has(char)) {
                return [];
            }
            node = node.children.get(char);
        }

        const pq = Array.from(node.count.entries()).sort((a, b) => {
            if (b[1] === a[1]) {
                return a[0].localeCompare(b[0]);
            } else {
                return b[1] - a[1];
            }
        });

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

3 238

Задача: 787. Cheapest Flights Within K Stops Сложность: medium Есть n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] указывает на то, что существует рейс из города fromi в город toi с ценой pricei. Также даны три целых числа src, dst и k. Верните самую дешевую цену от src до dst с не более чем k остановками. Если такого маршрута нет, верните -1. Пример:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

👨‍💻 Алгоритм: 1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X и соответствующую цену, которую нужно заплатить, чтобы перейти к соседу. Инициализируйте массив dist, хранящий минимальную цену для достижения узла из узла src. Инициализируйте его большими значениями. Инициализируйте очередь, хранящую пары {node, distance}. Изначально очередь должна содержать только {src, 0}. Создайте переменную stops и установите ее значение равным 0. 2⃣Выполняйте поиск в ширину (BFS), пока очередь не станет пустой или пока stops > k. Итерируйте по всем узлам на определенном уровне. Это будет сделано путем запуска вложенного цикла и посещения всех узлов, которые в данный момент находятся в очереди. В каждой паре {node, distance} итерируйте по всем соседям узла. Для каждого соседа проверьте, меньше ли dist[neighbor] чем distance + цена ребра. Если это так, обновите dist[neighbor] и добавьте {neighbor, dist[neighbor]} в очередь. 3⃣После итерации по всем узлам на текущем уровне увеличьте stops на один. Мы посетили все узлы на определенном уровне и готовы посетить следующий уровень узлов. Когда мы достигнем условия, при котором либо очередь станет пустой, либо stops == k, у нас будет наш ответ в dist[dst]. Если dist[dst] не изменилось с начального большого значения, значит, мы никогда не достигли его, и следует вернуть -1. 😎 Решение:

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& e : flights) {
            adj[e[0]].push_back({e[1], e[2]});
        }
        vector<int> dist(n, numeric_limits<int>::max());
        queue<pair<int, int>> q;
        q.push({src, 0});
        int stops = 0;

        while (stops <= k && !q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [node, distance] = q.front();
                q.pop();
                for (auto& [neighbour, price] : adj[node]) {
                    if (price + distance >= dist[neighbour]) continue;
                    dist[neighbour] = price + distance;
                    q.push({neighbour, dist[neighbour]});
                }
            }
            stops++;
        }
        return dist[dst] == numeric_limits<int>::max() ? -1 : dist[dst];
    }
};

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

3 238

Repost from easyoffer

База 1000+ реальных собеседований теперь встроена в easyoffer Смотрите, как другие кандидаты отвечают на вопросы, решают задачи и проходят этапы на реальных собеседованиях от топовых компаний. Подготовьтесь к своему собеседованию с двойной уверенностью. Напоминаем, что сегодня последний день Чёрной Пятницы 👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/

3 238

Задача: 1662. Check If Two String Arrays are Equivalent Сложность: easy Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае. Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку. Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

👨‍💻 Алгоритм: 1⃣Построение списка символов для word2: Создайте список list2 для хранения всех символов из массива строк word2. 2⃣Итерация по word1 и проверка соответствующих символов: Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2. 3⃣Возврат результата: Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают. 😎 Решение:

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        string list2;
        for (const string& s : word2) {
            list2 += s;
        }

        int index = 0;
        int list2Length = list2.size();

        for (const string& s : word1) {
            for (char c : s) {
                if (index >= list2Length || c != list2[index]) {
                    return false;
                }
                index++;
            }
        }

        return index == list2Length;
    }
};

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

3 238

Задача: 991. Broken Calculator Сложность: medium Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно: Умножить число на экране на 2, или Вычесть 1 из числа на экране. Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе. Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
};

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

3 238

Задача: 1033. Moving Stones Until Consecutive Сложность: medium На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть. Пример:

Input: a = 3, b = 5, c = 1
Output: [1,2]

👨‍💻 Алгоритм: 1⃣Сортировка позиций: Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z. 2⃣Вычисление минимальных ходов: Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0. Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1. В остальных случаях минимальное количество ходов равно 2. 3⃣Вычисление максимальных ходов: Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1). 😎 Решение:

vector<int> numMovesStones(int a, int b, int c) {
    vector<int> stones = {a, b, c};
    sort(stones.begin(), stones.end());
    int x = stones[0], y = stones[1], z = stones[2];
    int min_moves = (y - x <= 2 || z - y <= 2) ? ((y - x == 1 && z - y == 1) ? 0 : 1) : 2;
    int max_moves = (y - x - 1) + (z - y - 1);
    return {min_moves, max_moves};
}

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

3 238

Задача: 1339. Maximum Product of Splitted Binary Tree Сложность: medium Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным. Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после. Пример:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

👨‍💻 Алгоритм: 1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке. 2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева. 3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7. 😎 Решение:

class Solution {
    vector<int> allSums;
    
public:
    int maxProduct(TreeNode* root) {
        long totalSum = treeSum(root);
        long best = 0;
        for (long sum : allSums) {
            best = max(best, sum * (totalSum - sum));
        }
        return (int)(best % 1000000007);
    }
    
private:
    int treeSum(TreeNode* subroot) {
        if (!subroot) return 0;
        int leftSum = treeSum(subroot->left);
        int rightSum = treeSum(subroot->right);
        int totalSum = leftSum + rightSum + subroot->val;
        allSums.push_back(totalSum);
        return totalSum;
    }
};

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

3 238

Repost from easyoffer

Черная пятница на easyoffer Скидка 70% на PRO до 29 ноября. 👉 https://easyoffer.ru/

3 238

Задача: 860. Lemonade Change Сложность: easy На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5. Обратите внимание, что изначально у вас нет никакой сдачи. Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае. Пример:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

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

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

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

3 238

Задача: 1063. Number of Valid Subarrays Сложность: hard Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

👨‍💻 Алгоритм: 1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке. 2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек. 3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans. 😎 Решение:

class Solution {
public:
    int validSubarrays(vector<int>& nums) {
        int ans = 0;
        stack<int> st;
        
        for (int i = 0; i < nums.size(); i++) {
            while (!st.empty() && nums[i] < nums[st.top()]) {
                ans += (i - st.top());
                st.pop();
            }
            st.push(i);
        }
        
        while (!st.empty()) {
            ans += (nums.size() - st.top());
            st.pop();
        }
        
        return ans;
    }
};

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