Задача: 1669. Merge In Between Linked Lists
Сложность: medium

Вам даны два связанных списка: list1 и list2 размером n и m соответственно.

Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.

Синие ребра и узлы на рисунке в вверху поста указывают на результат:

Пример:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

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

1⃣Инициализация и добавление узлов из list1 до узла a в массив:
Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.

2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.

3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.

😎 Решение:

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        vector<int> mergeArray;
        int index = 0;
        ListNode* current1 = list1;
        
        while (index < a) {
            mergeArray.push_back(current1->val);
            current1 = current1->next;
            index++;
        }
        
        ListNode* current2 = list2;
        while (current2 != nullptr) {
            mergeArray.push_back(current2->val);
            current2 = current2->next;
        }
        
        while (index < b + 1) {
            current1 = current1->next;
            index++;
        }
        
        while (current1 != nullptr) {
            mergeArray.push_back(current1->val);
            current1 = current1->next;
        }
        
        ListNode* resultList = nullptr;
        for (int i = mergeArray.size() - 1; i >= 0; i--) {
            resultList = new ListNode(mergeArray[i], resultList);
        }
        
        return resultList;
    }
};

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

2⃣Разбиваем полученный результат на слова, используя пробелы в качестве разделителей.

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

class Solution {
public:
    string mostCommonWord(string paragraph, vector<string>& banned) {
        for (char& c : paragraph) {
            c = isalnum(c) ? tolower(c) : ' ';
        }

        istringstream iss(paragraph);
        string word;
        unordered_map<string, int> wordCount;
        unordered_set<string> bannedWords(banned.begin(), banned.end());

        while (iss >> word) {
            if (bannedWords.find(word) == bannedWords.end()) {
                wordCount[word]++;
            }
        }

        return max_element(wordCount.begin(), wordCount.end(), 
                           [](const pair<string, int>& a, const pair<string, int>& b) {
                               return a.second < b.second;
                           })->first;
    }
};

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

Дано множество слов. Необходимо определить, является ли слово уникальным по своей аббревиатуре среди слов в словаре.

Пример:

Input: dictionary = ["deer", "door", "cake", "card"]
isUnique("dear") → false
isUnique("cart") → true
isUnique("cake") → true

👨‍💻 Алгоритм

1⃣Создание сокращения слова
Если длина слова ≤ 2, возвращаем его как есть. Иначе создаем строку: первая буква + количество символов между + последняя буква. Например:
"dog" → "d1g"
"it" → "it"

2⃣Инициализация
Создаем множество dict, в которое помещаем все слова словаря (для точной проверки совпадения), и abbrDict, где ключ — сокращение, а значение — уникальность (true/false). Если для одной аббревиатуры встречается несколько разных слов, устанавливаем флаг как false.

3⃣Проверка isUnique
Если сокращение не найдено — возвращаем true.
Если найдено и уникально, проверяем, есть ли само слово в оригинальном словаре. Если есть — true, иначе — false.

😎 Решение

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string>& dictionary) {
        for (const string& word : dictionary) {
            dict.insert(word);
            string abbr = toAbbr(word);
            if (abbrDict.count(abbr)) {
                abbrDict[abbr] = abbrDict[abbr] == word;
            } else {
                abbrDict[abbr] = true;
            }
        }
    }

    bool isUnique(string word) {
        string abbr = toAbbr(word);
        auto it = abbrDict.find(abbr);
        return it == abbrDict.end() || (it->second && dict.count(word));
    }

private:
    unordered_map<string, bool> abbrDict;
    unordered_set<string> dict;

    string toAbbr(const string& word) {
        int n = word.length();
        if (n <= 2) return word;
        return word.front() + to_string(n - 2) + word.back();
    }
};

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

Задача: 1427. Perform String Shifts
Сложность: easy

Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]:
directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо).
amounti - это количество, на которое строка s должна быть сдвинута.
Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец.
Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало.
Верните итоговую строку после всех операций.

Пример:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

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

1⃣Пройдите по списку сдвигов, суммируя все сдвиги вправо и влево в два отдельных значения.

2⃣Определите, какое из значений больше, и частично компенсируйте его другим. Затем выполните соответствующий сдвиг с оставшимся значением. Если оба значения равны, строка останется неизменной.

3⃣Выполните сдвиг строки на основе вычисленного значения и верните итоговую строку.

😎 Решение:

class Solution {
public:
    string stringShift(string s, vector<vector<int>>& shift) {
        int leftShifts = 0, rightShifts = 0;
        for (auto& move : shift) {
            if (move[0] == 0) {
                leftShifts += move[1];
            } else {
                rightShifts += move[1];
            }
        }
        
        int netShifts = (rightShifts - leftShifts) % s.length();
        if (netShifts < 0) {
            netShifts += s.length();
        }
        
        if (netShifts == 0) {
            return s;
        }
        
        return s.substr(s.length() - netShifts) + s.substr(0, s.length() - netShifts);
    }
};

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

Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

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

Пример:

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

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
public:
    vector<int> inorderNodes;
    
    void inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        
        inorderTraversal(root->left);
        inorderNodes.push_back(root->val);
        inorderTraversal(root->right);
    }
    
    int minDiffInBST(TreeNode* root) {
        inorderTraversal(root);
        
        int minDistance = INT_MAX;
        for (int i = 1; i < inorderNodes.size(); i++) {
            minDistance = min(minDistance, inorderNodes[i] - inorderNodes[i - 1]);
        }
        
        return minDistance;
    }
};

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

Задача: 1018. Binary Prefix Divisible By 5
Сложность: easy

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

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

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

2⃣Итерация по массиву:
Пройдите по всем элементам массива nums. Для каждого элемента:
Обновите значение x, учитывая текущий бит.
Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.
Чтобы избежать переполнения, используйте модуль 5 для переменной x.

3⃣Возврат результата:
Верните массив answer с результатами проверки делимости на 5.

😎 Решение:

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        int x = 0;
        vector<bool> answer;
        for (int num : nums) {
            x = (x * 2 + num) % 5;
            answer.push_back(x == 0);
        }
        return answer;
    }
};

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

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

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

class Solution {
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        int m = grid.size(), n = grid[0].size();
        int original_color = grid[row][col];
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<pair<int, int>> borders;

        function<void(int, int)> dfs = [&](int r, int c) {
            visited[r][c] = true;
            bool is_border = false;
            for (auto [dr, dc] : vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    if (!visited[nr][nc]) {
                        if (grid[nr][nc] == original_color) {
                            dfs(nr, nc);
                        } else {
                            is_border = true;
                        }
                    }
                } else {
                    is_border = true;
                }
            }
            if (is_border || r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                borders.emplace_back(r, c);
            }
        };

        dfs(row, col);
        for (auto [r, c] : borders) {
            grid[r][c] = color;
        }

        return grid;
    }
};

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

Задача: 1323. Maximum 69 Number
Сложность: easy

Дано положительное целое число num, состоящее только из цифр 6 и 9.

Верните максимальное число, которое можно получить, изменив не более одной цифры (6 становится 9, а 9 становится 6).

Пример:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

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

1⃣Преобразуйте входное целое число num в итерируемый и изменяемый объект num_obj.

2⃣Пройдитесь по num_obj и, если найдете цифру 6, замените её на 9 и прекратите итерацию.

3⃣Верните целое число, преобразованное из измененного num_obj.

😎 Решение:

class Solution {
public:
    int maximum69Number (int num) {
        string numStr = to_string(num);
        for (char &c : numStr) {
            if (c == '6') {
                c = '9';
                break;
            }
        }
        return stoi(numStr);
    }
};

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

Задача: 772. Basic Calculator III
Сложность: medium

Реализуйте базовый калькулятор для вычисления простого строкового выражения.

Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.

Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].

Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().

Пример:

Input: s = "1+1"
Output: 2

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

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎 Решение:

class Solution {
public:
    string evaluate(char operator, string first, string second) {
        int x = stoi(first);
        int y = stoi(second);
        int res = 0;
        
        if (operator == '+') {
            res = x;
        } else if (operator == '-') {
            res = -x;
        } else if (operator == '*') {
            res = x * y;
        } else {
            res = x / y;
        }
        
        return to_string(res);
    }
    
    int calculate(string s) {
        stack<string> stack;
        string curr = "";
        char previousOperator = '+';
        s += "@";
        unordered_set<string> operators = {"+", "-", "*", "/"};
        
        for (char c: s) {
            if (isdigit(c)) {
                curr += c;
            } else if (c == '(') {
                stack.push(string(1, previousOperator));
                previousOperator = '+';
            } else {
                if (previousOperator == '*' || previousOperator == '/') {
                    stack.push(evaluate(previousOperator, stack.top(), curr));
                    stack.pop();
                } else {
                    stack.push(evaluate(previousOperator, curr, "0"));
                }
                
                curr = "";
                previousOperator = c;
                if (c == ')') {
                    int currentTerm = 0;
                    while (operators.find(stack.top()) == operators.end()) {
                        currentTerm += stoi(stack.top());
                        stack.pop();
                    }
                    
                    curr = to_string(currentTerm);
                    previousOperator = stack.top()[0];
                    stack.pop();
                }
            }
        }
        
        int ans = 0;
        while (!stack.empty()) {
            ans += stoi(stack.top());
            stack.pop();
        }

        return ans;
    }
};

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int m = image.size(), n = image[0].size();
        int left = searchColumns(image, 0, y, 0, m, true);
        int right = searchColumns(image, y + 1, n, 0, m, false);
        int top = searchRows(image, 0, x, left, right, true);
        int bottom = searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

private:
    int searchColumns(vector<vector<char>>& image, int i, int j, int top, int bottom, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int t = top;
            while (t < bottom && image[t][k] == '0') t++;
            if ((t < bottom) == opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }

    int searchRows(vector<vector<char>>& image, int i, int j, int left, int right, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int l = left;
            while (l < right && image[k][l] == '0') l++;
            if ((l < right) == opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }
};

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

Задача: 115. Distinct Subsequences
Сложность: hard

Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.

Пример:

Input: s = "rabbbit", t = "rabbit" Output: 3
Explanation:
Из строки s = "rabbbit" можно получить "rabbit" тремя разными способами, выбирая разные b на позиции 2, 3 и 4.

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

1⃣Реализуем рекурсивную функцию recurse(i, j), где i — текущий индекс в строке s, а j — в строке t. Используем хэш-таблицу memo для кэширования результатов recurse(i, j).

2⃣Базовые случаи:
Если j == t.length() — вся строка t успешно сопоставлена, возвращаем 1.
Если i == s.length() — строка s закончилась до завершения t, возвращаем 0.

3⃣Если s[i] == t[j], то у нас два варианта:
использовать символ s[i] → recurse(i+1, j+1)
пропустить символ s[i] → recurse(i+1, j)
Если s[i] != t[j], продолжаем только с recurse(i+1, j). Результат сохраняем в memo и возвращаем.

😎 Решение:

class Solution {
private:
    unordered_map<string, int> memo;

public:
    int numDistinct(string s, string t) {
        if (s.size() < t.size()) return 0;
        if (s == t || t.empty()) return 1;

        string key = to_string(s.size()) + "," + to_string(t.size());
        if (memo.find(key) != memo.end()) return memo[key];

        int N = s.size(), M = t.size();
        int ans = numDistinct(s.substr(0, N - 1), t);

        if (s[N - 1] == t[M - 1])
            ans += numDistinct(s.substr(0, N - 1), t.substr(0, M - 1));

        memo[key] = ans;
        return ans;
    }
};

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

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

😎 Решение:

using namespace std;

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;

        for (int i = 0; i < equations.size(); ++i) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }

        vector<double> results;
        for (auto& query : queries) {
            string C = query[0], D = query[1];
            if (!graph.count(C) || !graph.count(D)) {
                results.push_back(-1.0);
            } else {
                results.push_back(bfs(C, D, graph));
            }
        }
        return results;
    }

private:
    double bfs(const string& start, const string& end, unordered_map<string, unordered_map<string, double>>& graph) {
        queue<pair<string, double>> q;
        q.push({start, 1.0});
        unordered_set<string> visited;

        while (!q.empty()) {
            auto [current, product] = q.front(); q.pop();
            if (current == end) return product;
            visited.insert(current);
            for (auto& [neighbor, value] : graph[current]) {
                if (!visited.count(neighbor)) {
                    q.push({neighbor, product * value});
                }
            }
        }
        return -1.0;
    }
};

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

Задача: 1360. Number of Days Between Two Dates
Сложность: easy

Напишите программу для подсчета количества дней между двумя датами.

Даты даны в виде строк в формате YYYY-MM-DD, как показано в примерах.

Пример:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

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

1⃣Преобразование строк в даты
Используйте встроенные функции для преобразования строковых представлений дат в объекты дат.

2⃣Вычисление разницы в днях
Вычислите разницу между двумя объектами дат в днях.

3⃣Возвращение результата
Верните абсолютное значение разницы в днях для получения положительного числа.

😎 Решение:

#include <iostream>
#include <string>
#include <cmath>
#include <ctime>

class Solution {
public:
    int daysBetweenDates(std::string date1, std::string date2) {
        std::tm tm1 = {}, tm2 = {};
        strptime(date1.c_str(), "%Y-%m-%d", &tm1);
        strptime(date2.c_str(), "%Y-%m-%d", &tm2);
        std::time_t time1 = std::mktime(&tm1);
        std::time_t time2 = std::mktime(&tm2);
        return std::abs((time2 - time1) / (60 * 60 * 24));
    }
};

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

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.

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

😎 Решение:

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int product = 1, count = 0, left = 0;
    for (int right = 0; right < nums.size(); right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

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

Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

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

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

2⃣Использование бинарного поиска:
Примените бинарный поиск в диапазоне от минимальной до максимальной грузоподъемности, чтобы найти наименьшую грузоподъемность, при которой все пакеты можно отправить за заданное количество дней.

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

😎 Решение:

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        auto canShipInDays = [&](int capacity) {
            int days = 1, total = 0;
            for (int weight : weights) {
                if (total + weight > capacity) {
                    days++;
                    total = 0;
                }
                total += weight;
            }
            return days <= D;
        };
        
        int left = *max_element(weights.begin(), weights.end());
        int right = accumulate(weights.begin(), weights.end(), 0);
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (canShipInDays(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

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

Задача: 1278. Palindrome Partitioning III
Сложность: hard

Вам дана строка s, содержащая строчные буквы, и целое число k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая подстрока была палиндромом. Верните минимальное количество символов, которое нужно изменить, чтобы разделить строку.

Пример:

Input: s = "abc", k = 2
Output: 1

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

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

2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений.

3⃣Верните минимальное количество изменений, найденное во втором шаге.

😎 Решение:

class Solution {
public:
    int minChangesToMakePalindrome(string s, int k) {
        int n = s.length();
        
        vector<vector<int>> dp1(n, vector<int>(n, 0));
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp1[i][j] = minChangeToPalindrome(s, i, j);
            }
        }

        vector<vector<int>> dp2(n + 1, vector<int>(k + 1, INT_MAX));
        dp2[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int kk = 1; kk <= k; kk++) {
                for (int j = 0; j < i; j++) {
                    dp2[i][kk] = min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1]);
                }
            }
        }

        return dp2[n][k];
    }

private:
    int minChangeToPalindrome(const string& s, int i, int j) {
        int changes = 0;
        while (i < j) {
            if (s[i] != s[j]) {
                changes++;
            }
            i++;
            j--;
        }
        return changes;
    }
};

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

class Solution {
public:
    int fixedPoint(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        int answer = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == mid) {
                answer = mid;
                right = mid - 1;
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
};

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

Задача: 894. All Possible Full Binary Trees
Сложность: medium

Учитывая целое число n, верните список всех возможных полных бинарных деревьев с узлами. Каждый узел каждого дерева в ответе должен иметь Node.val == 0. Каждый элемент ответа является корневым узлом одного возможного дерева. Вы можете вернуть конечный список деревьев в любом порядке. Полное бинарное дерево - это бинарное дерево, в котором каждый узел имеет ровно 0 или 2 дочерних.

Пример:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

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

1⃣Если n четное, вернуть пустой список, так как полное бинарное дерево не может иметь четное количество узлов.

2⃣Если n == 1, вернуть дерево с одним узлом. Для всех возможных значений i от 1 до n-1 с шагом 2: Создать левое поддерево с i узлами. Создать правое поддерево с n-1-i узлами. Объединить все комбинации левого и правого поддеревьев с новым корнем, добавив их в список результатов.

3⃣Вернуть список результатов.

😎 Решение:

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

class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        if (n % 2 == 0) return {};
        if (n == 1) return {new TreeNode(0)};
        
        vector<TreeNode*> result;
        for (int i = 1; i < n; i += 2) {
            vector<TreeNode*> leftTrees = allPossibleFBT(i);
            vector<TreeNode*> rightTrees = allPossibleFBT(n - 1 - i);
            for (auto left : leftTrees) {
                for (auto right : rightTrees) {
                    TreeNode* root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.push_back(root);
                }
            }
        }
        return result;
    }
};

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

Задача: 844. Backspace String Compare
Сложность: easy

Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.

Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.

Пример:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

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

1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы.

2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены.

3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false.

😎 Решение:

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S[i] == '#') { skipS++; i--; }
                else if (skipS > 0) { skipS--; i--; }
                else break;
            }
            while (j >= 0) {
                if (T[j] == '#') { skipT++; j--; }
                else if (skipT > 0) { skipT--; j--; }
                else break;
            }
            if (i >= 0 && j >= 0 && S[i] != T[j]) {
                return false;
            }
            if ((i >= 0) != (j >= 0)) {
                return false;
            }
            i--; j--;
        }
        return true;
    }
};

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