C/C++ | LeetCode

Задача: 959. Regions Cut By Slashes Сложность: medium n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области. Дана сетка grid, представленная в виде строкового массива. Верните количество областей. Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'. Пример:

    
        Input: grid = [" /","/ "]
Output: 2{}
    

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

    
        class DSU {
public:
    vector<int> parent;
    DSU(int N) : parent(N) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unionSet(int x, int y) {
        parent[find(x)] = find(y);
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int N = grid.size();
        DSU dsu(4 * N * N);
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r][c];
                
                if (val != '\\') {
                    dsu.unionSet(root + 0, root + 1);
                    dsu.unionSet(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.unionSet(root + 0, root + 2);
                    dsu.unionSet(root + 1, root + 3);
                }
                
                if (r + 1 < N) {
                    dsu.unionSet(root + 3, (root + 4 * N) + 0);
                }
                if (r - 1 >= 0) {
                    dsu.unionSet(root + 0, (root - 4 * N) + 3);
                }
                if (c + 1 < N) {
                    dsu.unionSet(root + 2, (root + 4) + 1);
                }
                if (c - 1 >= 0) {
                    dsu.unionSet(root + 1, (root - 4) + 2);
                }
            }
        }
        
        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.find(x) == x) {
                ++ans;
            }
        }
        
        return ans;
    }
};{}
    

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

Задача: 317. Shortest Distance from All Buildings Сложность: hard Дана сетка m x n, содержащая значения 0, 1 или 2, где: каждое 0 обозначает пустую землю, по которой можно свободно проходить, каждое 1 обозначает здание, через которое нельзя пройти, каждое 2 обозначает препятствие, через которое нельзя пройти. Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо. Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1. Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи. Пример:

    
        Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и запуск BFS Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки. 2⃣Обработка BFS и обновление расстояний При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX. 3⃣Обновление и возврат минимального расстояния Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1. 😎 Решение:

    
        #include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
private:
    int bfs(vector<vector<int>>& grid, int row, int col, int totalHouses) {
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int rows = grid.size(), cols = grid[0].size();
        int distanceSum = 0, housesReached = 0, steps = 0;
        queue<pair<int, int>> q;
        q.push({row, col});
        vector<vector<bool>> vis(rows, vector<bool>(cols, false));
        vis[row][col] = true;

        while (!q.empty() && housesReached != totalHouses) {
            int size = q.size();
            while (size-- > 0) {
                auto curr = q.front();
                q.pop();
                int r = curr.first, c = curr.second;
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                for (auto& dir : dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2) {
                        vis[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 0 && vis[r][c]) grid[r][c] = 2;
                }
            }
            return INT_MAX;
        }
        return distanceSum;
    }

public:
    int shortestDistance(vector<vector<int>>& grid) {
        int minDistance = INT_MAX, rows = grid.size(), cols = grid[0].size(), totalHouses = 0;
        for (const auto& row : grid) for (const auto& cell : row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = min(minDistance, bfs(grid, r, c, totalHouses));
        return minDistance == INT_MAX ? -1 : minDistance;
    }
};{}
    

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

Задача: 1025. Divisor Game Сложность: easy Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально. Пример:

    
        Input: n = 2
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Определение выигрыша: Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом. Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом. 2⃣Проверка четности числа: Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false. 3⃣Возврат результата: Возвращаем результат в зависимости от четности числа n. 😎 Решение:

    
        class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};{}
    

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

Задача: 1272. Remove Interval Сложность: medium Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше. Пример:

    
        Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]{}
    

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

    
        class Solution {
public:
    vector<vector<double>> removeInterval(vector<vector<double>>& intervals, vector<double>& toBeRemoved) {
        vector<vector<double>> result;
        for (auto& interval : intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.push_back({interval[0], min(interval[1], toBeRemoved[0])});
            }
            if (interval[1] > toBeRemoved[1]) {
                result.push_back({max(interval[0], toBeRemoved[1]), interval[1]});
            }
        }
        return result;
    }
};{}
    

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

Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Сложность: medium Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit. Пример:

    
        Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.{}
    

👨‍💻 Алгоритм: 1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна. 2⃣Итеративно добавлять элементы в дек, поддерживая условие абсолютной разницы между максимальным и минимальным элементом в окне, чтобы она была не больше limit, при необходимости сдвигая left. 3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат. 😎 Решение:

    
        #include <queue>
#include <vector>

