C/C++ | LeetCode

Задача: 286. Walls and Gates Сложность: medium Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями: -1: Стена или препятствие. 0: Ворота. INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647. Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF. Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty()) return;

        int m = rooms.size();
        int n = rooms[0].size();
        queue<pair<int, int>> q;
        const int INF = 2147483647;
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto& [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
};

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

Все серии шпионского детектива «Разящий луч» уже на Иви! ❤️Повёлся на женскую провокацию и сдал себя с потрохами! 🏃‍♂️Молодой и влюблённый Ульрих делает роковую ошибку, раскрывая своё местонахождение. Ведь за ним и его матерью гонятся сотрудники ЦРУ. Парень должен стать разменной монетой в борьбе советской и американской разведок. На кону — секретный проект новейшего лазерного оружия. ⚡Включайте «Разящий луч» и узнайте, чем закончится гонка вооружений США и СССР в разгар холодной войны. Создатели сериала вдохновлялись реальными советскими учёными и разработками, что, однако, не помешало им лихо закрутить сюжет! Смотреть #реклама 16+ ivi.ru О рекламодателе

Задача: 980. Unique Paths III Сложность: hard Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть: 1, представляющая начальную клетку. Существует ровно одна начальная клетка. 2, представляющая конечную клетку. Существует ровно одна конечная клетка. 0, представляющая пустые клетки, по которым можно ходить. -1, представляющая препятствия, по которым нельзя ходить. Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз. Пример:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

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

class Solution {
public:
    int rows, cols;
    vector<vector<int>> grid;
    int path_count;

    void backtrack(int row, int col, int remain) {
        if (grid[row][col] == 2 && remain == 1) {
            path_count += 1;
            return;
        }

        int temp = grid[row][col];
        grid[row][col] = -4;
        remain -= 1;

        int row_offsets[4] = {0, 0, 1, -1};
        int col_offsets[4] = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int next_row = row + row_offsets[i];
            int next_col = col + col_offsets[i];

            if (0 > next_row || next_row >= rows || 0 > next_col || next_col >= cols)
                continue;

            if (grid[next_row][next_col] < 0)
                continue;

            backtrack(next_row, next_col, remain);
        }

        grid[row][col] = temp;
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
        int non_obstacles = 0, start_row = 0, start_col = 0;

        rows = grid.size();
        cols = grid[0].size();
        this->grid = grid;

        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row][col];
                if (cell >= 0)
                    non_obstacles += 1;
                if (cell == 1) {
                    start_row = row;
                    start_col = col;
                }
            }

        path_count = 0;

        backtrack(start_row, start_col, non_obstacles);

        return path_count;
    }
};

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

В Битрикс24 теперь можно сделать сайт за 30 секунд Серьёзно. Пишешь, что нужно, и AI сам всё собирает: тексты, картинки, оформление. ✨Никакой магии, просто умный помощник. Попробуйте — закайфуете от скорости! Начать #реклама 16+ sites-24.bitrix24.ru О рекламодателе

Задача: 370. Range Addition Сложность: medium Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci]. У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci. Верните arr после применения всех обновлений. Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

👨‍💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:

vector<int> getModifiedArray(int length, vector<vector<int> > updates)
{
    vector<int> result(length, 0);

    for (auto& tuple : updates) {
        int start = tuple[0], end = tuple[1], val = tuple[2];

        for (int i = start; i <= end; i++) {
            result[i] += val;
        }
    }

    return result;
}

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

Задача: 372. Super Pow Сложность: medium Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива. Пример:

Input: a = 2, b = [3]
Output: 8

👨‍💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        const int MOD = 1337;

        auto powmod = [](int x, int y, int mod) -> int {
            int result = 1;
            x = x % mod;
            while (y > 0) {
                if (y % 2 == 1) {
                    result = (result * x) % mod;
                }
                y = y / 2;
                x = (x * x) % mod;
            }
            return result;
        };

        function<int(int, vector<int>&, int)> superPowHelper = [&](int a, vector<int>& b, int mod) -> int {
            if (b.empty()) {
                return 1;
            }
            int last_digit = b.back();
            b.pop_back();
            int part1 = powmod(a, last_digit, mod);
            int part2 = powmod(superPowHelper(a, b, mod), 10, mod);
            return (part1 * part2) % mod;
        };

        return superPowHelper(a, b, MOD);
    }
};

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

Не платите больше. Зафиксируйте цену сегодня Сколько клиентов вы уже упустили? Каждая просроченная заявка – это деньги вашим конкурентам. amoCRM помогает закрывать сделки, пока другие теряют лиды. Мы не делаем универсальных решений для всех. Только то, что работает в продажах. И одно из лучших решений, которое вы можете принять сейчас – это зафиксировать текущую цену. С 01 сентября amoCRM станет дороже. Но если подключитесь до этой даты, мы зафиксируем текущую цену для вас — и сейчас, и при продлении. ✨ Переходите по ссылке и успейте зафиксировать свою выгоду! Узнать больше #реклама 16+ amocrm.ru О рекламодателе

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60 Сложность: medium Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0. Пример:

