C/C++ | LeetCode

Задача: 22. Generate Parentheses Сложность: medium Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных круглых скобок. Пример:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

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

class Solution { 
public: 
    vector<string> res; 
 
    void dfs(string cur, int open, int close, int n) 
    { 
        if (cur.length() == 2 * n) 
        { 
            if (open == close) res.push_back(cur); 
            return; 
        } 
 
        if (open < n) dfs(cur + "(", open + 1, close, n); 
        if (open > close) dfs(cur + ")", open, close + 1, n); 
    } 
 
    vector<string> generateParenthesis(int n) { 
        dfs("", 0, 0, n); 
        return res; 
    } 
};

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

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary Сложность: easy Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника. Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты. Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0. 2⃣Итерация по зарплатам: Для каждой зарплаты добавить её к переменной sum. Обновить переменную minSalary, если текущая зарплата меньше её значения. Обновить переменную maxSalary, если текущая зарплата больше её значения. 3⃣Вычисление среднего значения: Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности. 😎 Решение:

class Solution {
public:
    double average(vector<int>& salary) {
        int minSalary = INT_MAX;
        int maxSalary = INT_MIN;
        int sum = 0;

        for (int sal : salary) {
            sum += sal;
            minSalary = min(minSalary, sal);
            maxSalary = max(maxSalary, sal);
        }

        return (sum - minSalary - maxSalary) / static_cast<double>(salary.size() - 2);
    }
};

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

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves Сложность: medium Вам дан массив целых чисел nums. За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение. Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов. Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int numsSize = nums.size();
        
        if (numsSize <= 4) return 0;
        
        sort(nums.begin(), nums.end());
        
        int minDiff = INT_MAX;
        
        for (int left = 0, right = numsSize - 4; left < 4; left++, right++) {
            minDiff = min(minDiff, nums[right] - nums[left]);
        }
        
        return minDiff;
    }
};

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

Задача: 83. Remove Duplicates from Sorted List Сложность: easy Дана голова отсортированного связного списка. Удалите все дубликаты, чтобы каждый элемент встречался только один раз. Верните также отсортированный связный список. Пример:

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

👨‍💻 Алгоритм: 1⃣Начинаем с текущего узла current = head и двигаемся по списку, пока current и current->next не равны NULL. 2⃣Если current->val == current->next->val, это дубликат — пропускаем next, сдвигая current->next = current->next->next. 3⃣Если значения различаются — просто переходим к следующему узлу: current = current->next. 😎 Решение:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* current = head;
        while (current != NULL && current->next != NULL) {
            if (current->next->val == current->val) {
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }
        return head;
    }
};

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

Задача: 869. Reordered Power of 2 Сложность: medium Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем. Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки. Пример:

Input: n = 1
Output: true

👨‍💻 Алгоритм: 1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations. 2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1. 3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false. 😎 Решение:

class Solution {
public:
    bool reorderedPowerOf2(int N) {
        string A = to_string(N);
        sort(A.begin(), A.end());
        for (int i = 0; i < 30; ++i) {
            string B = to_string(1 << i);
            sort(B.begin(), B.end());
            if (A == B) return true;
        }
        return false;
    }
};

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

Где вести задачи и проекты? Конечно, в Битрикс24 Бесплатный онлайн-сервис для бизнеса и совместной работы. Полный комплект для работы без хаоса. Ставьте первую задачу прямо сейчас Начать #реклама 16+ task-24.bitrix24.ru О рекламодателе

Задача: 1199. Minimum Time to Build Blocks Сложность: hard Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим. Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени. Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split. Выведите минимальное время, необходимое для строительства всех блоков. Изначально есть только один рабочий. Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

#include <vector>
#include <queue>

class Solution {
public:
    int minBuildTime(std::vector<int>& blocks, int split) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq(blocks.begin(), blocks.end());
        
        while (pq.size() > 1) {
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
            pq.push(split + y);
        }
        
        return pq.top();
    }
};

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

Задача: 722. Remove Comments Сложность: medium Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными. Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой. Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

vector<string> removeComments(vector<string>& source) {
    bool inBlock = false;
    string buffer;
    vector<string> result;
    
    for (const string& line : source) {
        int i = 0;
        if (!inBlock) buffer.clear();
        while (i < line.size()) {
            if (!inBlock && i + 1 < line.size() && line[i] == '/' && line[i + 1] == '*') {
                inBlock = true;
                i++;
            } else if (inBlock && i + 1 < line.size() && line[i] == '*' && line[i + 1] == '/') {
                inBlock = false;
                i++;
            } else if (!inBlock && i + 1 < line.size() && line[i] == '/' && line[i + 1] == '/') {
                break;
            } else if (!inBlock) {
                buffer.push_back(line[i]);
            }
            i++;
        }
        if (!inBlock && !buffer.empty()) {
            result.push_back(buffer);
        }
    }
    return result;
}

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

Задача: 249. Group Shifted Strings Сложность: medium Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

