C/C++ | LeetCode

Гайд для РОПов по проведению эффективных вебинаров Как руководителям отделов продаж увеличить количество успешных сделок при том же объеме лидов с помощью вебинаров? Гайд от МТС Линк по обучающим вебинарам для отделов продаж. ✅ В гайде: - Как эффективнее прокачивать скиллы менеджеров и закрывать больше сделок за меньшие сроки; - Как организовать тренинг так, чтобы участники действительно подключились и дошли до финального модуля; - Как выявить слабого менеджера и улучшить его показатели; - Как сэкономить время на организации вебинара и пригласить всех участников в 2 клика. Бонус внутри: 5 прикладных советов по контролю внимания участников во время вебинара ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 899. Orderly Queue Сложность: hard Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов. Пример:

Input: s = "cba", k = 1
Output: "acb"

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

class Solution {
public:
    string orderlyQueue(string s, int k) {
        if (k == 1) {
            string minString = s;
            for (int i = 1; i < s.length(); i++) {
                string rotated = s.substr(i) + s.substr(0, i);
                if (rotated < minString) {
                    minString = rotated;
                }
            }
            return minString;
        } else {
            sort(s.begin(), s.end());
            return s;
        }
    }
};

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

👩‍💻 C# вакансии всех грейдов: удалёнка, реклок, щедрый оффер! Только с прямыми контактами в Telegram! Ноль автоотказов — живой диалог и быстрые объективные решения. 👩‍💻 C# 👩‍💻 Python 👩‍💻 Java 👣 Go 🤖 ML & DS 👩‍💻 DevOps 🔎 QA 👩‍💻 Frontend 👩‍💻 Node.js 🖥 SQL 👩‍💻 UX/UI 🖼️ PHP 👩‍💻 Mobile 📋 Analyst 💼 1C 👨‍✈️ CyberSec 👩‍💻 IT HR Подпишись чтобы не упустить свой шанс получить лучший оффер!

Задача: 543. Diameter of Binary Tree Сложность: easy Учитывая корень бинарного дерева, вернуть длину диаметра дерева. Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень. Длина пути между двумя узлами представлена числом ребер между ними. Пример:

Input: root = [1,2]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS. 2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1. 3⃣Вызвать longestPath с root. 😎 Решение:

class Solution {
    int diameter;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        diameter = 0;
        longestPath(root);
        return diameter;
    }
    
private:
    int longestPath(TreeNode* node) {
        if (node == nullptr) return 0;
        
        int leftPath = longestPath(node->left);
        int rightPath = longestPath(node->right);
        
        diameter = std::max(diameter, leftPath + rightPath);
        
        return std::max(leftPath, rightPath) + 1;
    }
};

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

Задача: 230. Kth Smallest Element in a BST Сложность: medium Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве. Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

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

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stack;
        
        while (true) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            if (--k == 0) return root->val;
            root = root->right;
        }
    }
};

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

Пасты Лесной Бальзам - удобно, выгодно, эффективно Покупайте зубные пасты Лесной Бальзам в удобных флаконах с дозатором 👍 Зубные пасты Лесной бальзам: ✅ укрепляют эмаль ✅ освежают дыхание ✅ подходят для всей семьи, в том числе для детей с 7 лет Выбирайте комплексную защиту полости рта от Лесного Бальзама и покупайте зубную пасту в три раза реже! 💰 Попробовать #реклама ozon.ru О рекламодателе

⏳ 90 акционных мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

Задача: 861. Score After Flipping Matrix Сложность: hard Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [1], k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались. 2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались. 3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека. 😎 Решение:

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int N = A.size();
        vector<long> P(N + 1);
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];

        int ans = N + 1;
        deque<int> monoq;

        for (int y = 0; y < P.size(); ++y) {
            while (!monoq.empty() && P[y] <= P[monoq.back()])
                monoq.pop_back();
            while (!monoq.empty() && P[y] >= P[monoq.front()] + K)
                ans = min(ans, y - monoq.pop_front());
            monoq.push_back(y);
        }

        return ans < N + 1 ? ans : -1;
    }
};

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

Как списать долги? Бесплатно через МФЦ! Долги от 200 000₽. Поможем бесплатно списать долг и расторгнуть все кредитные договоры! Узнать больше #реклама нет-кредит.рф О рекламодателе

Задача: 660. Remove 9 Сложность: hard Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29... Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...]. Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности. Пример:

Input: n = 9
Output: 10

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

class Solution {
public:
    int newInteger(int n) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (to_string(num).find('9') == string::npos) {
                count++;
            }
        }
        return num;
    }
};

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank Сложность: medium У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо. Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени. Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски. Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски. Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans. 3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans. 😎 Решение:

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int num : left) {
            ans = max(ans, num);
        }
        for (int num : right) {
            ans = max(ans, n - num);
        }
        return ans;
    }
};

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

