C/C++ | LeetCode

Задача: 1365. How Many Numbers Are Smaller Than the Current Number Сложность: easy Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i]. Верните ответ в виде массива. Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

👨‍💻 Алгоритм: 1⃣Создание копии и сортировка массива: Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего. 2⃣Поиск индекса каждого элемента: Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i]. 3⃣Формирование ответа: Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего. 😎 Решение:

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> smallerNumbersThanCurrent(std::vector<int>& nums) {
        std::vector<int> sortedNums = nums;
        std::sort(sortedNums.begin(), sortedNums.end());
        std::vector<int> result;
        
        for (int num : nums) {
            result.push_back(std::find(sortedNums.begin(), sortedNums.end(), num) - sortedNums.begin());
        }
        
        return result;
    }
};

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

Задача: 45. Jump Game II Сложность: medium Дан массив nums, где каждый элемент nums[i] обозначает максимальную длину прыжка из позиции i. Необходимо вернуть минимальное количество прыжков, чтобы достичь последнего индекса. Гарантируется, что это возможно. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализировать: curEnd = 0 — граница текущего прыжка curFar = 0 — самая дальняя достижимая позиция answer = 0 — количество прыжков 2⃣Перебрать массив до предпоследнего индекса: На каждом шаге обновить curFar = max(curFar, i + nums[i]) 3⃣Когда текущий индекс достигает curEnd, совершается новый прыжок: Увеличить answer++ Обновить curEnd = curFar 😎 Решение:

class Solution {
public:
    int jump(vector<int>& nums) {
        int answer = 0, n = int(nums.size());
        int curEnd = 0, curFar = 0;

        for (int i = 0; i < n - 1; ++i) {
            curFar = max(curFar, i + nums[i]);
            if (i == curEnd) {
                answer++;
                curEnd = curFar;
            }
        }
        return answer;
    }
};

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

Задача: 1039. Minimum Score Triangulation of Polygon Сложность: medium У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника. Пример:

Input: values = [1,2,3]
Output: 6

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

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i][j] = INT_MAX;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
};

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

Задача: 460. LFU Cache Сложность: hard Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU). Реализуйте класс LFUCache: LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных. int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1. void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ. Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом. Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа. Функции get и put должны иметь среднюю временную сложность O(1). Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

👨‍💻 Алгоритм: 1⃣insert(int key, int frequency, int value): Вставить пару частота-значение в cache с заданным ключом. Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ. 2⃣int get(int key): Если ключа нет в кеше, вернуть -1. Получить частоту и значение из кеша. Удалить ключ из LinkedHashSet, связанного с частотой. Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies. Вызвать insert(key, frequency + 1, value). Вернуть значение. 3⃣void put(int key, int value): Если capacity <= 0, выйти. Если ключ существует, обновить значение и вызвать get(key). Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша. Установить minf в 1. Вызвать insert(key, 1, value). 😎 Решение:

#include <unordered_map>
#include <list>

class LFUCache {
    std::unordered_map<int, std::list<std::pair<int, int>>> frequencies;
    std::unordered_map<int, std::pair<int, std::list<std::pair<int, int>>::iterator>> cache;
    int capacity;
    int minf;

    void insert(int key, int frequency, int value) {
        frequencies[frequency].emplace_back(key, value);
        cache[key] = {frequency, --frequencies[frequency].end()};
    }

public:
    LFUCache(int capacity) : capacity(capacity), minf(0) {}

    int get(int key) {
        const auto it = cache.find(key);
        if (it == cache.end()) return -1;
        const int f = it->second.first;
        const auto iter = it->second.second;
        const std::pair<int, int> kv = *iter;
        frequencies[f].erase(iter);
        if (frequencies[f].empty()) {
            frequencies.erase(f);
            if (minf == f) ++minf;
        }
        insert(key, f + 1, kv.second);
        return kv.second;
    }

