C/C++ | LeetCode

Откройте Китай в незабываемом круизе по Янцзы 5-дневный круиз на лайнере 5*+ с балконными каютами. Русскоязычные группы и гид – комфорт на каждом этапе путешествия! ✅ Пекин – Запретный город, Великая китайская стена и Храм Неба ✅ Шанхай – Сад Юй Юань, небоскрёбы и вечерний мини-круиз по Хуанпу ✅ Река Янцзы – ущелья Ву и Цюйтан, мини-круиз по реке Богини ✅ Город-призрак Фэнду – мифы, легенды и древние храмы ✅ Путешествие на скоростном поезде и комфортные перелёты Питание, экскурсии, трансферы и проживание – уже включены Скидки до 9% при раннем бронировании! Выбирайте маршрут и бронируйте на сайте Узнать больше #реклама 16+ infoflot.com О рекламодателе

#medium Задача: 771. Jewels and Stones Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int ans = 0;
        for (char s : S)
            for (char j : J)
                if (j == s) {
                    ans++;
                    break;
                }
        return ans;
    }
};

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

Ошибки в коде — ключ для атаки на веб-приложения Всего одна ошибка — и данные ваших клиентов могут оказаться в руках мошенников. Иногда достаточно одной неверной строчки кода, чтобы хакеры получили доступ к информации о пользователях. Чтобы этого не произошло, важно позаботиться о безопасности еще на начальном этапе разработки. Как это сделать, расскажут эксперты «Солара» и AppSec Solutions на вебинаре 18 февраля. Вы узнаете: ✅какие языки программирования наиболее уязвимы — исследования от AppSec Solutions, ✅как проверить веб-приложение и ПО на безопасность без навыка разработки, ✅какие новые возможности появились в Solar appScreener 3.15.0. Регистрируйтесь! Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

#medium Задача: 713. Subarray Product Less Than K Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k. Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int product = 1, count = 0, left = 0;
    for (int right = 0; right < nums.size(); right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

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

VPS/VDS с GPU для бизнеса Создайте корпоративную IT-инфраструктуру с надежной защитой данных и бесперебойной работой приложений. Автоматизируйте бизнес-процессы: от сортировки писем в почтовом ящике до общения с клиентами через чат-боты. Виртуальные и выделенные сервера с GPU позволяют проводить вычисления в 10 раз быстрее, обрабатывая задачи параллельно. Выбирайте конфигурацию под свои цели: настраивайте количество виртуальных процессоров, объем оперативной памяти, жесткого диска и графического процессора. Увеличивайте или уменьшайте количество используемых ресурсов. Подключайте дополнительные мощности за пару кликов. Оставьте заявку и получите бесплатный тестовый период. Попробовать #реклама 16+ cloud.ttk.ru О рекламодателе

#medium Задача: 767. Reorganize String Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми. Верните любую возможную перестановку строки s или верните "", если это невозможно. Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет. 2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации. 3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans. 😎 Решение:

#include <queue>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    string reorganizeString(string s) {
        vector<int> charCounts(26, 0);
        for (char c : s) {
            charCounts[c - 'a']++;
        }

        priority_queue<vector<int>> pq;
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.push({charCounts[i], i + 'a'});
            }
        }
        
        string result;
        while (!pq.empty()) {
            auto first = pq.top();
            pq.pop();
            if (result.empty() || first[1] != result.back()) {
                result += char(first[1]);
                if (--first[0] > 0) {
                    pq.push(first);
                }
            } else {
                if (pq.empty()) {
                    return "";
                }
                auto second = pq.top();
                pq.pop();
                result += char(second[1]);
                if (--second[0] > 0) {
                    pq.push(second);
                }
                pq.push(first);
            }
        }

        return result;
    }
};

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

#easy Задача: 766. Toeplitz Matrix Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false. Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы. Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

