C/C++ | LeetCode

Профессия «Аналитик данных». Рассрочка 0% Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 официальный государственный диплом 🎓если после курса не найдёте работу — мы возвращаем деньги и это зафиксировано в договоре 🎓 рассрочка 0% на 24 мес., то есть без переплаты 🎓 бессрочный доступ к лекциям и материалам, которые продолжают обновляться 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше Финансовые услуги оказывает: ПАО "Сбербанк", АО "Тинькофф Банк" и др.. #реклама 16+ eduson.academy О рекламодателе

Задача: 73. Set Matrix Zeroes Сложность: medium Дана матрица m x n, нужно обнулить всю строку и столбец, если хотя бы один элемент равен 0. Решение должно быть на месте, без использования дополнительной матрицы. Пример:

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

👨‍💻 Алгоритм: 1⃣Обход всей матрицы: Если элемент matrix[i][j] == 0, помечаем: matrix[0][j] = 0 (нужен обнулить весь столбец j) matrix[i][0] = 0 (нужен обнулить всю строку i) Первый столбец не может пересекаться с первой строкой → используем флаг isCol 2⃣Второй проход (снизу вверх, слева направо): Если matrix[i][0] == 0 или matrix[0][j] == 0, то matrix[i][j] = 0 3⃣В конце отдельно обрабатываем первую строку и первый столбец: Если matrix[0][0] == 0 → обнулить всю первую строку Если isCol == true → обнулить весь первый столбец 😎 Решение:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool isCol = false;
        int R = matrix.size();
        int C = matrix[0].size();

        for (int i = 0; i < R; i++) {
            if (matrix[i][0] == 0) {
                isCol = true;
            }
            for (int j = 1; j < C; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (matrix[0][0] == 0) {
            for (int j = 0; j < C; j++) {
                matrix[0][j] = 0;
            }
        }

        if (isCol) {
            for (int i = 0; i < R; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

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

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ eduson.academy О рекламодателе

Задача: 1263. Minimum Moves to Move a Box to Their Target Location Сложность: hard Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1. Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        auto isValid = [&](int x, int y) {
            return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
        };
        
        queue<tuple<int, int, int, int, int>> q;
        unordered_set<string> visited;
        
        int px, py, bx, by, tx, ty;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'S') {
                    px = i;
                    py = j;
                } else if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                } else if (grid[i][j] == 'T') {
                    tx = i;
                    ty = j;
                }
            }
        }
        
        q.push({px, py, bx, by, 0});
        visited.insert(to_string(px) + "," + to_string(py) + "," + to_string(bx) + "," + to_string(by));
        
        while (!q.empty()) {
            auto [px, py, bx, by, pushes] = q.front();
            q.pop();
            if (bx == tx && by == ty) {
                return pushes;
            }
            for (auto [dx, dy] : directions) {
                int npx = px + dx, npy = py + dy;
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        int nbx = bx + dx, nby = by + dy;
                        if (isValid(nbx, nby) && visited.insert(to_string(npx) + "," + to_string(npy) + "," + to_string(nbx) + "," + to_string(nby)).second) {
                            q.push({npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.insert(to_string(npx) + "," + to_string(npy) + "," + to_string(bx) + "," + to_string(by)).second) {
                        q.push({npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
};

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае. Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз. Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

class Solution {
public:
    bool isMajorityElement(vector<int>& nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num == target) {
                count++;
            }
        }
        return count > nums.size() / 2;
    }
};

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 110. Balanced Binary Tree Сложность: easy Дано бинарное дерево. Определите, является ли оно сбалансированным по высоте. Пример:

Input: root = [3,9,20,null,null,15,7] Output: true

👨‍💻 Алгоритм: 1⃣Определим функцию height, которая возвращает: -1, если узел null; 1 + max(height(left), height(right)) — в остальных случаях. 2⃣Проверим, что разность высот левого и правого поддеревьев не превышает 1. 3⃣Рекурсивно проверим, что оба поддерева также сбалансированы: если root == NULL — дерево сбалансировано (вернём true); если разность высот больше 1 — вернём false; иначе — вернём isBalanced(left) && isBalanced(right). 😎 Решение:

class Solution {
private:
    int height(TreeNode* root) {
        if (root == NULL) {
            return -1;
        }
        return 1 + max(height(root->left), height(root->right));
    }

public:
    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        return abs(height(root->left) - height(root->right)) < 2 &&
               isBalanced(root->left) && isBalanced(root->right);
    }
};

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

Задача: 657. Robot Return to Origin Сложность: easy На плоскости с координатами (0, 0) находится робот. Дана последовательность его движений, определите, возвращается ли робот в исходную точку (0, 0) после завершения всех своих движений. Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз). Верните true, если робот возвращается в исходную точку после завершения всех своих движений, или false в противном случае. Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода. Пример:

Input: moves = "UD"
Output: true

👨‍💻 Алгоритм: 1⃣Инициализация координат: Начните с координат (0, 0). 2⃣Обработка движений: Пройдите по строке moves и обновляйте координаты в зависимости от движения: 'R' увеличивает координату x на 1. 'L' уменьшает координату x на 1. 'U' увеличивает координату y на 1. 'D' уменьшает координату y на 1. 3⃣Проверка конечных координат: Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false. 😎 Решение:

class Solution {
public:
    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        for (char move : moves) {
            switch (move) {
                case 'R': x++; break;
                case 'L': x--; break;
                case 'U': y++; break;
                case 'D': y--; break;
            }
        }
        return x == 0 && y == 0;
    }
};

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

Онлайн-магистратура в IT совместно с ИТМО, МИФИ и МФТИ День открытых дверей В удобное время | Онлайн Все программы 2025, общение со студентами и экспертами из вузов и Яндекса. Ответы на вопросы. Зарегистрироваться #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 259. 3Sum Smaller Сложность: medium Дан массив целых чисел nums и число target. Нужно найти количество троек индексов i < j < k, таких что: nums[i] + nums[j] + nums[k] < target. Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Объяснение: Подходящие тройки: [-2,0,1], [-2,0,3]

👨‍💻 Алгоритм: 1⃣Отсортируйте массив nums по возрастанию, чтобы можно было применять бинарный поиск или двухуказательный подход. 2⃣Для каждого i от 0 до n - 3, зафиксируйте nums[i], и найдите количество пар (j, k), таких что nums[i] + nums[j] + nums[k] < target. 3⃣Для поиска количества пар, чья сумма меньше заданного порога, используйте бинарный поиск, чтобы найти максимальный возможный индекс k и посчитать количество допустимых комбинаций. 😎 Решение:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size() - 2; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }

private:
    int twoSumSmaller(vector<int>& nums, int startIndex, int target) {
        int sum = 0;
        for (int i = startIndex; i < nums.size() - 1; i++) {
            int j = binarySearch(nums, i, target - nums[i]);
            sum += j - i;
        }
        return sum;
    }

    int binarySearch(vector<int>& nums, int startIndex, int target) {
        int left = startIndex;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

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

Задача: 1114. Print in Order Сложность: easy Предположим, у нас есть класс:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second(). Примечание: Мы не знаем, как потоки будут планироваться в операционной системе, даже если числа в вводе подразумевают порядок выполнения. Формат ввода, который вы видите, в основном предназначен для обеспечения полноты наших тестов. Пример:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

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

#include <semaphore.h>
#include <functional>

class Foo {
protected:
    sem_t firstJobDone;
    sem_t secondJobDone;

public:
    Foo() {
        sem_init(&firstJobDone, 0, 0);
        sem_init(&secondJobDone, 0, 0);
    }

    void first(std::function<void()> printFirst) {
        printFirst();
        sem_post(&firstJobDone);
    }

    void second(std::function<void()> printSecond) {
        sem_wait(&firstJobDone);
        printSecond();
        sem_post(&secondJobDone);
    }

    void third(std::function<void()> printThird) {
        sem_wait(&secondJobDone);
        printThird();
    }
};

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

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 1496. Path Crossing Сложность: easy Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path. Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false. Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями. Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0. 2⃣Проход по строке path: Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited. 3⃣Возврат результата: Если ни одна точка не пересекалась, вернуть false. 😎 Решение:

class Solution {
public:
    bool isPathCrossing(string path) {
        unordered_map<char, pair<int, int>> moves = {
            {'N', {0, 1}}, {'S', {0, -1}}, {'E', {1, 0}}, {'W', {-1, 0}}
        };
        set<pair<int, int>> visited = {{0, 0}};
        int x = 0, y = 0;

        for (char c : path) {
            x += moves[c].first;
            y += moves[c].second;
            if (visited.count({x, y})) {
                return true;
            }
            visited.insert({x, y});
        }

        return false;
    }
};

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 38. Count and Say Сложность: medium Последовательность "Count and Say" строится по следующему принципу: countAndSay(1) = "1" countAndSay(n) — это строка, описывающая предыдущую строку (n−1), используя RLE (сжатие длиной серий), т.е. количество подряд идущих символов + сам символ. Пример:

Input: n = 4 Output: "1211"

👨‍💻 Алгоритм: 1⃣Начинаем с s = "1" как countAndSay(1). 2⃣Для каждого шага до n применяем регулярное выражение, чтобы найти группы одинаковых подряд идущих символов. 3⃣Для каждой группы записываем: длину группы + сам символ, формируя новую строку. 😎 Решение:

class Solution {
public:
    string countAndSay(int n) {
        regex e("(.)\\1*");
        string s = "1";
        for (int i = 2; i <= n; i++) {
            string t;
            for (sregex_iterator it = sregex_iterator(s.begin(), s.end(), e);
                 it != sregex_iterator(); it++) {
                t += to_string(it->str().size()) + it->str(1);
            }
            s = t;
        }
        return s;
    }
};

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 591. Tag Validator Сложность: hard Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности. Фрагмент кода считается корректным, если соблюдаются все следующие правила: Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен. Закрытый тег (не обязательно корректный) имеет точно следующий формат: <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();
    }
};

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

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