    void put(int key, int value) {
        if (capacity <= 0) return;
        const auto it = cache.find(key);
        if (it != cache.end()) {
            it->second.second->second = value;
            get(key);
            return;
        }
        if (capacity == cache.size()) {
            cache.erase(frequencies[minf].front().first);
            frequencies[minf].pop_front();
            if (frequencies[minf].empty()) frequencies.erase(minf);
        }
        minf = 1;
        insert(key, 1, value);
    }
};

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

Задача: 69. Sqrt(x) Сложность: easy Дано неотрицательное число x. Верните его целочисленный квадратный корень, округлённый вниз. Нельзя использовать встроенные функции, вроде pow или sqrt. Пример:

Input: x = 4 Output: 2

👨‍💻 Алгоритм: 1⃣Если x < 2, сразу вернуть x, так как sqrt(0) = 0, sqrt(1) = 1 2⃣Используем бинарный поиск в диапазоне от 2 до x / 2 На каждой итерации: pivot = (left + right) / 2 Если pivot * pivot == x, вернуть pivot Если pivot * pivot < x, сдвинуть left = pivot + 1 Иначе right = pivot - 1 3⃣В конце вернуть right, т.к. он будет ближайшим целым значением, квадрат которого ≤ x 😎 Решение:

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        long num;
        int pivot, left = 2, right = x / 2;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            num = (long)pivot * pivot;
            if (num > x)
                right = pivot - 1;
            else if (num < x)
                left = pivot + 1;
            else
                return pivot;
        }
        return right;
    }
};

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

Задача: 1047. Remove All Adjacent Duplicates In String Сложность: easy Вам дана строка s, состоящая из строчных английских букв. Удаление дубликатов заключается в выборе двух соседних и одинаковых букв и их удалении. Мы многократно производим удаление дубликатов в s, пока не перестанем это делать. Верните конечную строку после того, как все такие удаления дубликатов будут произведены. Можно доказать, что ответ уникален. Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stack;
        for (char c : s) {
            if (!stack.empty() && stack.top() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        string result;
        while (!stack.empty()) {
            result += stack.top();
            stack.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

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

Задача: 1426. Counting Elements Сложность: easy Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно. Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

👨‍💻 Алгоритм: 1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве. 2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве. 3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика. 😎 Решение:

class Solution {
public:
    int countElements(vector<int>& arr) {
        int count = 0;
        for (int x : arr) {
            if (integerInArray(arr, x + 1)) {
                count++;
            }
        }
        return count;
    }
    
    bool integerInArray(vector<int>& arr, int target) {
        for (int x : arr) {
            if (x == target) {
                return true;
            }
        }
        return false;
    }
};

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

Задача: 895. Maximum Frequency Stack Сложность: hard Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека. Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

class FreqStack {
    std::unordered_map<int, int> freq;
    std::unordered_map<int, std::stack<int>> group;
    int maxfreq = 0;

public:
    FreqStack() {}

    void push(int val) {
        int f = ++freq[val];
        if (f > maxfreq) maxfreq = f;
        group[f].push(val);
    }

    int pop() {
        int val = group[maxfreq].top();
        group[maxfreq].pop();
        if (group[maxfreq].empty()) maxfreq--;
        freq[val]--;
        return val;
    }
};

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

Задача: 1196. How Many Apples Can You Put into the Basket Сложность: easy У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса. Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину. Пример:

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

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

class Solution {
public:
    int maxNumberOfApples(vector<int>& weight) {
        priority_queue<int, vector<int>, greater<int>> heap(weight.begin(), weight.end());
        int apples = 0, units = 0;

        while (!heap.empty() && units + heap.top() <= 5000) {
            units += heap.top();
            heap.pop();
            apples++;
        }
        return apples;
    }
};

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

Задача: 1219. Path with Maximum Gold Сложность: medium В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста. Верните максимальное количество золота, которое вы можете собрать при следующих условиях: - Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки. - Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз. - Вы не можете посещать одну и ту же ячейку более одного раза. - Никогда не посещайте ячейку с 0 золотом. - Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото. Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), maxGold = 0;
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row, col));
            }
        }
        return maxGold;
    }

