C/C++ | LeetCode

#medium Задача: 756. Pyramid Transition Matrix Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае. Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<char>> allowedDict;

        for (const string& pattern : allowed) {
            string key = pattern.substr(0, 2);
            char value = pattern[2];
            allowedDict[key].push_back(value);
        }

        return canBuild(bottom, allowedDict);
    }

private:
    bool canBuild(string currentLevel, unordered_map<string, vector<char>>& allowedDict) {
        if (currentLevel.size() == 1) return true;

        vector<vector<char>> nextLevelOptions;
        for (size_t i = 0; i < currentLevel.size() - 1; ++i) {
            string key = currentLevel.substr(i, 2);
            if (!allowedDict.count(key)) return false;
            nextLevelOptions.push_back(allowedDict[key]);
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }

    bool canBuildNextLevel(vector<vector<char>>& options, size_t index, string nextLevel, unordered_map<string, vector<char>>& allowedDict) {
        if (index == options.size()) return canBuild(nextLevel, allowedDict);
        for (char option : options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }
};

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

#medium Задача: 755. Pour Water Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке. Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

class Solution {
public:
    vector<int> pourWater(vector<int>& heights, int volume, int k) {
        for (int v = 0; v < volume; v++) {
            int dropIndex = k;
            for (int d : {-1, 1}) {
                int i = k;
                while (i + d >= 0 && i + d < heights.size() && heights[i + d] <= heights[i]) {
                    if (heights[i + d] < heights[i]) {
                        dropIndex = i + d;
                    }
                    i += d;
                }
                if (dropIndex != k) {
                    break;
                }
            }
            heights[dropIndex]++;
        }
        return heights;
    }
};

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

Ты готов к ИТ-собеседованию? Бесплатный воркшоп 20 марта Приглашаем айтишников на воркшоп "Искусство продавать себя или как подготовиться к собесу на все 100" Рекрутер раскроет все карты! Записывайся на воркшоп, чтобы первым узнать: — Как подготовиться к собеседованию — Как презентовать свой опыт так, чтобы тебя запомнили — Как проверяют hard skills и как к этому подготовиться — Как произвести хорошее впечатление, запомниться рекрутеру и сделать так, чтобы захотели работать именно с тобой Дата: 20 марта, 18:00 Где: Онлайн Регистрируйся, чтобы получить полезные знания и быть готовым к следующему собеседованию на 100% Зарегистрироваться #реклама 16+ my.mts-link.ru О рекламодателе

#medium Задача: 754. Reach a Number Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения. Пример:

Input: target = 2
Output: 3

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

class Solution {
public:
    int reachTarget(int target) {
        target = abs(target);
        int position = 0;
        int steps = 0;
        while (position < target || (position - target) % 2 != 0) {
            steps++;
            position += steps;
        }
        return steps;
    }
};

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

Онлайн-магистратура «DevOps-инженер облачных сервисов» День открытых дверей 26 марта в 19:00 мск | Онлайн Эксперты Яндекса и ИТМО расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Забронировать #реклама 16+ practicum.yandex.ru О рекламодателе

#medium Задача: 753. Cracking the Safe Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно. После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода. Пример:

Input: n = 1, k = 2
Output: "10"

👨‍💻 Алгоритм: 1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1]. 2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз. 3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры. 😎 Решение:

class Solution {
public:
    string crackSafe(int n, int k) {
        unordered_set<string> seen;
        string result;

        string startNode(n - 1, '0');
        dfs(startNode, k, seen, result);

        result += startNode;
        return result;
    }

private:
    void dfs(const string& node, int k, unordered_set<string>& seen, string& result) {
        for (int x = 0; x < k; ++x) {
            string neighbor = node + to_string(x);
            if (!seen.count(neighbor)) {
                seen.insert(neighbor);
                dfs(neighbor.substr(1), k, seen, result);
                result += to_string(x);
            }
        }
    }
};

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

Цены на все Серверы онлайн! Удобный конфигуратор! Серверы STSS Flagman✅ Огромный выбор решений 👍 Консультации лучших экспертов 👌 Непревзойденный сервис ❤️ Получить предложение #реклама stss.ru О рекламодателе

#medium Задача: 752. Open the Lock Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно. Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        queue<pair<string, int>> queue;
        queue.push({"0000", 0});
        unordered_set<string> visited;
        visited.insert("0000");
        
        while (!queue.empty()) {
            auto [node, steps] = queue.front();
            queue.pop();
            if (node == target) {
                return steps;
            }
            if (dead.count(node)) {
                continue;
            }
            for (auto neighbor : neighbors(node)) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    queue.push({neighbor, steps + 1});
                }
            }
        }
        
        return -1;
    }

private:
    vector<string> neighbors(const string& node) {
        vector<string> res;
        for (int i = 0; i < 4; i++) {
            string up = node;
            up[i] = (node[i] - '0' + 1) % 10 + '0';
            res.push_back(up);
            string down = node;
            down[i] = (node[i] - '0' - 1 + 10) % 10 + '0';
            res.push_back(down);
        }
        return res;
    }
};

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

#medium Задача: 751. IP to CIDR Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список. Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

👨‍💻 Алгоритм: 1⃣Преобразовать начальный IP-адрес в целое число. 2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n. 3⃣Преобразовать блоки обратно в формат CIDR и вернуть их. 😎 Решение:

