C/C++ | LeetCode

#medium Задача: 313. Super Ugly Number Супер некрасивое число — это положительное целое число, простые множители которого находятся в массиве primes. Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число. Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число. Пример:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

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

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> ugly_numbers(n, 1);
        vector<int> indices(primes.size(), 0);
        vector<int> next_ugly = primes;
        
        for (int i = 1; i < n; ++i) {
            int next_val = *min_element(next_ugly.begin(), next_ugly.end());
            ugly_numbers[i] = next_val;
            
            for (int j = 0; j < primes.size(); ++j) {
                if (next_val == next_ugly[j]) {
                    indices[j]++;
                    next_ugly[j] = ugly_numbers[indices[j]] * primes[j];
                }
            }
        }
        
        return ugly_numbers[n - 1];
    }
};

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

#easy Задача: 520. Detect Capital Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий: Все буквы в этом слове заглавные, как "USA". Все буквы в этом слове строчные, как "leetcode". Только первая буква в этом слове заглавная, как "Google". Дана строка word. Верните true, если использование заглавных букв в ней правильное. Пример:

Input: word = "USA"
Output: true

👨‍💻 Алгоритм: 1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы". 2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные. 3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*. 😎 Решение:

#include <regex>
#include <string>

class Solution {
public:
    bool detectCapitalUse(std::string word) {
        std::regex pattern("[A-Z]*|.[a-z]*");
        return std::regex_match(word, pattern);
    }
};

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

#medium Задача: 518. Coin Change II Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег. Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0. Предположим, что у вас есть бесконечное количество каждой монеты. Ответ гарантированно вписывается в знаковое 32-битное целое число. Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

👨‍💻 Алгоритм: 1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты. 2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его. 3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу. 😎 Решение:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> memo(coins.size(), vector<int>(amount + 1, -1));
        return numberOfWays(0, amount, coins, memo);
    }
    
private:
    int numberOfWays(int i, int amount, vector<int>& coins, vector<vector<int>>& memo) {
        if (amount == 0) return 1;
        if (i == coins.size()) return 0;
        if (memo[i][amount] != -1) return memo[i][amount];
        
        if (coins[i] > amount) {
            memo[i][amount] = numberOfWays(i + 1, amount, coins, memo);
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i], coins, memo) + numberOfWays(i + 1, amount, coins, memo);
        }
        return memo[i][amount];
    }
};

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

#hard Задача: 517. Super Washing Machines У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста. За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин. Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1. Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

👨‍💻 Алгоритм: 1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение). 2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)). 3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res. 😎 Решение:

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int n = machines.size(), dressTotal = accumulate(machines.begin(), machines.end(), 0);
        if (dressTotal % n != 0) return -1;

        int dressPerMachine = dressTotal / n;
        for (int i = 0; i < n; i++) machines[i] -= dressPerMachine;

        int currSum = 0, maxSum = 0, res = 0;
        for (int m : machines) {
            currSum += m;
            maxSum = max(maxSum, abs(currSum));
            res = max(res, max(maxSum, m));
        }
        return res;
    }
};

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

#medium Задача: 516. Longest Palindromic Subsequence Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s. Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

👨‍💻 Алгоритм: 1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s. 2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1. 3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j]. 😎 Решение:

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        unordered_map<int, unordered_map<int, int>> memo;
        
        function<int(int, int)> lps = [&](int l, int r) {
            if (memo[l][r] != 0) return memo[l][r];
            if (l > r) return 0;
            if (l == r) return 1;
            
            if (s[l] == s[r]) {
                memo[l][r] = lps(l + 1, r - 1) + 2;
            } else {
                memo[l][r] = max(lps(l, r - 1), lps(l + 1, r));
            }
            return memo[l][r];
        };
        
        return lps(0, n - 1);
    }
};

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

#medium Задача: 515. Find Largest Value in Each Tree Row Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0). Пример:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

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

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root) return {};
        
        vector<int> ans;
        queue<TreeNode*> queue;
        queue.push(root);
        
        while (!queue.empty()) {
            int currentLength = queue.size();
            int currMax = INT_MIN;
            
            for (int i = 0; i < currentLength; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                currMax = max(currMax, node->val);
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
            }
            
            ans.push_back(currMax);
        }
        
        return ans;
    }
};

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

#easy Задача: 1287. Element Appearing More Than 25% In Sorted Array Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число. Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num. 2⃣Установите target = arr.length / 4. 3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение. 😎 Решение:

#include <vector>
#include <unordered_map>

class Solution {
public:
    int findSpecialInteger(std::vector<int>& arr) {
        std::unordered_map<int, int> counts;
        int target = arr.size() / 4;
        for (int num : arr) {
            counts[num]++;
            if (counts[num] > target) {
                return num;
            }
        }
        return -1;
    }
};

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

