C/C++ | LeetCode

⚡️ Вся база знаний по IT в одном месте! 🧑‍💻 IT База — краткие разборы самого важного из мира IT. Сотни мастхев-ресурсов, каждый день новые материалы по работе и подготовке к собеседованиям. Подойдёт как новичкам, так и состоявшимся айтишникам; 🖥 Frontend База — всё для фронтенд разработчиков. Готовые решения для проектов, полезные курсы по JS/HTML/CSS, готовые роадмапы для комфортного освоения в профессии и дальнейшего развития; 👣 Backend База — самое важное для бэкендеров. Всё о работе с PHP, MySQL, MongoDB, Golang и Rust в одном месте, плюс полные курсы и лайфхаки для работы на каждый день; 🖥 База Знаний — склад полезных курсов и материалов, где легко найти что-то нужное по хэштегам. Если вам что-то интересно про IT, то оно уже лежит на Базе, проверяйте. ⏲ Успей подписаться, чтобы не потерять!

#medium Задача: 286. Walls and Gates Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями: -1: Стена или препятствие. 0: Ворота. INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647. Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF. Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty()) return;

        int m = rooms.size();
        int n = rooms[0].size();
        queue<pair<int, int>> q;
        const int INF = 2147483647;
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto& [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
};

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

#medium Задача: 285. Inorder Successor in BST Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null. Преемник узла p — это узел с наименьшим ключом, который больше p.val. Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

👨‍💻 Алгоритм: 1⃣Определение переменных класса: Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть. 2⃣Обработка двух случаев: В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента. Правый дочерний элемент существует: - присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве. Правый дочерний элемент не существует: - определите функцию inorderCase2 и передайте ей узел и узел p. - выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла. - когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции. - наконец, верните inorderSuccessorNode как результат. 3⃣Итерация и обновление: В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент. 😎 Решение:

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    TreeNode* previous;
    TreeNode* inorderSuccessorNode;

public:
    Solution() : previous(nullptr), inorderSuccessorNode(nullptr) {}

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (p->right != nullptr) {
            TreeNode* leftmost = p->right;
            while (leftmost->left != nullptr) {
                leftmost = leftmost->left;
            }
            inorderSuccessorNode = leftmost;
        } else {
            inorderCase2(root, p);
        }
        return inorderSuccessorNode;
    }

private:
    void inorderCase2(TreeNode* node, TreeNode* p) {
        if (node == nullptr) {
            return;
        }

        inorderCase2(node->left, p);

        if (previous == p && inorderSuccessorNode == nullptr) {
            inorderSuccessorNode = node;
            return;
        }

        previous = node;

        inorderCase2(node->right, p);
    }
};

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

#medium Задача: 284. Peeking Iterator Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента). Реализуйте класс PeekingIterator: PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел. int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент. boolean hasNext(): Возвращает true, если в массиве еще есть элементы. int peek(): Возвращает следующий элемент в массиве без перемещения указателя. Пример:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

👨‍💻 Алгоритм: 1⃣Инициализация итератора: В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null. 2⃣Операция peek: Метод peek возвращает значение next, не перемещая указатель итератора. 3⃣Операции next и hasNext: Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException. Метод hasNext возвращает true, если next не равно null, и false в противном случае. 😎 Решение:

#include <iterator>
#include <stdexcept>

class PeekingIterator : public std::iterator<std::input_iterator_tag, int> {
private:
    std::vector<int>::iterator iter;
    std::vector<int>::iterator end;
    int nextElem;
    bool hasNextElem;

public:
    PeekingIterator(std::vector<int>::iterator begin, std::vector<int>::iterator end) : iter(begin), end(end) {
        if (iter != end) {
            nextElem = *iter;
            hasNextElem = true;
        } else {
            hasNextElem = false;
        }
    }

    int peek() {
        if (!hasNextElem) {
            throw std::out_of_range("No more elements");
        }
        return nextElem;
    }

    int next() {
        if (!hasNextElem) {
            throw std::out_of_range("No more elements");
        }
        int currentElem = nextElem;
        ++iter;
        if (iter != end) {
            nextElem = *iter;
        } else {
            hasNextElem = false;
        }
        return currentElem;
    }

