C/C++ | LeetCode

Задача: 1276. Number of Burgers with No Waste of Ingredients Сложность: medium Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните []. Пример:

    
        Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]{}
    

👨‍💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:

    
        class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
            return {};
        }
        int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
        int total_small = cheeseSlices - total_jumbo;
        return {total_jumbo, total_small};
    }
};{}
    

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

Задача: 667. Beautiful Arrangement II Сложность: medium Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию: Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них. Пример:

    
        Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1{}
    

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

    
        class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> answer;
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer.push_back(left++);
            } else {
                answer.push_back(right--);
            }
        }
        
        if (k % 2 == 0) {
            for (int i = right; i >= left; i--) {
                answer.push_back(i);
            }
        } else {
            for (int i = left; i <= right; i++) {
                answer.push_back(i);
            }
        }
        
        return answer;
    }
};{}
    

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 637. Average of Levels in Binary Tree Сложность: easy Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа. Пример:

    
        Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]{}
    

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

    
        class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> queue;
        queue.push(root);
        
        while (!queue.empty()) {
            long sum = 0;
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                sum += node->val;
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
            }
            result.push_back((double) sum / count);
        }
        
        return result;
    }
};{}
    

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

Задача: 856. Score of Parentheses Сложность: medium Дана строка s, состоящая из сбалансированных скобок, верните счёт строки. Счёт сбалансированной строки скобок основывается на следующих правилах: "()" имеет счёт 1. AB имеет счёт A + B, где A и B — сбалансированные строки скобок. (A) имеет счёт 2 * A, где A — сбалансированная строка скобок. Пример:

    
        Input: s = "()"
Output: 1{}
    

👨‍💻 Алгоритм: 1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки. 2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n). 3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]). 😎 Решение:

    
        class Solution {
public:
    int scoreOfParentheses(string S) {
        return F(S, 0, S.size());
    }

    int F(string S, int i, int j) {
        int ans = 0, bal = 0;

        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }

        return ans;
    }
};{}
    

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

Задача: 100. Same Tree Сложность: easy Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения. Пример:

    
        Input: p = [1,2,3], q = [1,2,3] Output: true
{}
    

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

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

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

Задача: 362. Design Hit Counter Сложность: medium Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке. Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной. Пример:

    
        Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.{}
    

👨‍💻 Алгоритм: 1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь. 2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки. 3⃣Верните размер очереди как количество попаданий за последние 5 минут. 😎 Решение:

    
        #include <queue>

class HitCounter {
public:
    HitCounter() {}

    void hit(int timestamp) {
        hits.push(timestamp);
    }

    int getHits(int timestamp) {
        while (!hits.empty() && timestamp - hits.front() >= 300) {
            hits.pop();
        }
        return hits.size();
    }

private:
    std::queue<int> hits;
};{}
    

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

Задача: 1013. Partition Array Into Three Parts With Equal Sum Сложность: easy Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) Пример:

    
        Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true{}
    

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

    
        class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total_sum = accumulate(arr.begin(), arr.end(), 0);
        if (total_sum % 3 != 0) {
            return false;
        }
        
        int target = total_sum / 3, part_sum = 0, count = 0, n = arr.size();
        
        for (int i = 0; i < n; ++i) {
            part_sum += arr[i];
            if (part_sum == target) {
                ++count;
                part_sum = 0;
                if (count == 2 && i < n - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
};{}
    

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

Задача: 323. Number of Connected Components in an Undirected Graph Сложность: medium У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе. Верните количество связных компонентов в графе. Пример:

    
        Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
{}
    

👨‍💻 Алгоритм: 1⃣Создание списка смежности Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v. 2⃣Инициализация посещенных узлов Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин. 3⃣Подсчет компонентов Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе. 😎 Решение:

    
        class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        vector<bool> visited(n, false);
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                count++;
            }
        }

        return count;
    }

private:
    void dfs(int node, const vector<vector<int>>& adj, vector<bool>& visited) {
        stack<int> stack;
        stack.push(node);
        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            if (!visited[current]) {
                visited[current] = true;
                for (int neighbor : adj[current]) {
                    if (!visited[neighbor]) stack.push(neighbor);
                }
            }
        }
    }
};{}
    

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

Задача: 501. Find Mode in Binary Search Tree Сложность: easy Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве. Если в дереве более одной моды, верните их в любом порядке. Предположим, что BST определяется следующим образом: Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла. Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла. Оба поддерева также должны быть бинарными деревьями поиска. Пример:

    
        Input: root = [1,null,2,2]
Output: [2]{}
    

👨‍💻 Алгоритм: 1⃣Обход дерева Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values. 2⃣Поиск мод Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans. 3⃣Возврат результата Верните список ans. 😎 Решение:

    
        class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> values;
        dfs(root, values);
        
        int maxStreak = 0, currStreak = 0, currNum = 0;
        vector<int> ans;
        
        for (int num : values) {
            if (num == currNum) {
                currStreak++;
            } else {
                currStreak = 1;
                currNum = num;
            }
            
            if (currStreak > maxStreak) {
                ans = {num};
                maxStreak = currStreak;
            } else if (currStreak == maxStreak) {
                ans.push_back(num);
            }
        }
        
        return ans;
    }
    
private:
    void dfs(TreeNode* node, vector<int>& values) {
        if (!node) return;
        dfs(node->left, values);
        values.push_back(node->val);
        dfs(node->right, values);
    }
};{}
    

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