#hard Задача: 514. Freedom Trail В видеоигре Fallout 4 в квесте "Дорога к свободе" игрокам нужно добраться до металлического диска, называемого "Кольцо Свободы", и использовать его для набора определённого ключевого слова, чтобы открыть дверь. Дана строка ring, представляющая код, выгравированный на внешнем кольце, и другая строка key, представляющая ключевое слово, требуемое набрать. Верните минимальное количество шагов, чтобы набрать все символы ключевого слова. Изначально первый символ кольца выровнен в направлении "12 часов". Вы должны набирать все символы из строки key один за другим, поворачивая кольцо по или против часовой стрелки, чтобы каждый символ строки key выровнять в направлении "12 часов", а затем нажимая на центральную кнопку. На этапе вращения кольца для набора символа key[i]: Вы можете вращать кольцо по часовой или против часовой стрелки на одно место, что считается одним шагом. Конечная цель вращения — выровнять один из символов кольца в направлении "12 часов", и этот символ должен быть равен key[i]. Если символ key[i] уже выровнен в направлении "12 часов", нажмите центральную кнопку, чтобы набрать его, что также считается одним шагом. После нажатия вы можете начинать набирать следующий символ из key (следующий этап). Иначе, вы завершили весь набор. Пример:

Input: ring = "godding", key = "godding"
Output: 13

👨‍💻 Алгоритм: 1⃣Определите функцию countSteps для вычисления минимального пути между двумя индексами кольца ring. Создайте переменные ringLen и keyLen для хранения длин кольца и ключа соответственно. Создайте словарь bestSteps для хранения минимального количества шагов для нахождения символа на keyIndex, когда ringIndex кольца выровнен в позиции "12 часов". 2⃣Определите функцию tryLock, возвращающую минимальное количество шагов для набора ключевого слова. Параметры: ringIndex, keyIndex, minSteps (минимальные шаги для набора ключевого слова на данный момент). Проверьте, равен ли keyIndex значению keyLen; если да, верните 0. Проверьте, есть ли пара (ringIndex, keyIndex) в bestSteps. Если есть, верните bestSteps[ringIndex][keyIndex]. Пройдите по каждому charIndex в ring. Если ring[charIndex] равен key[keyIndex], вычислите totalSteps, добавляя результат countSteps, единицу (нажатие центральной кнопки) и результат tryLock для следующего символа в key. Сохраните минимальное значение между totalSteps и текущим minSteps в minSteps. Сохраните minSteps для (ringIndex, keyIndex) в bestSteps. 3⃣Вызовите tryLock(0, 0, INT_MAX), начиная с нулевого индекса ring в позиции "12 часов" и первого символа в key. Наибольшее целое число передается как последний параметр, т.к. путь между нулевым индексом ring и первым символом key еще не определен. 😎 Решение:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int ringLen = ring.size();
        int keyLen = key.size();
        unordered_map<string, int> bestSteps;

        auto countSteps = [&](int curr, int next) {
            int stepsBetween = abs(curr - next);
            int stepsAround = ringLen - stepsBetween;
            return min(stepsBetween, stepsAround);
        };
        function<int(int, int)> tryLock = [&](int ringIndex, int keyIndex) {
            string keyPair = to_string(ringIndex) + "-" + to_string(keyIndex);
            if (bestSteps.find(keyPair) != bestSteps.end()) {
                return bestSteps[keyPair];
            }
            if (keyIndex == keyLen) {
                bestSteps[keyPair] = 0;
                return 0;
            }
            int minSteps = INT_MAX;
            for (int charIndex = 0; charIndex < ringLen; charIndex++) {
                if (ring[charIndex] == key[keyIndex]) {
                    minSteps = min(minSteps, 
                                   countSteps(ringIndex, charIndex)
                                   + 1
                                   + tryLock(charIndex, keyIndex + 1));
                }
            }
            bestSteps[keyPair] = minSteps;
            return minSteps;
        };
        return tryLock(0, 0);
    }
};

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

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

Что может быть лучше пиццы? ❤️Только 2 пиццы в подарок к заказам Додо и другие выгодные предложение по подписке Газпром Бонус за 0₽! Оформляйте подписку по ссылке и получайте максимум выгоды! Попробовать #реклама dodo.gazprombonus.ru О рекламодателе

#medium Задача: 513. Find Bottom Left Tree Value Дан корень двоичного дерева, верните самое левое значение в последней строке дерева. Пример:

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

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

class Solution {
    int maxDepth = -1;
    int bottomLeftValue = 0;
    
public:
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 0);
        return bottomLeftValue;
    }
    
    void dfs(TreeNode* current, int depth) {
        if (!current) return;
        
        if (depth > maxDepth) {
            maxDepth = depth;
            bottomLeftValue = current->val;
        }
        
        dfs(current->left, depth + 1);
        dfs(current->right, depth + 1);
    }
};

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

