C/C++ | LeetCode

#medium Задача: 299. Bulls and Cows Вы играете в игру "Быки и коровы" со своим другом. Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией: Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции. Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками. Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга. Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры. Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

👨‍💻 Алгоритм: 1⃣Инициализация счетчиков: Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот. 2⃣Обход строки guess: Для каждого символа ch в строке guess: Если ch присутствует в строке secret: Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]): Увеличьте количество быков: bulls += 1. Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0). Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]): Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0). Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1. 3⃣Возврат результата: Верните количество быков и коров в формате "xAyB". 😎 Решение:

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

class Solution {
public:
    string getHint(string secret, string guess) {
        unordered_map<char, int> h;
        for (char ch : secret) {
            h[ch]++;
        }

        int bulls = 0;
        int cows = 0;
        int n = guess.size();
        string secretArray = secret;
        string guessArray = guess;

        for (int idx = 0; idx < n; ++idx) {
            char ch = guessArray[idx];
            if (h.find(ch) != h.end()) {
                if (ch == secretArray[idx]) {
                    bulls++;
                    if (h[ch] <= 0) {
                        cows--;
                    }
                } else {
                    if (h[ch] > 0) {
                        cows++;
                    }
                }
                h[ch]--;
            }
        }

        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

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

Обучаем Java-разработчиков оплата после выхода на работу В Kata Academy можно выучиться на Java-разработчика бесплатно, а заплатить уже после трудоустройства по специальности из фактической зарплаты. Если задуматься, то все в выигрыше: — ты получаешь работу в Москве или Санкт-Петербурге с хорошей зарплатой, мы получаем процент за инвестиции в тебя; — в наших интересах научить тебя так, чтобы твоя зарплата была как можно выше; — мы прокачиваем твои навыки еще 2 года после курса: проводим выездные мероприятия и мастер-классы — и доходы наших выпускников растут; — мы не зависим от банков и их рассрочек — кризис не повлиял на доступность курсов. Чтобы попасть на курс, нужно выполнить небольшое тестовое задание. Переходи по ссылке и оставляй заявку! Узнать больше #реклама 16+ kata.academy О рекламодателе

#medium Задача: 300. Longest Increasing Subsequence Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности. Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение:

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;

        std::vector<int> dp(nums.size(), 1);

        for (size_t i = 1; i < nums.size(); ++i) {
            for (size_t j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }
        }

        return *std::max_element(dp.begin(), dp.end());
    }
};

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

Senior-разработчик создал крутейший канал про SQL Благодаря простым картинкам даже новичок научится разрабатывать приложения с использованием баз данных. Присоединяйтесь: @SQL

#medium Задача: 395. Longest Substring with At Least K Repeating Characters Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k. Если такой подстроки не существует, верните 0. Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

👨‍💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:

class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.length() == 0 || k > s.length()) {
            return 0;
        }
        int countMap[26] = {0};
        int n = s.length();
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            memset(countMap, 0, sizeof(countMap));
            for (int end = start; end < n; end++) {
                countMap[s[end] - 'a']++;
                if (isValid(countMap, k)) {
                    result = max(result, end - start + 1);
                }
            }
        }
        return result;
    }

private:
    bool isValid(int countMap[26], int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int i = 0; i < 26; i++) {
            if (countMap[i] > 0) countLetters++;
            if (countMap[i] >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
};

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

🔥 Ресурсы для подготовки к работе в IT! 🔥 1️⃣ База собеседований IT – это уникальная коллекция собеседований от реальных топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 150+ собеседований, чтобы ты мог подготовиться к интервью с уверенностью и успехом. 2️⃣ База тестовых заданий – твоё секретное оружие для успешного прохождения этапов отбора! 📋 Здесь ты найдёшь 121+ тестовых заданий от тех же топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries. Решай реальные задачи и набирайся опыта для будущих собеседований! 🎯 Присоединяйся к базам и прокачай свои шансы на успешное трудоустройство!

#hard Задача: 301. Remove Invalid Parentheses Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой. Верните список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке. Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

👨‍💻 Алгоритм: 1⃣Инициализация: Инициализируйте массив, который будет хранить все допустимые выражения. Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо. Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно. 2⃣Обработка текущего символа: Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии. Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения. 3⃣Завершение рекурсии и проверка: Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны). Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор. Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений. 😎 Решение:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
private:
    unordered_set<string> validExpressions;
    int minimumRemoved;

    void reset() {
        validExpressions.clear();
        minimumRemoved = INT_MAX;
    }

    void recurse(const string &s, int index, int leftCount, int rightCount, string &expression, int removedCount) {
        if (index == s.length()) {
            if (leftCount == rightCount) {
                if (removedCount <= minimumRemoved) {
                    if (removedCount < minimumRemoved) {
                        validExpressions.clear();
                        minimumRemoved = removedCount;
                    }
                    validExpressions.insert(expression);
                }
            }
            return;
        }

        char currentCharacter = s[index];
        int length = expression.length();

        if (currentCharacter != '(' && currentCharacter != ')') {
            expression += currentCharacter;
            recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
            expression.erase(length);
        } else {
            recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
            expression += currentCharacter;

            if (currentCharacter == '(') {
                recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
            } else if (rightCount < leftCount) {
                recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
            }

            expression.erase(length);
        }
    }