class Solution {
public:
    int longestSubarray(std::vector<int>& nums, int limit) {
        std::priority_queue<std::pair<int, int>> maxHeap;
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> minHeap;
        int left = 0, maxLength = 0;

        for (int right = 0; right < nums.size(); ++right) {
            maxHeap.push({nums[right], right});
            minHeap.push({nums[right], right});

            while (maxHeap.top().first - minHeap.top().first > limit) {
                left = std::min(maxHeap.top().second, minHeap.top().second) + 1;
                while (maxHeap.top().second < left) {
                    maxHeap.pop();
                }
                while (minHeap.top().second < left) {
                    minHeap.pop();
                }
            }

            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};{}
    

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

Задача: 647. Palindromic Substrings Сложность: medium Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке. Пример:

    
        Input: s = "abc"
Output: 3{}
    

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

    
        int expandAroundCenter(const string& s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        count++;
        left--;
        right++;
    }
    return count;
}

int countSubstrings(string s) {
    int totalCount = 0;
    for (int i = 0; i < s.length(); i++) {
        totalCount += expandAroundCenter(s, i, i);
        totalCount += expandAroundCenter(s, i, i + 1);
    }
    return totalCount;
}{}
    

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

Задача: 813. Largest Sum of Averages Сложность: medium Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива. Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом. Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

    
        Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.{}
    

👨‍💻 Алгоритм: 1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N). 2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i). 3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)). 😎 Решение:

    
        class Solution {
public:
    double largestSumOfAverages(vector<int>& A, int K) {
        int N = A.size();
        vector<double> P(N + 1);
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        
        vector<double> dp(N);
        for (int i = 0; i < N; ++i)
            dp[i] = (P[N] - P[i]) / (N - i);
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    dp[i] = max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
                }
            }
        }
        
        return dp[0];
    }
};{}
    

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

Задача: 1357. Apply Discount Every n Orders Сложность: medium В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i]. Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара). Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100). Реализуйте класс Cashier: Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен. double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты. Пример:

    
        Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами. 2⃣Обработка каждого счета: Создайте метод getBill, который принимает массивы product и amount. Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты. Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу. 3⃣Верните итоговую сумму счета. 😎 Решение:

    
        #include <unordered_map>
#include <vector>

class Cashier {
public:
    Cashier(int n, int discount, std::vector<int>& products, std::vector<int>& prices) 
        : n(n), discount(discount), customerCount(0) {
        for (size_t i = 0; i < products.size(); ++i) {
            productsPrices[products[i]] = prices[i];
        }
    }

    double getBill(std::vector<int>& product, std::vector<int>& amount) {
        customerCount++;
        double bill = 0.0;
        
        for (size_t i = 0; i < product.size(); ++i) {
            bill += productsPrices[product[i]] * amount[i];
        }
        
        if (customerCount % n == 0) {
            bill *= (100.0 - discount) / 100.0;
        }
        
        return bill;
    }

private:
    int n;
    int discount;
    int customerCount;
    std::unordered_map<int, int> productsPrices;
};{}
    

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

Задача: 109. Convert Sorted List to Binary Search Tree Сложность: medium Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска. Пример:

    
        Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]
{}
    

👨‍💻 Алгоритм: 1⃣Так как список односвязный, для нахождения середины используем два указателя: slow_ptr (двигается на 1 узел) и fast_ptr (на 2 узла). Когда fast_ptr дойдёт до конца, slow_ptr будет в середине. 2⃣Для отделения левой части от средней сохраняем prev_ptr, который указывает на узел перед slow_ptr. Затем делаем prev_ptr->next = nullptr, чтобы отсоединить левую часть списка. 3⃣Рекурсивно строим левое поддерево из головы списка, правое — из mid->next. Базовый случай — если head == mid, это лист, возвращаем его как TreeNode. 😎 Решение:

    
        class Solution {
public:
    ListNode* findMiddleElement(ListNode* head) {
        ListNode* prevPtr = nullptr;
        ListNode* slowPtr = head;
        ListNode* fastPtr = head;

        while (fastPtr != nullptr && fastPtr->next != nullptr) {
            prevPtr = slowPtr;
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }

        if (prevPtr != nullptr) {
            prevPtr->next = nullptr;
        }
        return slowPtr;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* mid = this->findMiddleElement(head);
        TreeNode* node = new TreeNode(mid->val);

        if (head == mid) {
            return node;
        }

        node->left = this->sortedListToBST(head);
        node->right = this->sortedListToBST(mid->next);
        return node;
    }
};{}
    

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

Задача: 23. Merge k Sorted Lists Сложность: medium Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его. Пример:

    
        Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6]{}
    

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

    
        /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class compare {
public:
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;

        priority_queue<ListNode*, vector<ListNode*>, compare> minheap;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL)
                minheap.push(lists[i]);
        }

        ListNode* head = NULL;
        ListNode* temp1;

        while (!minheap.empty()) {
            ListNode* temp = minheap.top();
            minheap.pop();

            if (head == NULL) {
                head = temp;
                temp1 = temp;
            } else {
                temp1->next = temp;
                temp1 = temp;
            }

            if (temp->next != NULL) {
                minheap.push(temp->next);
            }
        }

        if (temp1 != NULL)
            temp1->next = NULL;

        return head;
    }
};{}
    

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