class Solution {
public:
    vector<string> findCidrBlocks(string startIp, int n) {
        int start = ipToInt(startIp);
        vector<string> result;
        
        while (n > 0) {
            int maxSize = 1;
            while (maxSize <= start && maxSize <= n) {
                maxSize <<= 1;
            }
            maxSize >>= 1;
            
            while (start % maxSize != 0) {
                maxSize >>= 1;
            }
            
            result.push_back(cidr(intToIp(start), 32 - bitCount(maxSize - 1) + 1));
            start += maxSize;
            n -= maxSize;
        }
        
        return result;
    }
    
private:
    int ipToInt(const string& ip) {
        int result = 0;
        stringstream ss(ip);
        string segment;
        for (int i = 0; getline(ss, segment, '.'); ++i) {
            result = result * 256 + stoi(segment);
        }
        return result;
    }

    string intToIp(int num) {
        return to_string((num >> 24) & 255) + "." + to_string((num >> 16) & 255) + "." +
               to_string((num >> 8) & 255) + "." + to_string(num & 255);
    }

    string cidr(const string& ip, int prefixLength) {
        return ip + "/" + to_string(prefixLength);
    }

    int bitCount(int n) {
        return (int)log2(n) + 1;
    }
};

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

На easyoffer 2.0 появится: 🎯 Тренажер "Проработка вопросов" ✅ Метод интервальных повторений и флеш-карточки ✅ Персональный подход изучения на основе ваших ответов ✅ Упор на самые частые вопросы 📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос). 🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом. Уже в течение недели я объявлю о старте краудфандинговой кампании на сбор финансирования, чтобы ускорить разработку сайта. Все кто поддержит проект до официального релиза получат самые выгодные условия пользования сервисом. А именно 1 год доступа к сайту по цене месячной подписки. ‼️ Очень важно, чтобы как можно больше людей поддержали проект в первые дни, по-этому те кто окажет поддержку первыми получат еще более выгодную стоимость на годовую подписку и существенный 💎 бонус о котором я позже расскажу в этом телеграм канале. Подписывайтесь, чтобы узнать о старте проекта раньше других и воспользоваться лимитированными вознаграждениями.

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

#medium Задача: 750. Number Of Corner Rectangles Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список. Пример:

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

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

class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = i + 1; j < grid.size(); j++) {
                int numPairs = 0;
                for (int k = 0; k < grid[0].size(); k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        numPairs++;
                    }
                }
                if (numPairs > 1) {
                    count += numPairs * (numPairs - 1) / 2;
                }
            }
        }
        return count;
    }
};

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

Ваш сайт = ваши деньги. Что, если завтра его не станет? Стабильность онлайн-бизнеса напрямую зависит от работы сайта. Если клиенты не смогут оформить заказ, они не будут ждать — уйдут туда, где все работает без сбоев. Многие думают, что хакеры нападают только на крупные компании. Это миф. Ваши конкуренты могут накрутить ботов или заказать DDoS-атаку, что приведет к потерям прибыли и репутации. Как защитить сайт и избежать финансовых потерь, расскажут эксперты «Солара» на вебинаре «Безопасный сайт — прибыльный сайт: как хакерские атаки влияют на ваш доход». Вы узнате: - Почему важно поддерживать бесперебойную работу веб-ресурса; - Как киберугрозы наносят ущерб бизнесу; - Что важно при выборе защиты. Вас ждут реальные кейсы атак, которые докажут: такие проблемы касаются не только крупных компаний. Регистрируйтесь! Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

#medium Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One Дано бинарное представление целого числа в виде строки 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;
    }
};

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

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

#hard Задача: 1402. Reducing Dishes Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени. Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i]. Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд. Блюда можно готовить в любом порядке, и шеф может отказаться от некоторых блюд, чтобы достичь максимального значения. Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив satisfaction в порядке возрастания. 2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан. 3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ: Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение. Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo. Рассчитайте максимум из двух вариантов: добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1. Пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time. 😎 Решение:

class Solution {
public:
    int findMaxSatisfaction(vector<int>& satisfaction, vector<vector<int>>& memo, int index, int time) {
        if (index == satisfaction.size()) return 0;
        if (memo[index][time] != -1) return memo[index][time];

        return memo[index][time] = max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                                       findMaxSatisfaction(satisfaction, memo, index + 1, time));
    }

    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        vector<vector<int>> memo(satisfaction.size() + 1, vector<int>(satisfaction.size() + 1, -1));
        return findMaxSatisfaction(satisfaction, memo, 0, 1);
    }
};

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

Аудит СУБД со скидкой 50%: проверьте базы данных! Как работает ваша СУБД? Уверены, что она справляется с нагрузкой и не тормозит бизнес-процессы? Команда РДТЕХ предлагает профессиональный аудит СУБД со скидкой 50%! 💻 Мы проанализируем ваши базы данных на Oracle, PostgreSQL или Microsoft SQL Server, выявим слабые места и дадим рекомендации по оптимизации. Наши эксперты с опытом внедрения и поддержки СУБД помогут: ✅ Ускорить работу системы; ✅ Снизить риски сбоев; ✅ Повысить отказоустойчивость. ✨ Акция действует до конца марта! Успейте проверить свою СУБД и сэкономить. Не упустите шанс улучшить производительность ваших баз данных! Узнать больше #реклама rdtex.ru О рекламодателе

#easy Задача: 748. Shortest Completing Word Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1. Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> licenseCount = getCharCount(licensePlate);
        
        string result;
        for (const string& word : words) {
            if (isCompletingWord(word, licenseCount)) {
                if (result.empty() || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
    
private:
    unordered_map<char, int> getCharCount(const string& s) {
        unordered_map<char, int> count;
        for (char c : s) {
            if (isalpha(c)) {
                count[tolower(c)]++;
            }
        }
        return count;
    }
    
    bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
        unordered_map<char, int> wordCount;
        for (char c : word) {
            wordCount[c]++;
        }
        for (const auto& entry : licenseCount) {
            if (wordCount[entry.first] < entry.second) {
                return false;
            }
        }
        return true;
    }
};

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

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