public:
    vector<string> removeInvalidParentheses(string s) {
        reset();
        string expression;
        recurse(s, 0, 0, 0, expression, 0);
        return vector<string>(validExpressions.begin(), validExpressions.end());
    }
};

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

CodHub теперь в Telegram! Бесплатные обучающие материалы, которые лучше платных — книги, ресурсы, статьи и курсы топовых вузов страны тут: 👩‍💻 Материалы по Python 👩‍💻 Материалы по Frontend 👩‍💻 Материалы по Java 👩‍💻 Материалы по С# 👩‍💻 Материалы по C/C++ 👩‍💻 Материалы по Хакингу 🖥 Материалы по SQL 👩‍💻 Материалы по Kotlin/Swift 👩‍💻 Материалы по Linux 🐞 Материалы по QA 👩‍💻 Материалы по Go 👩‍💻 Материалы по PHP Подписываетесь: @CodHub_tg

#medium Задача: 280. Wiggle Sort Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3].... Вы можете считать, что входной массив всегда имеет допустимый ответ. Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

👨‍💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:

#include <vector>

class Solution {
public:
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void wiggleSort(std::vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; ++i) {
            if ((i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1])) {
                swap(nums, i, i + 1);
            }
        }
    }
};

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

#medium Задача: 394. Decode String Дана закодированная строка, вернуть её декодированную версию. Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом. Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4]. Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105. Пример:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

👨‍💻 Алгоритм: 1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек. 2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k. 3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его. 😎 Решение:

class Solution {
public:
    string decodeString(string s) {
        stack<char> stack;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ']') {
                string decodedString = "";
                while (stack.top() != '[') {
                    decodedString = stack.top() + decodedString;
                    stack.pop();
                }
                stack.pop();
                int base = 1;
                int k = 0;
                while (!stack.empty() && isdigit(stack.top())) {
                    k = k + (stack.top() - '0') * base;
                    stack.pop();
                    base *= 10;
                }
                while (k != 0) {
                    for (int j = decodedString.size() - 1; j >= 0; j--) {
                        stack.push(decodedString[j]);
                    }
                    k--;
                }
            } else {
                stack.push(s[i]);
            }
        }
        string result;
        while (!stack.empty()) {
            result = stack.top() + result;
            stack.pop();
        }
        return result;
    }
};

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

#medium Задача: 393. UTF-8 Validation Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов). Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила: Для 1-байтового символа первый бит — 0, за которым следует его Unicode код. Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10. Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1. Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных. Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

👨‍💻 Алгоритм: 1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep. 2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа. 3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий. Теперь давайте перейдем к реализации этого алгоритма. 😎 Решение:

class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int nBytes = 0;
        for (int num : data) {
            string binRep = bitset<8>(num).to_string();
            if (nBytes == 0) {
                for (char bit : binRep) {
                    if (bit == '0') break;
                    nBytes++;
                }
                if (nBytes == 0) continue;
                if (nBytes == 1 || nBytes > 4) return false;
            } else {
                if (!(binRep[0] == '1' && binRep[1] == '0')) return false;
            }
            nBytes--;
        }
        return nBytes == 0;
    }
};

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

#easy Задача: 392. Is Subsequence Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false. Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является). Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int leftBound = s.length(), rightBound = t.length();
        int pLeft = 0, pRight = 0;

        while (pLeft < leftBound && pRight < rightBound) {
            if (s[pLeft] == t[pRight]) {
                pLeft++;
            }
            pRight++;
        }
        return pLeft == leftBound;
    }
};

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

👩‍💻 Python: @python_ready 👩‍💻 Java: @java_ready 📖 Общее IT: @roadmap_ready 👩‍💻 Frontend: @code_ready 👩‍💻 Backend: @backend_ready 🖥 Базы Данных & SQL: @sql_ready 👩‍💻 C#: @csharp_ready 👩‍💻 C/C++: @cpp_ready 📋 IT Архив: @archive_ready 🖥 Design: @time_design