private:
    int directions[5] = {0, 1, 0, -1, 0};

    int dfsBacktrack(vector<vector<int>>& grid, int rows, int cols, int row, int col) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0) return 0;
        int originalVal = grid[row][col];
        grid[row][col] = 0;
        int maxGold = 0;
        for (int i = 0; i < 4; ++i) {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row + directions[i], col + directions[i + 1]));
        }
        grid[row][col] = originalVal;
        return maxGold + originalVal;
    }
};

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

Задача: 468. Validate IP Address Сложность: medium Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами. Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7 ", где: 1 <= xi.length <= 4 xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F'). Ведущие нули в xi допускаются. Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

👨‍💻 Алгоритм: 1⃣Для проверки адреса IPv4: Разделить IP на четыре части по разделителю ".". Проверить каждую подстроку: Является ли она целым числом между 0 и 255. Не содержит ли она ведущих нулей (исключение — число "0"). 2⃣Для проверки адреса IPv6: Разделить IP на восемь частей по разделителю ":". Проверить каждую подстроку: Является ли она шестнадцатеричным числом длиной от 1 до 4 символов. 3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither". 😎 Решение:

class Solution {
public:
    std::string validateIPv4(const std::string& IP) {
        std::vector<std::string> nums = split(IP, '.');
        if (nums.size() != 4) return "Neither";
        for (std::string& x : nums) {
            if (x.size() == 0 || x.size() > 3) return "Neither";
            if (x[0] == '0' && x.size() != 1) return "Neither";
            if (!std::all_of(x.begin(), x.end(), ::isdigit)) return "Neither";
            if (std::stoi(x) > 255) return "Neither";
        }
        return "IPv4";
    }

    std::string validateIPv6(const std::string& IP) {
        std::vector<std::string> nums = split(IP, ':');
        if (nums.size() != 8) return "Neither";
        std::unordered_set<char> hexdigits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                                              'a', 'b', 'c', 'd', 'e', 'f', 'A', 'B', 'C', 'D', 'E', 'F'};
        for (std::string& x : nums) {
            if (x.size() == 0 || x.size() > 4) return "Neither";
            for (char ch : x) {
                if (hexdigits.find(ch) == hexdigits.end()) return "Neither";
            }
        }
        return "IPv6";
    }

    std::string validIPAddress(const std::string& IP) {
        if (std::count(IP.begin(), IP.end(), '.') == 3) {
            return validateIPv4(IP);
        } else if (std::count(IP.begin(), IP.end(), ':') == 7) {
            return validateIPv6(IP);
        } else {
            return "Neither";
        }
    }

private:
    std::vector<std::string> split(const std::string& s, char delimiter) {
        std::vector<std::string> tokens;
        std::string token;
        std::istringstream tokenStream(s);
        while (std::getline(tokenStream, token, delimiter)) {
            tokens.push_back(token);
        }
        return tokens;
    }
};

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

Задача: 360. Sort Transformed Array Сложность: medium Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке. Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

👨‍💻 Алгоритм: 1⃣Преобразование и сортировка Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed. 2⃣Поразрядная сортировка Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed. 3⃣Сортировка по цифре Для каждой цифры (разряда) используем подсчет для сортировки массива. 😎 Решение:

#include <vector>
#include <algorithm>
#include <cmath>