    bool hasNext() const {
        return hasNextElem;
    }
};

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#easy Задача: 283. Move Zeroes Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов. Обратите внимание, что вы должны сделать это на месте, не создавая копию массива. Пример:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

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

void moveZeroes(vector<int>& nums) {
    for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[lastNonZeroFoundAt++], nums[cur]);
        }
    }
}

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

#hard Задача: 282. Expression Add Operators Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target. Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей. Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

👨‍💻 Алгоритм: 1⃣Инициализация и рекурсивный вызов: Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения. Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений. 2⃣Рекурсивная генерация выражений: В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения. Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение. 3⃣Проверка и запись валидных выражений: Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов. Если выражение валидное, записывайте его в список результатов. 😎 Решение:

class Solution {
private:
    vector<string> answer;
    string digits;
    long long target;

    void recurse(int index, long long previousOperand, long long currentOperand, long long value, vector<string>& ops) {
        if (index == digits.size()) {
            if (value == target && currentOperand == 0) {
                string expression = accumulate(ops.begin(), ops.end(), string(""));
                answer.push_back(expression);
            }
            return;
        }

        currentOperand = currentOperand * 10 + (digits[index] - '0');
        string currentValRep = to_string(currentOperand);

        if (currentOperand > 0) {
            recurse(index + 1, previousOperand, currentOperand, value, ops);
        }

        ops.push_back("+");
        ops.push_back(currentValRep);
        recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
        ops.pop_back();
        ops.pop_back();

        if (!ops.empty()) {
            ops.push_back("-");
            ops.push_back(currentValRep);
            recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
            ops.pop_back();
            ops.pop_back();

            ops.push_back("*");
            ops.push_back(currentValRep);
            recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), ops);
            ops.pop_back();
            ops.pop_back();
        }
    }

public:
    vector<string> addOperators(string num, int target) {
        if (num.empty()) {
            return {};
        }

        this->target = target;
        this->digits = num;
        this->answer.clear();
        vector<string> ops;
        recurse(0, 0, 0, 0, ops);
        return answer;
    }
};

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

#medium Задача: 281. Zigzag Iterator Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно. Реализуйте класс ZigzagIterator: ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2. boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае. int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу. Пример:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

👨‍💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors. Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст. 2⃣Метод next: Удалите первую пару индексов из очереди. Извлеките элемент из соответствующего списка по указанным индексам. Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди. Верните извлеченный элемент. 3⃣Метод hasNext: Проверьте, пуста ли очередь. Верните true, если в очереди есть элементы, и false в противном случае. 😎 Решение:

#include <vector>
#include <queue>
#include <utility>

class ZigzagIterator {
private:
    std::vector<std::vector<int>> vectors;
    std::queue<std::pair<int, int>> queue;

public:
    ZigzagIterator(std::vector<int>& v1, std::vector<int>& v2) {
        vectors.push_back(v1);
        vectors.push_back(v2);
        for (int i = 0; i < vectors.size(); ++i) {
            if (!vectors[i].empty()) {
                queue.push({i, 0});
            }
        }
    }

    int next() {
        auto [vecIndex, elemIndex] = queue.front();
        queue.pop();
        int nextElemIndex = elemIndex + 1;
        if (nextElemIndex < vectors[vecIndex].size()) {
            queue.push({vecIndex, nextElemIndex});
        }
        return vectors[vecIndex][elemIndex];
    }

    bool hasNext() {
        return !queue.empty();
    }
};

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

#easy Задача: 293. Flip Game Вы играете в игру Flip со своим другом. Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем. Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список []. Пример:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