👨‍💻 Алгоритм: 1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м 2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой. 3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true. 😎 Решение:

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        unordered_map<int, int> groups;
        for (int r = 0; r < matrix.size(); ++r) {
            for (int c = 0; c < matrix[0].size(); ++c) {
                if (!groups.count(r - c))
                    groups[r - c] = matrix[r][c];
                else if (groups[r - c] != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
};

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

Все новости из мира программирования на этом канале @umnyiprogrammist Подписывайтесь, чтобы не упустите ничего важного Ставь 👍 и забирай 📚 Базу знаний

Квартиры в ЖК SOKOLNIKI! Рассрочка до 2,5 лет, ПВ от 10% Видовые квартиры бизнес+ класса возле парка от 28 м² от 400 000 руб./м² Первый взнос от 10% Гибкие программы рассрочки до 2,5х лет с переходом в ипотеку Квартиры от 28м² до 135м² От студий до семейных фоматов с большими гостиными Колясочные на этаже Все для удобства родителей Дизайнерские лобби Стильные входные группы Подземный паркинг Системы хранения велосипедов и самокатов Детский сад Закрытая территория Девелопер STONE 18 лет на рынке недвижимости. 27 проектов м. "Сокольники", 12 мин. от парка Перейти на сайт Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ «КВАРТАЛ СОКОЛЬНИКИ». Финансовые услуги оказывает: ПАО "Совкомбанк". #реклама stone-sokolniki.ru О рекламодателе

#hard Задача: 765. Couples Holding Hands Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки. Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1). Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами. Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

class Solution {
public:
    int N;
    vector<vector<int>> pairs;

    int minSwapsCouples(vector<int>& row) {
        N = row.size() / 2;
        pairs.resize(N, vector<int>(2));
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return min(ans1, ans2);
    }
};

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Уже есть опыт работы в ИТ, но хочешь прокачать скилы и продвинуться в карьере? Тогда скорее залетай на бесплатный ИТ-интенсив в Открытых школах Т1. Открытые школы — это возможность усилить свои навыки и получить оффер в ИТ-холдинг Т1. И все это за месяц, онлайн и в удобное вечернее время. Что ты получишь? ✅ бесплатное обучение в гибком формате: по вечерам, онлайн, из любого города РФ и РБ. ✅ материалы от HR для прокачки резюме и подготовки к интервью в Т1. ✅ много практики и уникальный рыночный опыт. ✅ поддержку опытных преподавателей и карьерный фаст-трек до мидла в Т1 для лучших выпускников. ✅ реальный шанс получить оффер в Т1. Более 1000 специалистов уже прошли этот путь — теперь твоя очередь! Регистрация до 14 марта! Подать заявку #реклама 16+ t1.ru О рекламодателе

#hard Задача: 711. Number of Distinct Islands II Вам дана двоичная матричная сетка 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;
    }
};

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

Прокачаем ваш frontend скилл с junior до middle Научим писать код, который не стыдно показать Первые 7 дней бесплатно. Попробуй! Узнать больше #реклама 16+ ykul.ru О рекламодателе

Ищу работу пол года Практически под каждым постом в этом канале я вижу комментарии от людей, которые ищут работу по полгода. Это перерастает в обсуждение того, как нужно (или не нужно) искать работу, почему процесс найма сломан и как они откликались на фейковые вакансии. Честно говоря, искать работу полгода — это нонсенс. Очевидно, что человек делает что-то не так. Главная ошибка, которую совершают многие, — это создание иллюзии поиска работы. То есть человек вроде бы ищет работу, но делает это неэффективно, тратя время на нецелевые действия. Например: ➖ Просматривает вакансии перед откликом. ➖ Пытается понять, подходит ли он под вакансию. Если считает, что не подходит — не откликается. ➖ Пишет сопроводительные письма (иногда даже уникальные под каждую вакансию). ➖ Заполняет анкеты, проходит тесты. Все эти действия отнимают время, но не приводят к результату. Почему это не работает? HR-менеджер не может вручную отсмотреть 2000 откликов, оценить каждое резюме и прочитать сопроводительные письма. Поэтому компании используют ATS-системы (системы автоматического подбора), которые анализируют резюме и определяют процент его соответствия вакансии. Что делать, чтобы повысить шансы? 1️⃣ Добавить ключевые навыки в резюме — и в основной текст, и в теги. Возьмите их с easyoffer.ru 2️⃣ Убрать нерелевантный опыт, оставить только подходящий. 3️⃣ Оформить опыт так, чтобы он выглядел релевантным. Если у вас его нет, укажите проекты, стажировки или другой опыт, который можно представить как работу от 1 года. Если опыт слишком большой, сузьте его до 6 лет. 4️⃣ Откликаться на все вакансии без разбору. Если вы Junior, не ищите только стажер или Junior-вакансии — пробуйте везде. Не отказывайте себе сами, пусть это решит HR 5️⃣ Сделать резюме публичным, потому что HR-менеджеры часто ищут кандидатов не только среди откликов, но и в базе резюме. 6️⃣ Используйте ИИ по минимуму – ATS-системы считывают это и помечают "сгенерировано ИИ" ‼️ Главное правило: чем больше откликов — тем выше шанс получить оффер. Делайте резюме удобным для ATS-систем, и вас заметят. 1. Посмотрите видео о том как я вывел свою резюме в Топ1 на HH 2. Посмотрите видео как я нашел первую работу 3. Прочитайте этот кейс про оптимизацию резюме Если прям вообще тяжело. Создайте несколько разных резюме. Создайте 2, 3 да хоть 10 резюме. Настройте авто-отлики и ждите приглашения на собесы. Не нужно создавать иллюзию поиска работы, сделайте несколько простых и актуальных действий.