#Hard Задача: 600. Non-negative Integers without Consecutive Ones Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц. Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

👨‍💻 Алгоритм: 1⃣Простой метод заключается в переборе всех чисел от 1 до num. Для каждого текущего выбранного числа проверяем все соседние позиции, чтобы выяснить, содержит ли число две последовательные единицы. Если не содержит, увеличиваем количество чисел без последовательных единиц. 2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x. 3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц. 😎 Решение:

class Solution {
public:
    int findIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (check(i)) {
                count++;
            }
        }
        return count;
    }

    bool check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
};

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

Просто используйте подписку на Кинопоиск и Музыку за 1₽ Ответьте на 1 вопрос и получите в подарок доступ к Кинопоиску, Музыке и Книгам на 60 дней за 1 рубль. ✨ Сервисы будут доступны не только для Вас, но и для трёх ваших близких Попробовать #реклама 18+ kinopoisk.ru О рекламодателе Реклама на Яндексе

#Easy Задача: 599. Minimum Index Sum of Two Lists Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов. Общая строка - это строка, которая появляется и в list1, и в list2. Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк. Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке. Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

👨‍💻 Алгоритм: 1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме. 2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j. 3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой. 😎 Решение:

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

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<int, vector<string>> map;
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if (list1[i] == list2[j]) {
                    map[i + j].push_back(list1[i]);
                }
            }
        }
        int minIndexSum = INT_MAX;
        for (auto& [key, val] : map) {
            minIndexSum = min(minIndexSum, key);
        }
        return map[minIndexSum];
    }
};

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

#easy Задача: 594. Longest Harmonious Subsequence Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1. Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей. Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов. Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> count;
        int res = 0;
        
        for (int num : nums) {
            count[num]++;
            if (count.find(num + 1) != count.end()) {
                res = max(res, count[num] + count[num + 1]);
            }
            if (count.find(num - 1) != count.end()) {
                res = max(res, count[num] + count[num - 1]);
            }
        }
        
        return res;
    }
};

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

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

#Easy Задача: 598. Range Addition II Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi. Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций. Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

👨‍💻 Алгоритм: 1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j). 2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])). 3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y. 😎 Решение:

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        int minA = m;
        int minB = n;
        for (auto& op : ops) {
            minA = min(minA, op[0]);
            minB = min(minB, op[1]);
        }
        return minA * minB;
    }
};

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

Полный экскурс в Реверсивный инжиниринг: запись до 26 декабря! Дарим 3 месяца подписки на Codeby Games при покупке любого курса до 31 декабря!  В курсе подробно рассматривается синтаксис Ассемблера, анализ приложений различного уровня сложности, от простейших crackme до полноценных программ на современных архитектурах. Необходимые знания: язык Ассемблера, С/С++, python, навыки работы с IDA и другими инструментами для реверса Вы получите сертификат/удостоверение о повышении квалификации Пишите нам @Codeby_Academy или оставьте заявку на сайте

#medium Задача: 593. Valid Square Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат. Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке. Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов). Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

#include <vector>
#include <cmath>

using namespace std;

class Solution {
public:
    int dist(vector<int>& p1, vector<int>& p2) {
        return pow(p2[1] - p1[1], 2) + pow(p2[0] - p1[0], 2);
    }

    bool check(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        return dist(p1, p2) > 0 &&
               dist(p1, p2) == dist(p2, p3) &&
               dist(p2, p3) == dist(p3, p4) &&
               dist(p3, p4) == dist(p4, p1) &&
               dist(p1, p3) == dist(p2, p4);
    }

    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        return check(p1, p2, p3, p4) ||
               check(p1, p3, p2, p4) ||
               check(p1, p2, p4, p3);
    }
};

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

Квартиры в Тюмени в семейную ипотеку от 13 233 ₽/мес «Окинава» — современный ЖК в районе озера Алебашево. 10 минут до центра Тюмени. Не упустите свою выгоду: ✅ Квартиры от 13 233 ₽/мес ✅ Платеж на весь срок ✅ Паркинг в подарок Это не просто жилой комплекс, это остров 4 стихий. Каждая из стихий — отдельный дом и очередь строительства. В «Окинаве» есть все для комфортной жизни: — Видовые квартиры с террасой — Закрытые дворы-стилобаты — Функциональные планировки — 2-уровневый пешеходный бульвар Зафиксируйте условия покупки и получите подборку планировок! 🏠 Получить предложение Проектная декларация на сайте https://наш.дом.рф/. Застройщик: СЗ ИСБ-НЕДВИЖИМОСТЬ. Финансовые услуги оказывает: ПАО "Сбербанк". #реклама mrqz.me О рекламодателе