Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

👨‍💻 Алгоритм:

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.

😎 Решение:

class Solution {
public:
    int storeFirstOptions(string& s, int startPos, vector<char>& firstOptions) {
        if (s[startPos] != '{') {
            firstOptions.push_back(s[startPos]);
        } else {
            startPos++;
            while (s[startPos] != '}') {
                if (s[startPos] >= 'a' && s[startPos] <= 'z') {
                    firstOptions.push_back(s[startPos]);
                }
                startPos++;
            }
            sort(firstOptions.begin(), firstOptions.end());
        }
        return startPos + 1;
    }

    vector<string> findAllWords(string& s, int startPos) {
        if (startPos == s.size()) {
            return {""};
        }

        vector<char> firstOptions;
        int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
        vector<string> wordsWithRemString = findAllWords(s, remStringStartPos);

        vector<string> expandedWords;
        for (char c : firstOptions) {
            for (string& word : wordsWithRemString) {
                expandedWords.push_back(c + word);
            }
        }
        return expandedWords;
    }

    vector<string> expand(string s) {
        return findAllWords(s, 0);
    }
};

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

Задача: 900. RLE Iterator
Сложность: medium

Для кодирования последовательности целых чисел мы можем использовать кодирование по длине строки (т. е. RLE). В кодированном по длине пробега массиве четной длины (с индексацией 0) для всех четных i значение encoding[i] говорит нам о том, сколько раз неотрицательное целое значение encoding[i + 1] повторяется в последовательности.

Например, последовательность arr = [8,8,8,5,5] может быть закодирована как encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] и encoding = [2,8,1,8,2,5] также являются допустимыми RLE для arr.
Задав кодированный по длине пробега массив, разработайте итератор для его итерации. Реализуйте класс RLEIterator: RLEIterator(int[] encoded) Инициализирует объект с кодированным массивом encoded. int next(int n) Исчерпывает следующие n элементов и возвращает последний исчерпанный таким образом элемент. Если не осталось элементов для исчерпания, возвращает -1.

Пример:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

👨‍💻 Алгоритм:

1⃣Инициализировать итератор с закодированным массивом и индексом, указывающим на текущую позицию.

2⃣При вызове метода next(n), уменьшить текущий счетчик на n или перейти к следующему числу, если текущий счетчик равен нулю.

3⃣Возвращать текущий элемент или -1, если все элементы исчерпаны.

😎 Решение:

class RLEIterator {
    vector<int> encoding;
    int index;

public:
    RLEIterator(vector<int>& encoding) : encoding(encoding), index(0) {}

    int next(int n) {
        while (index < encoding.size()) {
            if (n > encoding[index]) {
                n -= encoding[index];
                index += 2;
            } else {
                encoding[index] -= n;
                return encoding[index + 1];
            }
        }
        return -1;
    }
};

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

Задача: 1058. Minimize Rounding Error to Meet Target
Сложность: medium

Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби.

Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

👨‍💻 Алгоритм:

1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен.
Найди разницу между целевой суммой и текущей суммой.

2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы.
Если разница отрицательная или больше количества элементов в массиве, верни "-1".

3⃣Вычисли ошибки округления для всех элементов и отсортируй их по возрастанию.
Выбери необходимые округления вверх и вычисли общую ошибку округления.

😎 Решение:

string minimizeRoundingError(vector<string>& prices, int target) {
    vector<int> floors;
    vector<double> floatPrices;
    double totalFloor = 0;

    for (const string& price : prices) {
        double p = stod(price);
        floatPrices.push_back(p);
        int floorVal = floor(p);
        floors.push_back(floorVal);
        totalFloor += floorVal;
    }
    
    int difference = target - totalFloor;
    if (difference < 0 || difference > prices.size()) {
        return "-1";
    }
    
    vector<pair<double, double>> roundingErrors;
    for (int i = 0; i < prices.size(); ++i) {
        roundingErrors.push_back({ceil(floatPrices[i]) - floors[i], floatPrices[i] - floors[i]});
    }
    
    sort(roundingErrors.begin(), roundingErrors.end(), [](const pair<double, double>& a, const pair<double, double>& b) {
        return a.second < b.second;
    });
    
    double roundingErrorSum = 0;
    for (int i = 0; i < floors.size(); ++i) {
        roundingErrorSum += (floatPrices[i] - floors[i]);
    }
    
    for (int i = 0; i < difference; ++i) {
        roundingErrorSum += roundingErrors[i].second;
    }
    
    stringstream ss;
    ss << fixed << setprecision(3) << roundingErrorSum;
    return ss.str();
}

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

Задача: 1001. Grid Illumination
Сложность: hard

Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.

Пример:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]

👨‍💻 Алгоритм:

1⃣Инициализация данных:
Используйте множества для хранения включенных ламп, освещенных строк, столбцов, диагоналей и обратных диагоналей.
Инициализируйте множества и словари для отслеживания количества ламп, освещающих каждую строку, столбец, диагональ и обратную диагональ.

2⃣Обработка запросов:
Для каждого запроса проверьте, освещена ли ячейка, используя словари строк, столбцов, диагоналей и обратных диагоналей.
После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.

3⃣Обновление состояний ламп:
Обновите состояния ламп и освещенных ячеек после каждого запроса, чтобы корректно обрабатывать следующие запросы.

😎 Решение:

class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_set<long long> lamps_on;
        unordered_map<int, int> rows, cols, diag1, diag2;

        for (auto& lamp : lamps) {
            int r = lamp[0], c = lamp[1];
            long long key = (long long)r * n + c;
            if (lamps_on.count(key)) continue;
            lamps_on.insert(key);
            rows[r]++;
            cols[c]++;
            diag1[r - c]++;
            diag2[r + c]++;
        }

        vector<int> result;
        vector<pair<int, int>> directions = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

        for (auto& query : queries) {
            int r = query[0], c = query[1];
            if (rows[r] > 0 || cols[c] > 0 || diag1[r - c] > 0 || diag2[r + c] > 0) {
                result.push_back(1);
            } else {
                result.push_back(0);
            }

            for (auto& dir : directions) {
                int nr = r + dir.first, nc = c + dir.second;
                long long key = (long long)nr * n + nc;
                if (lamps_on.count(key)) {
                    lamps_on.erase(key);
                    rows[nr]--;
                    cols[nc]--;
                    diag1[nr - nc]--;
                    diag2[nr + nc]--;
                }
            }
        }

        return result;
    }
};

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, обозначающие диапазон [left, right].
Нужно вернуть результат побитового AND всех чисел в этом диапазоне (включительно).

Пример:

Input: left = 5, right = 7 Output: 4

👨‍💻 Алгоритм:

1⃣Пока left < right, сдвигаем оба числа вправо (>>= 1), пока они не станут равны. Это находит общий префикс битов.

2⃣Подсчитываем количество сдвигов — это количество младших битов, которые могут изменяться в диапазоне, и обнуляются при AND.

3⃣После этого сдвигаем результат left обратно влево (<< shift) — возвращаем биты на место.

😎 Решение:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
};

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

Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

👨‍💻 Алгоритм:

1⃣Получите цвет начального пикселя.

2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.

3⃣Обновите изображение и верните его.

😎 Решение:

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
private:
    void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        dfs(image, x + 1, y, originalColor, newColor);
        dfs(image, x - 1, y, originalColor, newColor);
        dfs(image, x, y + 1, originalColor, newColor);
        dfs(image, x, y - 1, originalColor, newColor);
    }
};

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

Задача: 107. Binary Tree Level Order Traversal II
Сложность: medium

Дан корень бинарного дерева. Верните обход значений узлов снизу вверх по уровням (то есть слева направо, уровень за уровнем, от листа к корню).

Пример:

Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]

👨‍💻 Алгоритм:

1⃣Инициализируйте список levels. Его длина определяет текущий уровень дерева. Если уровень level равен длине levels, нужно добавить новый вложенный список.

2⃣Добавьте значение текущего узла в список соответствующего уровня.

3⃣Рекурсивно вызывайте helper для левого и правого поддеревьев, передавая level + 1.

😎 Решение:

class Solution {
public:
    vector<vector<int>> levels;

    void helper(TreeNode* node, int level) {
        if (levels.size() == level)
            levels.push_back(vector<int>());
        levels[level].push_back(node->val);
        if (node->left != NULL) helper(node->left, level + 1);
        if (node->right != NULL) helper(node->right, level + 1);
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if (root == NULL) return levels;
        helper(root, 0);
        reverse(levels.begin(), levels.end());
        return levels;
    }
};

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

Задача: 287. Find the Duplicate Number
Сложность: medium

Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.

Пример:

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

👨‍💻 Алгоритм:

1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

2⃣Восстановление массива:
Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива.

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int duplicate = -1;
        for (int i = 0; i < nums.size(); i++) {
            int cur = abs(nums[i]);
            if (nums[cur] < 0) {
                duplicate = cur;
                break;
            }
            nums[cur] *= -1;
        }
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = abs(nums[i]);
        }
        return duplicate;
    }
};

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

Задача: 284. Peeking Iterator
Сложность: medium

Создайте итератор, который поддерживает операцию 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;
    }
};

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

Задача: 111. Minimum Depth of Binary Tree
Сложность: easy

Дано бинарное дерево. Найдите его минимальную глубину — количество узлов вдоль кратчайшего пути от корня до ближайшего листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7] Output: 2

👨‍💻 Алгоритм:

1⃣Используем рекурсивный обход в глубину (dfs). Базовый случай: если узел null, глубина равна 0.