Input: time = [30,20,150,100,40]
Output: 3

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

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> remainders(60, 0);
        int count = 0;
        
        for (int t : time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
};

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

Продажа апартаментов в Красной Поляне ✅ АК «Поляна Пик» — премиум в Красной Поляне! 🏠 Апартаменты с ремонтом и мебелью от застройщика 💻 Под управлением DoubleTree by Hilton 4* ✨ Бассейн 25м, территория 4.5 Га Площади от 47 до 144 м² ФЗ-214 | Ипотека | Рассрочка Онлайн-показ — смотрите из любой точки мира! ⚡ Подробности на сайте! Узнать больше Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и риски. Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ ТАВРИДА СТРОЙ. Финансовые услуги оказывает: ООО СЗ ТАВРИДА СТРОЙ, ПАО "Сбербанк". #реклама invest-apartmens.online О рекламодателе

Задача: 304. Range Sum Query 2D - Immutable Сложность: medium Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа: Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2). Реализуйте класс NumMatrix: - NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2). Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени. Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями. 2⃣Предварительное вычисление сумм: Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени. 😎 Решение:

class NumMatrix {
private:
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
};

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 124. Binary Tree Maximum Path Sum Сложность: hard Вам дан массив цен, где prices[i] — цена акции в i-й день. Можно совершить не более двух транзакций. Найдите максимальную прибыль. Пример:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        if (length <= 1) return 0;

        int leftMin = prices[0];
        int rightMax = prices[length - 1];

        vector<int> leftProfits(length, 0);
        vector<int> rightProfits(length + 1, 0);

        for (int l = 1; l < length; ++l) {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = min(leftMin, prices[l]);

            int r = length - 1 - l;
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r]);
            rightMax = max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < length; ++i) {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1]);
        }

        return maxProfit;
    }
};

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1245. Tree Diameter Сложность: medium Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева. Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

👨‍💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        if (edges.empty()) return 0;

        unordered_map<int, vector<int>> graph;
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int farthest_node = 0;
        auto dfs = [&](int node, int parent) {
            int max_depth = 0;
            for (int neighbor : graph[node]) {
                if (neighbor != parent) {
                    int depth = dfs(neighbor, node);
                    if (depth + 1 > max_depth) {
                        max_depth = depth + 1;
                        farthest_node = neighbor;
                    }
                }
            }
            return max_depth;
        };

        dfs(0, -1);
        int start_node = farthest_node;

        dfs(start_node, -1);
        return dfs(farthest_node, -1);
    }
};

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One Сложность: medium Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам: Если текущее число четное, его нужно разделить на 2. Если текущее число нечетное, нужно прибавить к нему 1. Гарантируется, что для всех тестовых случаев всегда можно достичь единицы. Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

class Solution {
public:
    int numSteps(string s) {
        int operations = 0;
        while (s.size() > 1) {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int i = s.size() - 1;
                while (i >= 0 && s[i] == '1') {
                    s[i] = '0';
                    i--;
                }
                if (i < 0) {
                    s.insert(s.begin(), '1');
                } else {
                    s[i] = '1';
                }
            }
            operations++;
        }
        return operations;
    }
};

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

Баранкины и камни силы Смотрите на Кинопоиске с 7 августа. Семья таксистов обретает сверхсилы — и родственницу из XIX века. Фантастическая комедия с Андреем Федорцовым Узнать больше #реклама 16+ kinopoisk.ru О рекламодателе

Задача: 366. Find Leaves of Binary Tree Сложность: medium Дан корень бинарного дерева, соберите узлы дерева следующим образом: Соберите все листовые узлы. Удалите все листовые узлы. Повторяйте, пока дерево не станет пустым. Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

👨‍💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:

#include <vector>
#include <algorithm>
using namespace std;

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

class Solution {
private:
    vector<pair<int, int>> pairs;

    int getHeight(TreeNode* node) {
        if (!node) return -1;
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        int currHeight = max(leftHeight, rightHeight) + 1;
        pairs.push_back({currHeight, node->val});
        return currHeight;
    }

public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        getHeight(root);
        sort(pairs.begin(), pairs.end());
        vector<vector<int>> solution;
        int currentHeight = -1;
        for (const auto& p : pairs) {
            if (p.first != currentHeight) {
                solution.push_back(vector<int>());
                currentHeight = p.first;
            }
            solution.back().push_back(p.second);
        }
        return solution;
    }
};

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

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней. Напоминаю, что в честь релиза запускаем акцию. Первые 500 покупателей получат: 🚀 Скидку 50% на PRO тариф на 1 год 🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал 🔔 Подпишитесь на этот канал: https://t.me/+b2fZN17A9OQ3ZmJi В нем мы опубликуем сообщение о релизе в первую очередь