👨‍💻 Алгоритм: 1️⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода. 2️⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса: Если символы на позициях index и index + 1 равны '+': Создайте новую строку nextState, заменив две последовательные '+' на '--'. Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца. Сохраните созданное nextState в массив nextPossibleStates. 3️⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния. 😎 Решение:

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> generatePossibleNextMoves(string currentState) {
        vector<string> nextPossibleStates;

        for (int index = 0; index < currentState.length() - 1; ++index) {
            if (currentState[index] == '+' && currentState[index + 1] == '+') {
                string nextState = currentState.substr(0, index) + "--" + currentState.substr(index + 2);
                nextPossibleStates.push_back(nextState);
            }
        }

        return nextPossibleStates;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 291. Word Pattern II Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону. Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки. Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

👨‍💻 Алгоритм: 1️⃣Инициализация структур данных и определение рекурсивной функции: Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s. Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ. Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону. 2️⃣Рекурсивная проверка соответствия: Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false. Получите символ из шаблона по индексу pIndex. Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне. 3️⃣Отображение новых подстрок: Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки. Для каждой новой подстроки проверьте, существует ли она уже в ` 😎 Решение:

#include <unordered_map>
#include <unordered_set>
#include <string>

class Solution {
public:
    bool wordPatternMatch(std::string pattern, std::string s) {
        std::unordered_map<char, std::string> symbolMap;
        std::unordered_set<std::string> wordSet;
        return isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

private:
    bool isMatch(const std::string& s, int sIndex, const std::string& pattern, int pIndex,
                 std::unordered_map<char, std::string>& symbolMap, std::unordered_set<std::string>& wordSet) {
        if (pIndex == pattern.size()) {
            return sIndex == s.size();
        }
        char symbol = pattern[pIndex];
        if (symbolMap.find(symbol) != symbolMap.end()) {
            const std::string& word = symbolMap[symbol];
            if (!s.compare(sIndex, word.size(), word) == 0) {
                return false;
            }
            return isMatch(s, sIndex + word.size(), pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.size(); k++) {
            std::string newWord = s.substr(sIndex, k - sIndex);
            if (wordSet.find(newWord) != wordSet.end()) {
                continue;
            }
            symbolMap[symbol] = newWord;
            wordSet.insert(newWord);
            if (isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.erase(symbol);
            wordSet.erase(newWord);
        }
        return false;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 290. Word Pattern Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону. Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s. Пример:

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

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

#include <unordered_map>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

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

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

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

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

        return true;
    }
};

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

#easy Задача: 292. Nim Game Вы играете в следующую игру Nim со своим другом: Изначально на столе лежит куча камней. Вы и ваш друг поочередно делаете ходы, и вы ходите первым. Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи. Тот, кто убирает последний камень, становится победителем. Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false. Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

👨‍💻 Алгоритм: 1⃣Определите базовый случай: Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true. 2⃣Анализ оставшихся камней: Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false. 3⃣Выигрышная стратегия: Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true. 😎 Решение:

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

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

#medium Задача: 294. Flip Game II Вы играете в игру Flip со своим другом. Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем. Верните true, если начальный игрок может гарантировать победу, и false в противном случае. Пример:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

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

class Solution {
public:
    bool canWin(string currentState) {
        vector<char> stateArray(currentState.begin(), currentState.end());
        
        for (int i = 0; i < stateArray.size() - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState(stateArray.begin(), stateArray.end());
                
                if (!canWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
};

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

Обучение на Frontend-разработчика. С нуля за 9 месяцев. На курсе вы получите все навыки, необходимые для старта в профессии Frontend-разработчика. Персональный наставник middle/senior уровня. 14 проектов, лайвкодинг, хакатоны, репетиции техсобеседования. Освоите JavaScript, React, TypeScript Официальный диплом и сертификат школы. Поддержка наставника по JS в течение 3-х месяцев после диплома. Гарантия трудоустройства. Если вы не устроитесь, вернём деньги. Это закреплено в договоре п. 6.14 Узнать больше #реклама 16+ result.school О рекламодателе

#hard Задача: 295. Find Median from Data Stream Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений. Например, для arr = [2, 3, 4] медиана равна 3. Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5. Реализуйте класс MedianFinder: MedianFinder() инициализирует объект MedianFinder. void addNum(int num) добавляет целое число num из потока данных в структуру данных. double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься. Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

#include <vector>
#include <algorithm>

class MedianFinder {
private:
    std::vector<int> numbers;

public:
    MedianFinder() {}

    void addNum(int num) {
        numbers.push_back(num);
    }

    double findMedian() {
        std::sort(numbers.begin(), numbers.end());
        int n = numbers.size();
        if (n % 2 == 0) {
            return (numbers[n / 2 - 1] + numbers[n / 2]) / 2.0;
        } else {
            return numbers[n / 2];
        }
    }
};

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

#hard Задача: 296. Best Meeting Point Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия. Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи. Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|. Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        int minDistance = INT_MAX;
        for (int row = 0; row < grid.size(); ++row) {
            for (int col = 0; col < grid[0].size(); ++col) {
                int distance = search(grid, row, col);
                minDistance = min(distance, minDistance);
            }
        }
        return minDistance;
    }

private:
    int search(vector<vector<int>>& grid, int row, int col) {
        queue<tuple<int, int, int>> q;
        q.push({row, col, 0});
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int totalDistance = 0;

        while (!q.empty()) {
            auto [r, c, d] = q.front();
            q.pop();

            if (r < 0 || c < 0 || r >= m || c >= n || visited[r][c]) {
                continue;
            }

            if (grid[r][c] == 1) {
                totalDistance += d;
            }

            visited[r][c] = true;

            q.push({r + 1, c, d + 1});
            q.push({r - 1, c, d + 1});
            q.push({r, c + 1, d + 1});
            q.push({r, c - 1, d + 1});
        }

        return totalDistance;
    }
};

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

#hard Задача: 297. Serialize and Deserialize Binary Tree Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде. Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева. Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы. Пример:

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

👨‍💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:

#include <string>
#include <sstream>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
public:
    void rserialize(TreeNode* root, std::string& str) {
        if (root == nullptr) {
            str += "null,";
        } else {
            str += std::to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    std::string serialize(TreeNode* root) {
        std::string str;
        rserialize(root, str);
        return str;
    }

    TreeNode* rdeserialize(std::vector<std::string>& data) {
        if (data[0] == "null") {
            data.erase(data.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(std::stoi(data[0]));
        data.erase(data.begin());
        root->left = rdeserialize(data);
        root->right = rdeserialize(data);
        return root;
    }

    TreeNode* deserialize(std::string data) {
        std::vector<std::string> dataArray;
        std::string item;
        std::istringstream ss(data);
        while (std::getline(ss, item, ',')) {
            dataArray.push_back(item);
        }
        return rdeserialize(dataArray);
    }
};

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

#medium Задача: 433. Minimum Genetic Mutation Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'. Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке. Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией. Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой. Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1. Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк. Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> queue;
        unordered_set<string> seen;
        queue.push(start);
        seen.insert(start);
        
        int steps = 0;
        while (!queue.empty()) {
            int nodesInQueue = queue.size();
            
            for (int j = 0; j < nodesInQueue; j++) {
                string node = queue.front();
                queue.pop();

                if (node == end) {
                    return steps;
                }
                
                for (char c: "ACGT") {
                    for (int i = 0; i < node.size(); i++) {
                        string neighbor = node;
                        neighbor[i] = c;
                        if (!seen.count(neighbor) && find(bank.begin(), bank.end(), neighbor) != bank.end()) {
                            queue.push(neighbor);
                            seen.insert(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
};

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

#medium Задача: 298. Binary Tree Longest Consecutive Sequence Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений. Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути. Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути. Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

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

class Solution {
private:
    int maxLength = 0;

    void dfs(TreeNode* node, TreeNode* parent, int length) {
        if (!node) return;
        if (parent && node->val == parent->val + 1) {
            length++;
        } else {
            length = 1;
        }
        maxLength = std::max(maxLength, length);
        dfs(node->left, node, length);
        dfs(node->right, node, length);
    }

public:
    int longestConsecutive(TreeNode* root) {
        dfs(root, nullptr, 0);
        return maxLength;
    }
};

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

⚡️ IT-обучение теперь в Telegram! В cвязи с недавнем замедлением Ютуба — лучшие обучающие каналы переехали в Telegram Вот каналы для айтишников: 👩‍💻 С/С++: @Cpp 👩‍💻 C#: @Csharp 📱 GitHub: @GitHub ⚙️ Backend: @Backend 👩‍💻 Разработка игр: @GameDev 🤓 Общее айти: @portalToIT 👩‍💻 Python: @Python 👩‍💻 Frontend: @Frontend 👩‍💻 Java: @Java 🖥 Базы Данных & SQL: @SQL 👩‍💻 Golang: @Golang 👩‍💻 PHP: @PHP 👩‍💻 Моб. разработка: @MobDev 👩‍💻 DevOps: @DevOps 🖥 Data Science: @DataScience 🤔 Хакинг & ИБ: @InfoSec 🐞 Тестирование: @QA 📱 Маркетинг: @Marketing 🖥 Дизайн: @Design ➡️ Сохраняйте себе, чтобы не потерять