Задача: 290. Word Pattern Сложность: easy Дан шаблон из букв и строка, нужно определить, соответствует ли строка шаблону по правилу биекции между символами и словами. Пример:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

👨‍💻 Алгоритм 1⃣Разделите строку s на слова, используя пробел как разделитель. Проверьте, совпадает ли количество слов с длиной строки pattern. Если нет — верните false. 2⃣Создайте два отображения: mapChar: символ шаблона → слово mapWord: слово → символ шаблона 3⃣Итерируйтесь по шаблону и списку слов одновременно. Если отображения нарушаются (несоответствие между буквой и словом) — верните false. Если все соответствия верны — верните true. 😎 Решение

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> mapChar;
        unordered_map<string, char> mapWord;
        vector<string> words;
        stringstream ss(s);
        string word;

        while (ss >> word) {
            words.push_back(word);
        }

        if (words.size() != pattern.size()) return false;

        for (int i = 0; i < pattern.size(); ++i) {
            char c = pattern[i];
            string w = words[i];
            if (mapChar.count(c)) {
                if (mapChar[c] != w) return false;
            } else {
                if (mapWord.count(w)) return false;
                mapChar[c] = w;
                mapWord[w] = c;
            }
        }

        return true;
    }
};

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

Высшее образование дистанционно от 6700 ₽/мес. Поступи в Московский технологический институт в июне! — Высшее образование в московском вузе без выезда на сессии. — Полностью дистанционный онлайн-формат. — Обучайся дома, на работе, в путешествии. — Диплом государственного образца. — 73 направления и программы обучения. — Программа колледж + вуз без ЕГЭ. Скидка 10% на платное обучение при оплате за год. Подать заявку #реклама 16+ mti-vuz.ru О рекламодателе