👨‍💻 Алгоритм: 1⃣Для каждой строки вычисляем нормализованный ключ, сдвигая строку так, чтобы она начиналась с 'a'. Используем формулу (буква - сдвиг + 26) % 26 + 'a'. 2⃣Сохраняем строки в unordered_map, где ключом служит нормализованная строка, а значением — список всех строк, попадающих под эту группу. 3⃣Формируем результат из всех списков строк, сгруппированных по ключу, и возвращаем его. 😎 Решение:

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    char shiftLetter(char letter, int shift) {
        return (letter - shift + 26) % 26 + 'a';
    }
    
    string getHash(string& s) {
        int shift = s[0];
        string hashKey;
        for (char letter : s) {
            hashKey += shiftLetter(letter, shift);
        }
        return hashKey;
    }
    
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> mapHashToList;
        for (string& str : strings) {
            string hashKey = getHash(str);
            mapHashToList[hashKey].push_back(str);
        }

        vector<vector<string>> groups;
        for (auto& it : mapHashToList) {
            groups.push_back(it.second);
        }

        return groups;
    }
};

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

Задача: 1133. Largest Unique Number Сложность: easy Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1. Пример:

Input: nums = [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

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

class Solution {
public:
    int largestUniqueNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        
        for (int num : nums) {
            count[num]++;
        }
        
        int result = -1;
        for (auto& entry : count) {
            if (entry.second == 1) {
                result = max(result, entry.first);
            }
        }
        
        return result;
    }
};

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

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

Задача: 33. Search in Rotated Sorted Array Сложность: medium Дан массив nums, отсортированный по возрастанию и повернутый на некотором неизвестном индексе. Необходимо найти индекс элемента target. Если он не найден — вернуть -1. Решение должно работать за O(log n). Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            if (nums[m] == target) {
                return m;
            }
            if (nums[left] <= nums[m]) { // левая часть отсортирована
                if (nums[left] <= target && target < nums[m]) {
                    right = m - 1;
                } else {
                    left = m + 1;
                }
            } else { // правая часть отсортирована
                if (nums[m] < target && target <= nums[right]) {
                    left = m + 1;
                } else {
                    right = m - 1;
                }
            }
        }
        return -1;
    }
};

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

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

Задача: 1003. Check If Word Is Valid After Substitutions Сложность: medium Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false. Пример:

Input: s = "aabcbc"
Output: true

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

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 3 != 0) {
            return false;
        }

        stack<char> stk;
        for (char ch : s) {
            if (ch == 'c') {
                if (stk.size() < 2 || stk.top() != 'b') {
                    return false;
                }
                stk.pop();
                if (stk.top() != 'a') {
                    return false;
                }
                stk.pop();
            } else {
                stk.push(ch);
            }
        }

        return stk.empty();
    }
};

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

ДПДГ- эффективный метод работы с травмой клиента Приглашаем на бесплатный мастер-класс, на котором вы узнаете, как психологу эффективно работать с травмой клиента с помощью метода ДПДГ(EMDR) 2.0 Что Вас ждет: 👌 Обзор техники, с помощью которой вы увидите значительные улучшения после одной сессии при широком спектре проблем; 👌 Разбор кейсов; 👌Пошаговый план для работы с травмой и ее последствиями; 👌Демонстрация ресурсной техники ДПДГ(EMDR). Совместная практика с психологом. ✨Регистрируйтесь и получите тест на уровень стресса для оценки риска психосоматических заболеваний Узнать больше #реклама 16+ dmseregin.ru О рекламодателе

Задача: 237. Delete Node in a Linked List Сложность: medium Дан односвязный список с головой head, и требуется удалить узел node в этом списке. Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head. Все значения в односвязном списке уникальны, и гарантируется, что данный узел node не является последним узлом в списке. Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду: - Значение данного узла не должно существовать в односвязном списке. - Количество узлов в односвязном списке должно уменьшиться на один. - Все значения перед узлом должны оставаться в том же порядке. - Все значения после узла должны оставаться в том же порядке. Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

👨‍💻 Алгоритм: 1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле. 2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка. 3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка. 😎 Решение:

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

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

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

Задача: 1035. Uncrossed Lines Сложность: medium Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом. Пример:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2

👨‍💻 Алгоритм: 1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS): Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2. 2⃣Построение таблицы динамического программирования: Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1]. Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым. 3⃣Заполнение таблицы динамического программирования: Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1]. Результат будет находиться в ячейке dp[nums1.length][nums2.length]. 😎 Решение:

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
};

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

Задача: 1394. Find Lucky Integer in an Array Сложность: easy Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению. Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1. Пример:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> counts;
        for (int num : arr) {
            counts[num]++;
        }
        
        int largestLuckyNumber = -1;
        for (const auto& entry : counts) {
            if (entry.first == entry.second) {
                largestLuckyNumber = max(largestLuckyNumber, entry.first);
            }
        }
        
        return largestLuckyNumber;
    }
};

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