class Solution {
public:
    std::vector<int> sortTransformedArray(std::vector<int>& nums, int a, int b, int c) {
        std::vector<int> transformed(nums.size());
        for (size_t i = 0; i < nums.size(); ++i) {
            transformed[i] = a * nums[i] * nums[i] + b * nums[i] + c;
        }

        radixSort(transformed);

        return transformed;
    }

private:
    void radixSort(std::vector<int>& array) {
        int maxElement = abs(array[0]);
        for (int num : array) {
            maxElement = std::max(maxElement, abs(num));
        }

        for (int placeValue = 1; maxElement / placeValue > 0; placeValue *= 10) {
            countingSortByDigit(array, placeValue);
        }

        std::vector<int> negatives, positives;
        for (int num : array) {
            if (num < 0) negatives.push_back(num);
            else positives.push_back(num);
        }

        std::sort(negatives.begin(), negatives.end());
        std::sort(positives.begin(), positives.end());

        std::merge(negatives.begin(), negatives.end(), positives.begin(), positives.end(), array.begin());
    }

    void countingSortByDigit(std::vector<int>& array, int placeValue) {
        std::vector<int> output(array.size());
        std::vector<int> count(10, 0);

        for (int num : array) {
            int digit = (abs(num) / placeValue) % 10;
            count[digit]++;
        }

        for (int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }

        for (int i = array.size() - 1; i >= 0; --i) {
            int num = array[i];
            int digit = (abs(num) / placeValue) % 10;
            output[count[digit] - 1] = num;
            count[digit]--;
        }

        for (size_t i = 0; i < array.size(); ++i) {
            array[i] = output[i];
        }
    }
};

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

Задача: 994. Rotting Oranges Сложность: medium Дан m x n сетка, где каждая ячейка может иметь одно из трех значений: 0, представляющее пустую ячейку, 1, представляющее свежий апельсин, 2, представляющее гнилой апельсин. Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым. Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1. Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        int freshCount = 0;
        int minutes = 0;
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        if (freshCount == 0) return 0;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto [x, y] = q.front(); q.pop();
                for (auto dir : directions) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        freshCount--;
                        q.push({nx, ny});
                    }
                }
            }
            if (!q.empty()) {
                minutes++;
            }
        }
        
        return freshCount == 0 ? minutes : -1;
    }
};

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

Задача: 234. Palindrome Linked List Сложность: easy Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае. Пример:

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

👨‍💻 Алгоритм: 1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null. 2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся. 3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата. 😎 Решение:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;

        ListNode* currentNode = head;
        while (currentNode != nullptr) {
            vals.push_back(currentNode->val);
            currentNode = currentNode->next;
        }

        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (vals[front] != vals[back]) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
};

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

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int s1Len = s1.size(), s2Len = s2.size();
        if (s1Len > s2Len) return false;
        
        vector<int> s1Count(26, 0), s2Count(26, 0);
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count == s2Count) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count == s2Count;
    }
};

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

Задача: 736. Parse Lisp Expression Сложность: hard Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

class Solution {
public:
    int evaluate(string expression) {
        return evaluate(expression, {});
    }

private:
    int evaluate(string expression, unordered_map<string, int> env) {
        if (expression[0] != '(') {
            if (isdigit(expression[0]) || expression[0] == '-') {
                return stoi(expression);
            }
            return env[expression];
        }

        vector<string> tokens = tokenize(expression);
        if (tokens[0] == "let") {
            for (size_t i = 1; i < tokens.size() - 2; i += 2) {
                env[tokens[i]] = evaluate(tokens[i + 1], env);
            }
            return evaluate(tokens.back(), env);
        } else if (tokens[0] == "add") {
            return evaluate(tokens[1], env) + evaluate(tokens[2], env);
        } else if (tokens[0] == "mult") {
            return evaluate(tokens[1], env) * evaluate(tokens[2], env);
        }
        return 0;
    }

    vector<string> tokenize(const string& expression) {
        vector<string> tokens;
        string token;
        int parens = 0;
        istringstream iss(expression);
        char c;

        while (iss >> c) {
            if (c == '(') {
                parens++;
                if (parens == 1) continue;
            } else if (c == ')') {
                parens--;
                if (parens == 0) {
                    tokens.push_back(tokenize(token));
                    token = "";
                    continue;
                }
            } else if (c == ' ' && parens == 1) {
                if (!token.empty()) {
                    tokens.push_back(token);
                    token = "";
                }
                continue;
            }
            token += c;
        }
        if (!token.empty()) {
            tokens.push_back(token);
        }
        return tokens;
    }
};

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

Задача: 482. License Key Formatting Сложность: easy Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k. Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные. Верните переформатированный лицензионный ключ. Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

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

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        int count = 0;
        string ans;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] != '-') {
                ans.push_back(toupper(s[i]));
                count++;
                if (count == k) {
                    ans.push_back('-');
                    count = 0;
                }
            }
        }
        if (!ans.empty() && ans.back() == '-') {
            ans.pop_back();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

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

Задача: 376. Wiggle Subsequence Сложность: medium Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями. Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными. В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю. Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке. Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums. Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

👨‍💻 Алгоритм: 1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием. 2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием. 3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания. 😎 Решение:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2)
            return nums.size();
        vector<int> up(nums.size(), 0);
        vector<int> down(nums.size(), 0);
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = max(down[i], up[j] + 1);
                }
            }
        }
        return 1 + max(down[nums.size() - 1], up[nums.size() - 1]);
    }
};

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

Задача: 1197. Minimum Knight Moves Сложность: medium На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0]. У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении. Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует. Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

#include <deque>
#include <unordered_map>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int minKnightMoves(int x, int y) {
        vector<vector<int>> offsets = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
                                       {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
        
        deque<vector<int>> originQueue = {{0, 0, 0}};
        unordered_map<string, int> originDistance = {{"0,0", 0}};
        
        deque<vector<int>> targetQueue = {{x, y, 0}};
        unordered_map<string, int> targetDistance = {{to_string(x) + "," + to_string(y), 0}};
        
        while (true) {
            auto origin = originQueue.front();
            originQueue.pop_front();
            string originKey = to_string(origin[0]) + "," + to_string(origin[1]);
            if (targetDistance.find(originKey) != targetDistance.end()) {
                return origin[2] + targetDistance[originKey];
            }
            
            auto target = targetQueue.front();
            targetQueue.pop_front();
            string targetKey = to_string(target[0]) + "," + to_string(target[1]);
            if (originDistance.find(targetKey) != originDistance.end()) {
                return target[2] + originDistance[targetKey];
            }
            
            for (auto& offset : offsets) {
                vector<int> nextOrigin = {origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1};
                string nextOriginKey = to_string(nextOrigin[0]) + "," + to_string(nextOrigin[1]);
                if (originDistance.find(nextOriginKey) == originDistance.end()) {
                    originQueue.push_back(nextOrigin);
                    originDistance[nextOriginKey] = nextOrigin[2];
                }
                
                vector<int> nextTarget = {target[0] + offset[0], target[1] + offset[1], target[2] + 1};
                string nextTargetKey = to_string(nextTarget[0]) + "," + to_string(nextTarget[1]);
                if (targetDistance.find(nextTargetKey) == targetDistance.end()) {
                    targetQueue.push_back(nextTarget);
                    targetDistance[nextTargetKey] = nextTarget[2];
                }
            }
        }
    }
};

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

Задача: 1041. Robot Bounded In Circle Сложность: medium На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее. Пример:

Input: instructions = "GGLLGG"
Output: true

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

class Solution {
public:
    bool isRobotBounded(string instructions) {
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0, direction = 0;
        
        for (char instruction : instructions) {
            if (instruction == 'G') {
                x += directions[direction][0];
                y += directions[direction][1];
            } else if (instruction == 'L') {
                direction = (direction + 3) % 4;
            } else if (instruction == 'R') {
                direction = (direction + 1) % 4;
            }
        }
        
        return (x == 0 && y == 0) || direction != 0;
    }
};

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