#easy Задача: 389. Find the Difference Даны две строки s и t. Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию. Верните букву, которая была добавлена в t. Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

👨‍💻 Алгоритм: 1⃣Отсортируйте строки s и t. 2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s. 3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время. 😎 Решение:

#include <algorithm>
#include <string>

class Solution {
public:
    char findTheDifference(std::string s, std::string t) {
        std::sort(s.begin(), s.end());
        std::sort(t.begin(), t.end());

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != t[i]) {
                return t[i];
            }
        }

        return t[s.size()];
    }
};

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

#hard Задача: 369. Plus One Linked List Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу. Цифры хранятся таким образом, что самая значимая цифра находится в начале списка. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode* notNine = sentinel;

        ListNode* current = head;
        while (current != nullptr) {
            if (current->val != 9) {
                notNine = current;
            }
            current = current->next;
        }

        notNine->val += 1;
        notNine = notNine->next;

        while (notNine != nullptr) {
            notNine->val = 0;
            notNine = notNine->next;
        }

        return sentinel->val == 0 ? sentinel->next : sentinel;
    }
};

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

#easy Задача: 387. First Unique Character in a String Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1. Пример:

Input: s = "leetcode"
Output: 0

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

#include <vector>
#include <cstdlib>
#include <ctime>

class Solution {
private:
    std::vector<int> original;
    std::vector<int> array;

    int randRange(int min, int max) {
        return rand() % (max - min) + min;
    }

    void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

public:
    Solution(std::vector<int>& nums) : original(nums), array(nums) {
        std::srand(std::time(0));
    }

    std::vector<int> reset() {
        array = original;
        return original;
    }

    std::vector<int> shuffle() {
        for (int i = 0; i < array.size(); i++) {
            int randIndex = randRange(i, array.size());
            swapAt(i, randIndex);
        }
        return array;
    }
};

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

#medium Задача: 368. Largest Divisible Subset Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию: answer[i] % answer[j] == 0, или answer[j] % answer[i] == 0 Если существует несколько решений, вернуть любое из них. Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

👨‍💻 Алгоритм: 1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4). 2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8). 3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}. 😎 Решение:

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> largestDivisibleSubset(std::vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return {};

        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> EDS(n);

        for (int i = 0; i < n; ++i) {
            std::vector<int> maxSubset;
            for (int k = 0; k < i; ++k) {
                if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS[k].size()) {
                    maxSubset = EDS[k];
                }
            }
            EDS[i] = maxSubset;
            EDS[i].push_back(nums[i]);
        }

        std::vector<int> ret;
        for (const auto& subset : EDS) {
            if (ret.size() < subset.size()) {
                ret = subset;
            }
        }
        return ret;
    }
};

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

Захват переменных без ошибок — это возможно! Как? Расскажем на бесплатном вебинаре Слёрма «Ля какие! Лямбды в С++». Поговорим про: 📍 Захваты переменных, параметры, возвращаемые значения, типы замыканий. 📍 Лямбды в C++20 и C++23. 📍 Применение в реальных задачах: передача функций в алгоритмы STL, написание компактных колбэков Спикер: Юрий Вашинко, Tech Lead/Lead Developer 📆 Когда: 15 октября в 14:00 мск 🔗 Занять место на вебинаре — через бота Приходите! #реклама О рекламодателе erid: LjN8KEorG

#medium Задача: 384. Shuffle an Array Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания. Реализуйте класс Solution: Solution(int[] nums): Инициализирует объект целочисленным массивом nums. int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его. int[] shuffle(): Возвращает случайное перемешивание массива. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

👨‍💻 Алгоритм: 1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива. 2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент. 3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие. 😎 Решение:

#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

class Solution {
private:
    std::vector<int> array;
    std::vector<int> original;

    int randRange(int min, int max) {
        return rand() % (max - min) + min;
    }

    void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

public:
    Solution(std::vector<int>& nums) : array(nums), original(nums) {
        std::srand(std::time(0));
    }

    std::vector<int> reset() {
        array = original;
        return original;
    }

    std::vector<int> shuffle() {
        for (int i = 0; i < array.size(); i++) {
            int randIndex = randRange(i, array.size());
            swapAt(i, randIndex);
        }
        return array;
    }
};

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

#easy Задача: 383. Ransom Note Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае. Каждая буква из magazine может быть использована в ransomNote только один раз. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

#include <string>

bool canConstruct(std::string ransomNote, std::string magazine) {
    for (char c : ransomNote) {
        size_t index = magazine.find(c);
        if (index == std::string::npos) {
            return false;
        }
        magazine.erase(index, 1);
    }
    return true;
}

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