C/C++ | LeetCode

Задача: 283. Move Zeroes
Сложность: easy

Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.

Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.

Пример:

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

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

1⃣Инициализация указателей:
Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву.

2⃣Итерация и обмен элементами:
Итерируйтесь по массиву с помощью указателя cur.
Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt.

3⃣Завершение итерации:
Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов.

😎 Решение:

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

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

Задача: 870. Advantage Shuffle
Сложность: medium

Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].

Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.

Пример:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

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

1⃣Отсортируйте nums1 и nums2. Для каждой карты a из отсортированного nums1 определите, может ли она побить текущую наименьшую карту b из отсортированного nums2. Если да, добавьте a в assigned[b], если нет, добавьте a в remaining.

2⃣После распределения всех карт из nums1, используйте assigned и remaining для построения итогового результата. Для каждой карты b из nums2, если assigned[b] не пуст, добавьте в результат последнюю карту из assigned[b], иначе добавьте последнюю карту из remaining.

3⃣Верните итоговый результат.

😎 Решение:

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> sortedA(A);
        sort(sortedA.begin(), sortedA.end());
        vector<pair<int, int>> sortedB;
        for (int i = 0; i < B.size(); ++i)
            sortedB.push_back({B[i], i});
        sort(sortedB.begin(), sortedB.end());

        unordered_map<int, deque<int>> assigned;
        for (int b: B) assigned[b] = {};

        deque<int> remaining;
        int j = 0;
        for (int a: sortedA) {
            if (a > sortedB[j].first) {
                assigned[sortedB[j++].first].push_back(a);
            } else {
                remaining.push_back(a);
            }
        }

        vector<int> ans(B.size());
        for (int i = 0; i < B.size(); ++i) {
            if (assigned[B[i]].size() > 0) {
                ans[i] = assigned[B[i]].front();
                assigned[B[i]].pop_front();
            } else {
                ans[i] = remaining.front();
                remaining.pop_front();
            }
        }
        return ans;
    }
};

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

Задача: 775. Global and Local Inversions
Сложность: medium

Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].

Число глобальных инверсий — это количество различных пар (i, j), где:

0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:

0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.

Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

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

1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.

2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.

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

😎 Решение:

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int N = A.size();
        for (int i = 0; i < N; ++i)
            for (int j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
};

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

Задача: 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);
    }
};

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

Задача: 541. Reverse String II
Сложность: easy

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
public:
    string reverseStr(string s, int k) {
        vector<char> a(s.begin(), s.end());
        for (int start = 0; start < a.size(); start += 2 * k) {
            int i = start, j = min(start + k - 1, (int)a.size() - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return string(a.begin(), a.end());
    }
};

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        if (k > 26) return 0;
        
        int answer = 0;
        int n = s.size();
        
        for (int i = 0; i <= n - k; i++) {
            int freq[26] = {0};
            bool isUnique = true;
            
            for (int j = i; j < i + k; j++) {
                freq[s[j] - 'a']++;
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false;
                    break;
                }
            }
            
            if (isUnique) answer++;
        }
        
        return answer;
    }
};

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

Задача: 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;
    }
};

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

Задача: 1094. Car Pooling
Сложность: medium

Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).

Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.

Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.

Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity.

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

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

😎 Решение:

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> timestamp;
        for (auto& trip : trips) {
            timestamp[trip[1]] += trip[0];
            timestamp[trip[2]] -= trip[0];
        }
        int usedCapacity = 0;
        for (auto& change : timestamp) {
            usedCapacity += change.second;
            if (usedCapacity > capacity) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 1260. Shift 2D Grid
Сложность: easy

Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.

Пример:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

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

1⃣Преобразовать двумерную сетку в одномерный массив.

2⃣Выполнить сдвиг элементов в одномерном массиве.

3⃣Преобразовать одномерный массив обратно в двумерную сетку.

😎 Решение:

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int total = m * n;
        k = k % total;

        if (k == 0) {
            return grid;
        }

        vector<int> flatArray(total);
        for (int i = 0; i < total; ++i) {
            flatArray[i] = grid[i / n][i % n];
        }

        vector<int> newArray(total);
        for (int i = 0; i < total; ++i) {
            newArray[(i + k) % total] = flatArray[i];
        }

        vector<vector<int>> newGrid(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                newGrid[i][j] = newArray[i * n + j];
            }
        }

        return newGrid;
    }
};

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

Задача: №30. Substring with Concatenation of All Words
Сложность: hard

Вам дана строка s и массив строк words, где все слова одинаковой длины. Найдите все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке, без дополнительных символов между ними).

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]

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

1⃣Вычисляем длину каждого слова и общее количество слов.

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

3⃣Отслеживаем, сколько раз каждое слово встречается, используя unordered_map.

😎 Решение:

vector<int> findSubstring(string str, vector<string>& words) {
    int len = words[0].length();
    unordered_map<string, int> contain;
    for (string s : words) contain[s]++;
    
    vector<int> res;
    for (int j = 0; j < len; j++) {
        unordered_map<string, int> found;
        int st = j;
        for (int i = j; i <= str.size() - len; i += len) {
            string curr = str.substr(i, len);
            if (contain.find(curr) != contain.end()) {
                found[curr]++;
                while (found[curr] > contain[curr]) {
                    found[str.substr(st, len)]--;
                    st += len;
                }
                int size = (i - st + len) / len;
                if (size == words.size()) {
                    res.push_back(st);
                }
            } else {
                found.clear();
                st = i + len;
            }
        }
    }
    return res;
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

#include <algorithm>

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

class Solution {
public:
    int maxLength = 0;

    int longestZigZag(TreeNode* root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return maxLength;
    }

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

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

Задача: 347. Top K Frequent Elements
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.

Пример:

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

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

1⃣Подсчет частоты:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums.

2⃣Создание кучи:
Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов.

3⃣Возврат результата:
Верните k самых частых элементов.

😎 Решение:

#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        priority_queue<pair<int, int>> heap;
        for (const auto& [num, freq] : count) {
            heap.emplace(freq, num);
        }
        vector<int> result;
        for (int i = 0; i < k; ++i) {
            result.push_back(heap.top().second);
            heap.pop();
        }
        return result;
    }
};

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

Задача: 763. Partition Labels
Сложность: medium

Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.

Пример:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

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

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

2⃣Пройдите по строке, отслеживая максимальную позицию текущей части.

3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.

😎 Решение:

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> lastPos(26, 0);
        for (int i = 0; i < s.size(); i++) {
            lastPos[s[i] - 'a'] = i;
        }
        
        vector<int> partitions;
        int j = 0, anchor = 0;
        for (int i = 0; i < s.size(); i++) {
            j = max(j, lastPos[s[i] - 'a']);
            if (i == j) {
                partitions.push_back(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return partitions;
    }
};

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

Задача: 267. Palindrome Permutation II
Сложность: medium

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

1⃣Подсчёт частоты символов
Создаем хеш-таблицу частот. Если количество символов с нечетной частотой больше 1 — палиндром невозможен.

2⃣Формирование первой половины
Из каждого символа берём его частоту пополам и формируем строку half. Символ с нечетной частотой (если есть) сохраняем как центральный.

3⃣Генерация палиндромов
С помощью backtracking создаём все уникальные перестановки строки half, дополняем их зеркально. Если есть центральный символ — добавляем его в середину.

😎 Решение:

class Solution {
private:
    void backtrack(string& half, vector<bool>& used, string& path, string& mid, vector<string>& res) {
        if (path.size() == half.size()) {
            string rev = path;
            reverse(rev.begin(), rev.end());
            res.push_back(path + mid + rev);
            return;
        }

        for (int i = 0; i < half.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(half[i]);
            backtrack(half, used, path, mid, res);
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;

        int oddCount = 0;
        string mid = "", half = "";
        for (auto& [ch, count] : freq) {
            if (count % 2 != 0) {
                oddCount++;
                mid = ch;
            }
            half += string(count / 2, ch);
        }

        if (oddCount > 1) return {};

        sort(half.begin(), half.end());
        vector<string> res;
        vector<bool> used(half.size(), false);
        string path;
        backtrack(half, used, path, mid, res);
        return res;
    }
};

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

Задача: 681. Next Closest Time
Сложность: medium

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

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

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

2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎 Решение:

class Solution {
public:
    string nextClosestTime(string time) {
        int cur = 60 * stoi(time.substr(0, 2)) + stoi(time.substr(3));
        unordered_set<int> allowed;
        for (char c : time) if (c != ':') {
            allowed.insert(c - '0');
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            vector<int> digits = {cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
            bool valid = true;
            for (int d : digits) {
                if (!allowed.count(d)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return (cur / 60 < 10 ? "0" : "") + to_string(cur / 60) + ":" + (cur % 60 < 10 ? "0" : "") + to_string(cur % 60);
            }
        }
    }
};

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

Задача: 1490. Clone N-ary Tree
Сложность: medium

Дан корень N-арного дерева, верните глубокую копию (клон) дерева.
Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей.

class Node {
    public int val;
    public List<Node> children;
}

Сериализация входных данных N-арного дерева представлена в порядке обхода по уровням, каждая группа детей разделена значением null (см. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

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

1⃣Базовый случай:
Проверить, является ли входной узел null. Если да, вернуть null.

2⃣Копирование узла:
Создать новый узел с таким же значением, как у входного узла.

3⃣Рекурсивное клонирование детей:
Рекурсивно клонировать каждого ребёнка входного узла и добавить клонированных детей в список детей нового узла.
Вернуть клонированный узел.

😎 Решение:

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    Node* cloneTree(Node* root) {
        if (!root) return nullptr;

        Node* nodeCopy = new Node(root->val);
        for (Node* child : root->children) {
            nodeCopy->children.push_back(cloneTree(child));
        }
        return nodeCopy;
    }
};

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

Задача: 400. Nth Digit
Сложность: medium

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

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

1⃣Определение диапазона:
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа:
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры:
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

class Solution {
public:
    int findNthDigit(int n) {
        long length = 1, count = 9, start = 1;
        while (n > length * count) {
            n -= length * count;
            length++;
            count *= 10;
            start *= 10;
        }
        start += (n - 1) / length;
        string s = to_string(start);
        return s[(n - 1) % length] - '0';
    }
};

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int shiftAndCount(int xShift, int yShift, vector<vector<int>>& M, vector<vector<int>>& R) {
        int leftShiftCount = 0, rightShiftCount = 0;
        int rRow = 0;
        for (int mRow = yShift; mRow < M.size(); ++mRow) {
            int rCol = 0;
            for (int mCol = xShift; mCol < M.size(); ++mCol) {
                if (M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol])
                    leftShiftCount++;
                if (M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol])
                    rightShiftCount++;
                rCol++;
            }
            rRow++;
        }
        return max(leftShiftCount, rightShiftCount);
    }

    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        int maxOverlaps = 0;
        for (int yShift = 0; yShift < A.size(); ++yShift) {
            for (int xShift = 0; xShift < A.size(); ++xShift) {
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B));
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A));
            }
        }
        return maxOverlaps;
    }
};

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

class Solution {
public:
    int tilingRectangle(int n, int m) {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        for (int i = 1; i <= min(n, m); ++i) {
            dp[i][i] = 1;
        }
        
        for (int h = 1; h <= n; ++h) {
            for (int w = 1; w <= m; ++w) {
                if (h == w) continue;
                for (int i = 1; i <= h / 2; ++i) {
                    dp[h][w] = min(dp[h][w], dp[i][w] + dp[h - i][w]);
                }
                for (int j = 1; j <= w / 2; ++j) {
                    dp[h][w] = min(dp[h][w], dp[h][j] + dp[h][w - j]);
                }
            }
        }
        return dp[n][m];
    }
};

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

Задача: 1032. Stream of Characters
Сложность: hard

Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.

Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.

Пример:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

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

1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.

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

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class TrieNode {
public:
    TrieNode* children[26] = {};
    bool is_end_of_word = false;
};

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (int i = word.size() - 1; i >= 0; --i) {
                if (!node->children[word[i] - 'a']) {
                    node->children[word[i] - 'a'] = new TrieNode();
                }
                node = node->children[word[i] - 'a'];
            }
            node->is_end_of_word = true;
        }
    }
    
    bool query(char letter) {
        stream.push_front(letter);
        TrieNode* node = root;
        for (char c : stream) {
            if (!node->children[c - 'a']) return false;
            node = node->children[c - 'a'];
            if (node->is_end_of_word) return true;
        }
        return false;
    }

private:
    TrieNode* root;
    deque<char> stream;
};

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