#hard Задача: 765. Couples Holding Hands Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки. Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1). Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами. Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

class Solution {
public:
    int N;
    vector<vector<int>> pairs;

    int minSwapsCouples(vector<int>& row) {
        N = row.size() / 2;
        pairs.resize(N, vector<int>(2));
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return min(ans1, ans2);
    }
};

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

#hard Задача: 710. Random Pick with Blacklist Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список. Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

👨‍💻 Алгоритм: 1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список. 2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка. 3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение. 😎 Решение:

class Solution {
public:
    Solution(int n, std::vector<int>& blacklist) {
        bound = n - blacklist.size();
        std::unordered_set<int> blackset(blacklist.begin(), blacklist.end());
        int whitelist = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (blackset.count(whitelist)) {
                    whitelist++;
                }
                map[b] = whitelist;
                whitelist++;
            }
        }
    }
    
    int pick() {
        int r = rand() % bound;
        return map.count(r) ? map[r] : r;
    }
    
private:
    std::unordered_map<int, int> map;
    int bound;
};

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

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

#medium Задача: 764. Largest Plus Sign Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0. Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0. Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1. Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

👨‍💻 Алгоритм: 1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки. 2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки. 3⃣Пройдите по всей сетке и для каждой ячейки определите минимальную длину луча среди четырех направлений. Эта минимальная длина будет определять порядок крестообразного знака с центром в данной ячейке. Обновите максимальный порядок крестообразного знака и верните его после завершения обхода всей сетки. Если такого знака нет, верните 0. 😎 Решение:

class Solution {
public:
    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
        unordered_set<int> banned;
        for (const auto& mine : mines) {
            banned.insert(mine[0] * N + mine[1]);
        }
        
        int ans = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int k = 0;
                while (k <= r && r < N - k && k <= c && c < N - k &&
                      !banned.count((r - k) * N + c) &&
                      !banned.count((r + k) * N + c) &&
                      !banned.count(r * N + c - k) &&
                      !banned.count(r * N + c + k)) {
                    k++;
                }
                ans = max(ans, k);
            }
        }
        return ans;
    }
};

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

#hard Задача: 591. Tag Validator Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности. Фрагмент кода считается корректным, если соблюдаются все следующие правила: Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен. Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны. Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен. Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен. Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены. < неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный). cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>. CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы. Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

#include <string>
#include <stack>
#include <regex>
using namespace std;

class Solution {
    stack<string> stack;
    bool containsTag = false;

    bool isValidTagName(const string& s, bool ending) {
        if (ending) {
            if (!stack.empty() && stack.top() == s) stack.pop();
            else return false;
        } else {
            containsTag = true;
            stack.push(s);
        }
        return true;
    }

public:
    bool isValid(string code) {
        regex pattern("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*");
        if (!regex_match(code, pattern)) return false;

        int i = 0;
        while (i < code.size()) {
            bool ending = false;
            if (stack.empty() && containsTag) return false;
            if (code[i] == '<') {
                if (code[i + 1] == '!') {
                    i = code.find("]]>", i + 1);
                    if (i == string::npos) return false;
                    continue;
                }
                if (code[i + 1] == '/') {
                    i++;
                    ending = true;
                }
                int closeIndex = code.find('>', i + 1);
                if (closeIndex == string::npos || !isValidTagName(code.substr(i + 1, closeIndex - (i + 1)), ending)) return false;
                i = closeIndex;
            }
            i++;
        }
        return stack.empty();
    }
};

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