2⃣Если левый потомок отсутствует, возвращаем 1 + dfs(root->right) — двигаемся по правому поддереву.

3⃣Если правый потомок отсутствует, возвращаем 1 + dfs(root->left) — двигаемся по левому поддереву.
Если оба потомка существуют — возвращаем 1 + min(dfs(left), dfs(right)).

😎 Решение:

class Solution {
public:
    int dfs(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        if (!root->left) {
            return 1 + dfs(root->right);
        } else if (!root->right) {
            return 1 + dfs(root->left);
        }
        return 1 + min(dfs(root->left), dfs(root->right));
    }

    int minDepth(TreeNode* root) {
        return dfs(root);
    }
};

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

Задача: 938. Range Sum of BST
Сложность: easy

Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high].

Пример:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

👨‍💻 Алгоритм:

1⃣Если дерево пустое, вернуть 0.

2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве.
Если значение текущего узла больше high, рекурсивно искать в левом поддереве.

3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях.

😎 Решение:

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

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        if (root->val < low) return rangeSumBST(root->right, low, high);
        if (root->val > high) return rangeSumBST(root->left, low, high);
        return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
    }
};

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

Задача: 472. Concatenated Words
Сложность: hard

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.
Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

👨‍💻 Алгоритм:

1⃣Для каждого слова в списке:
Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка.

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

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

using namespace std;

class Solution {
    bool dfs(const string& word, int length, vector<bool>& visited,
             const unordered_set<string>& dictionary) {
        if (length == word.length()) {
            return true;
        }
        if (visited[length]) {
            return false;
        }
        visited[length] = true;
        for (int i = word.length() - (length == 0 ? 1 : 0); i > length; --i) {
            if (dictionary.count(word.substr(length, i - length)) &&
                dfs(word, i, visited, dictionary)) {
                return true;
            }
        }
        return false;
    }

public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> dictionary(words.begin(), words.end());
        vector<string> answer;
        for (const string& word : words) {
            vector<bool> visited(word.length());
            if (dfs(word, 0, visited, dictionary)) {
                answer.push_back(word);
            }
        }
        return answer;
    }
};

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

Задача: 1394. Find Lucky Integer in an Array
Сложность: easy

Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению.

Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1.

Пример:

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

👨‍💻 Алгоритм:

1⃣Создайте хэш-карту для подсчёта частоты каждого числа в массиве.

2⃣Пройдитесь по ключам и значениям хэш-карты, чтобы найти счастливые числа.

3⃣Верните наибольшее счастливое число или -1, если таких чисел нет.

😎 Решение:

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

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

Задача: 1035. Uncrossed Lines
Сложность: medium

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

Пример:

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

👨‍💻 Алгоритм:

1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

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

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

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

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

Задача: 237. Delete Node in a Linked List
Сложность: medium

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

Пример:

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

👨‍💻 Алгоритм:

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка.

😎 Решение:

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

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

Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

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

Пример:

Input: s = "aabcbc"
Output: true

👨‍💻 Алгоритм:

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

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

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

        return stk.empty();
    }
};

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

Задача: 33. Search in Rotated Sorted Array
Сложность: medium

Дан массив nums, отсортированный по возрастанию и повернутый на некотором неизвестном индексе. Необходимо найти индекс элемента target. Если он не найден — вернуть -1. Решение должно работать за O(log n).

Пример:

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

👨‍💻 Алгоритм:

1⃣Инициализируем границы бинарного поиска: left = 0, right = n-1.

2⃣В цикле проверяем значение в середине. Если совпадает с target — возвращаем индекс.

3⃣Определяем, какая половина массива отсортирована, и сужаем поиск к той части, где может находиться target.

😎 Решение:

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

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

Задача: 1133. Largest Unique Number
Сложность: easy

Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.

Пример:

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

👨‍💻 Алгоритм:

1⃣Создайте хеш-таблицу для хранения количества каждого числа в массиве.

2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа.

3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат.

😎 Решение:

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

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

Задача: 249. Group Shifted Strings
Сложность: medium

Пример:

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

👨‍💻 Алгоритм:

1⃣Для каждой строки вычисляем нормализованный ключ, сдвигая строку так, чтобы она начиналась с 'a'. Используем формулу (буква - сдвиг + 26) % 26 + 'a'.

2⃣Сохраняем строки в unordered_map, где ключом служит нормализованная строка, а значением — список всех строк, попадающих под эту группу.

3⃣Формируем результат из всех списков строк, сгруппированных по ключу, и возвращаем его.

😎 Решение:

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

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

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

        return groups;
    }
};

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

Задача: 722. Remove Comments
Сложность: medium

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

Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.

Пример:

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

👨‍💻 Алгоритм:

1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.

2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.

3⃣После обработки всех строк добавьте непустые строки из buffer в результат.

😎 Решение:

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

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