REKONFA Live 6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения. С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры. Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 930. Binary Subarrays With Sum Сложность: medium Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива. Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1;
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            currentSum += num;
            count += prefixSumCount[currentSum - goal];
            prefixSumCount[currentSum]++;
        }
        
        return count;
    }
};

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

Задача: 711. Number of Distinct Islands II Сложность: hard Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов. Пример:

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1

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

class Solution {
public:
    int numDistinctIslands2(vector<vector<int>>& grid) {
        unordered_set<string> uniqueIslands;
        
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    vector<pair<int, int>> shape;
                    dfs(grid, i, j, i, j, shape);
                    uniqueIslands.insert(normalize(shape));
                }
            }
        }
        
        return uniqueIslands.size();
    }
    
private:
    void dfs(vector<vector<int>>& grid, int i, int j, int baseI, int baseJ, vector<pair<int, int>>& shape) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        shape.emplace_back(i - baseI, j - baseJ);
        dfs(grid, i + 1, j, baseI, baseJ, shape);
        dfs(grid, i - 1, j, baseI, baseJ, shape);
        dfs(grid, i, j + 1, baseI, baseJ, shape);
        dfs(grid, i, j - 1, baseI, baseJ, shape);
    }
    
    string normalize(vector<pair<int, int>>& shape) {
        vector<vector<pair<int, int>>> shapes(8);
        for (auto& p : shape) {
            int x = p.first, y = p.second;
            shapes[0].emplace_back(x, y);
            shapes[1].emplace_back(x, -y);
            shapes[2].emplace_back(-x, y);
            shapes[3].emplace_back(-x, -y);
            shapes[4].emplace_back(y, x);
            shapes[5].emplace_back(y, -x);
            shapes[6].emplace_back(-y, x);
            shapes[7].emplace_back(-y, -x);
        }
        for (auto& s : shapes) {
            sort(s.begin(), s.end());
        }
        string minShape = to_string(shapes[0][0].first) + "," + to_string(shapes[0][0].second);
        for (auto& s : shapes) {
            string sStr;
            for (auto& p : s) {
                sStr += to_string(p.first) + "," + to_string(p.second) + ";";
            }
            minShape = min(minShape, sStr);
        }
        return minShape;
    }
};

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

Ищу желающих выполнять задачи с помощью ИИ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

Задача: 463. Island Perimeter Сложность: easy Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду. Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши). У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова. Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

👨‍💻 Алгоритм: 1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки. 2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши. 3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке. 😎 Решение:

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        
        int result = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int up = (r == 0) ? 0 : grid[r-1][c];
                    int left = (c == 0) ? 0 : grid[r][c-1];
                    int down = (r == rows-1) ? 0 : grid[r+1][c];
                    int right = (c == cols-1) ? 0 : grid[r][c+1];
                    
                    result += 4 - (up + left + right + down);
                }
            }
        }
        
        return result;
    }
};

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

Задача: 1502. Can Make Arithmetic Progression From Sequence Сложность: easy Последовательность чисел называется арифметической прогрессией, если разница между любыми двумя последовательными элементами одинаковая. Дан массив чисел arr, верните true, если массив можно переставить так, чтобы он образовал арифметическую прогрессию. В противном случае верните false. Пример:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив arr. 2⃣Запишите разницу первой пары элементов: diff = arr[1] - arr[0]. 3⃣Итерируйтесь по отсортированному массиву начиная с i = 2, проверяя, равна ли разница каждой пары элементов значению diff. Если нет, верните False. Если итерация завершена без нахождения различий, верните True. 😎 Решение:

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff = arr[1] - arr[0];
        
        for (int i = 2; i < arr.size(); ++i) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        
        return true;
    }
};

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

Бесплатный курс по дизайну: веб, графический и UX/UI Получи востребованные навыки: - создание дизайна сайтов и приложений - создание инфографики и карточек для маркетплейсов - работа в графическом редакторе Figma и др. Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰 Зарегистрироваться #реклама 16+ ydaev.ru О рекламодателе

Задача: 1014. Best Sightseeing Pair Сложность: easy Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей. Пример:

Input: values = [8,1,5,2,6]
Output: 11

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Инициализируйте переменную max_score для хранения максимальной оценки пары. Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву. 2⃣Проход по массиву: Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value. Обновите значение max_score, если текущая оценка больше. Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value. 3⃣Возврат результата: Верните значение max_score как максимальную оценку пары достопримечательностей. 😎 Решение:

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int max_score = 0;
        int max_i_plus_value = values[0];
        
        for (int j = 1; j < values.size(); ++j) {
            max_score = max(max_score, max_i_plus_value + values[j] - j);
            max_i_plus_value = max(max_i_plus_value, values[j] + j);
        }
        
        return max_score;
    }
};

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе