C/C++ | LeetCode

Задача: 23. Merge k Sorted Lists
Сложность: medium

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его.

Пример:

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

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

1⃣Создаем min-кучу, где приоритетом будет минимальное значение узлов.

2⃣Помещаем в кучу первые элементы всех непустых списков.

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

😎 Решение:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class compare {
public:
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;

        priority_queue<ListNode*, vector<ListNode*>, compare> minheap;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL)
                minheap.push(lists[i]);
        }

        ListNode* head = NULL;
        ListNode* temp1;

        while (!minheap.empty()) {
            ListNode* temp = minheap.top();
            minheap.pop();

            if (head == NULL) {
                head = temp;
                temp1 = temp;
            } else {
                temp1->next = temp;
                temp1 = temp;
            }

            if (temp->next != NULL) {
                minheap.push(temp->next);
            }
        }

        if (temp1 != NULL)
            temp1->next = NULL;

        return head;
    }
};

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

Задача: 1007. Minimum Domino Rotations For Equal Row
Сложность: medium

В ряду домино, tops[i] и bottoms[i] представляют собой верхнюю и нижнюю половинки i-го домино. (Домино - это плитка с двумя числами от 1 до 6 - по одному на каждой половине плитки.) Мы можем повернуть i-е домино так, чтобы tops[i] и bottoms[i] поменялись значениями. Верните минимальное количество поворотов, чтобы все значения tops были одинаковыми или все значения bottoms были одинаковыми. Если это невозможно сделать, верните -1.

Пример:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2

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

1⃣Проверка кандидатов:
Для начала рассмотрим два кандидата для достижения цели: tops[0] и bottoms[0]. Это кандидаты для унификации значений в ряду домино, поскольку если есть решение, один из этих двух кандидатов должен быть в верхней или нижней строке всех домино.

2⃣Подсчет поворотов для каждого кандидата:
Для каждого из кандидатов (tops[0] и bottoms[0]) подсчитайте количество поворотов, необходимых для унификации значений во всех tops или во всех bottoms.
Если какой-либо домино не может быть повернут для достижения требуемого кандидата, этот кандидат исключается из рассмотрения.

3⃣Возврат минимального количества поворотов:
Верните минимальное количество поворотов из всех возможных кандидатов. Если ни один кандидат не подходит, верните -1.

😎 Решение:

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        auto check = [&](int x) {
            int rotations_a = 0, rotations_b = 0;
            for (int i = 0; i < tops.size(); ++i) {
                if (tops[i] != x && bottoms[i] != x) {
                    return -1;
                } else if (tops[i] != x) {
                    rotations_a++;
                } else if (bottoms[i] != x) {
                    rotations_b++;
                }
            }
            return min(rotations_a, rotations_b);
        };
        
        int rotations = check(tops[0]);
        if (rotations != -1 || tops[0] == bottoms[0]) {
            return rotations;
        } else {
            return check(bottoms[0]);
        }
    }
};

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

Задача: 728. Self Dividing Numbers
Сложность: hard

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

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

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

😎 Решение:

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> result;
        for (int num = left; num <= right; num++) {
            if (isSelfDividing(num)) {
                result.push_back(num);
            }
        }
        return result;
    }

private:
    bool isSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
};

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

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

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

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

2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.

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

😎 Решение:

class Solution {
public:
    int maxLength(vector<string>& arr) {
        return backtrack(arr, 0, "");
    }

private:
    bool isUnique(const string& s) {
        unordered_set<char> char_set(s.begin(), s.end());
        return char_set.size() == s.size();
    }

    int backtrack(const vector<string>& arr, int index, const string& current) {
        if (!isUnique(current)) return 0;
        int max_length = current.size();
        for (int i = index; i < arr.size(); ++i) {
            max_length = max(max_length, backtrack(arr, i + 1, current + arr[i]));
        }
        return max_length;
    }
};

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

Задача: 89. Gray Code
Сложность: medium

Последовательность Грея длины n — это последовательность 2^n чисел от 0 до 2^n - 1,
в которой каждое следующее число отличается от предыдущего ровно на один бит,
и ни одно число не повторяется.

Пример:

Input: n = 2
Output: [0,1,3,2]
Пояснение: бинарный вид: [00, 01, 11, 10]

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

1⃣Начинаем с добавления 0 в результат — все коды Грея начинаются с нуля.

2⃣Используем DFS с backtracking:
перебираем числа, которые отличаются от текущего на один бит (используя current ^ (1 << i)).

3⃣Храним уже использованные числа в unordered_set, чтобы не добавлять повторения.
Если длина результата достигла 2^n, возвращаем true.
Иначе пробуем добавить подходящее следующее число. Если неудачно — откатываемся назад.

😎 Решение:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        unordered_set<int> isPresent;
        isPresent.insert(0);
        grayCodeHelper(result, n, isPresent);
        return result;
    }

private:
    bool grayCodeHelper(vector<int> &result, int n,
                        unordered_set<int> &isPresent) {
        if (result.size() == (1 << n)) return true;

        int current = result.back();
        for (int i = 0; i < n; i++) {
            int next = current ^ (1 << i);
            if (isPresent.find(next) == isPresent.end()) {
                result.push_back(next);
                isPresent.insert(next);
                if (grayCodeHelper(result, n, isPresent)) return true;
                isPresent.erase(next);
                result.pop_back();
            }
        }
        return false;
    }
};

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

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

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

Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: medium

Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold.

Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).

Гарантируется, что решение существует.

Пример:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

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

1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement.

2⃣Итерация по всем делителям от 1 до maxElement:
Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог.
Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums.

3⃣Проверьте, был ли превышен порог:
Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его.
Если не найдено возможного делителя, верните -1.

😎 Решение:

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int maxElement = *max_element(nums.begin(), nums.end());
        
        for (int divisor = 1; divisor <= maxElement; ++divisor) {
            int sumOfDivisionResults = 0;
            bool thresholdExceeded = true;
            
            for (int num : nums) {
                sumOfDivisionResults += (num + divisor - 1) / divisor;
                if (sumOfDivisionResults > threshold) {
                    thresholdExceeded = false;
                    break;
                }
            }
            
            if (thresholdExceeded) {
                return divisor;
            }
        }
        
        return -1;
    }
};

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

Задача: 1353. Maximum Number of Events That Can Be Attended
Сложность: medium

Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi.

Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d.

Верните максимальное количество событий, которые вы можете посетить.

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        set<int> visitedDays;
        int count = 0;
        
        for (const auto& event : events) {
            for (int day = event[0]; day <= event[1]; day++) {
                if (visitedDays.find(day) == visitedDays.end()) {
                    visitedDays.insert(day);
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};

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

Задача: 721. Accounts Merge
Сложность: medium

Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке.

Пример:

nput: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

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

1⃣Создайте граф, в котором узлы представляют email-адреса, а ребра соединяют email-адреса, принадлежащие одному аккаунту.

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

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

😎 Решение:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <algorithm>

using namespace std;

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, string> emailToName;
    unordered_map<string, unordered_set<string>> graph;

    
    for (auto& account : accounts) {
        string name = account[0];
        string firstEmail = account[1];
        for (int i = 1; i < account.size(); ++i) {
            string email = account[i];
            graph[firstEmail].insert(email);
            graph[email].insert(firstEmail);
            emailToName[email] = name;
        }
    }

    unordered_set<string> seen;
    vector<vector<string>> mergedAccounts;

   
    for (auto& [email, _] : emailToName) {
        if (seen.count(email) == 0) {
            vector<string> emails;
            stack<string> stk;
            stk.push(email);

            while (!stk.empty()) {
                string node = stk.top();
                stk.pop();
                if (seen.count(node) == 0) {
                    seen.insert(node);
                    emails.push_back(node);
                    for (auto& neighbor : graph[node]) {
                        if (!seen.count(neighbor)) {
                            stk.push(neighbor);
                        }
                    }
                }
            }

            sort(emails.begin(), emails.end());
            vector<string> account;
            account.push_back(emailToName[email]);
            account.insert(account.end(), emails.begin(), emails.end());
            mergedAccounts.push_back(account);
        }
    }

    return mergedAccounts;
}

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (!root) return true;

        queue<TreeNode*> q;
        q.push(root);
        bool nullNodeFound = false;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (!node) {
                nullNodeFound = true;
            } else {
                if (nullNodeFound) {
                    return false;
                }
                q.push(node->left);
                q.push(node->right);
            }
        }
        return true;
    }
};

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

Задача: 587. Erect the Fence
Сложность: hard

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.
Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.
Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке.

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

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

1⃣ Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

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

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

😎 Решение:

class Solution {
public:
    int orientation(vector<int>& p, vector<int>& q, vector<int>& r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](vector<int>& p, vector<int>& q) {
            return p[0] == q[0] ? p[1] < q[1] : p[0] < q[0];
        });

        vector<vector<int>> hull;

        for (auto& point : points) {
            while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), point) > 0)
                hull.pop_back();
            hull.push_back(point);
        }

        hull.pop_back();

        for (int i = points.size() - 1; i >= 0; --i) {
            while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) > 0)
                hull.pop_back();
            hull.push_back(points[i]);
        }

        set<vector<int>> s(hull.begin(), hull.end());
        return vector<vector<int>>(s.begin(), s.end());
    }
};

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

Задача: 364. Nested List Weight Sum II
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками.

Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.

Верните сумму каждого целого числа в nestedList, умноженную на его вес.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

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

class NestedInteger {
public:
    bool isInteger() const;
    int getInteger() const;
    const vector<NestedInteger> &getList() const;
};

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        queue<NestedInteger> q;
        for (auto& ni : nestedList) q.push(ni);

        int depth = 1, maxDepth = 0, sumOfElements = 0, sumOfProducts = 0;

        while (!q.empty()) {
            int size = q.size();
            maxDepth = max(maxDepth, depth);

            for (int i = 0; i < size; ++i) {
                NestedInteger nested = q.front();
                q.pop();

                if (nested.isInteger()) {
                    int value = nested.getInteger();
                    sumOfElements += value;
                    sumOfProducts += value * depth;
                } else {
                    for (auto& ni : nested.getList()) q.push(ni);
                }
            }
            depth++;
        }
        return (maxDepth + 1) * sumOfElements - sumOfProducts;
    }
};

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

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

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

Задача: 473. Matchsticks to Square
Сложность: medium

Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.
Вернуть true, если можно составить квадрат, и false в противном случае.

Пример:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

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

1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.

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

3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.

😎 Решение:

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> nums;
    std::vector<int> sums;
    int possibleSquareSide;

    Solution() : sums(4, 0) {}

    bool dfs(int index) {
        if (index == nums.size()) {
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
        }

        int element = nums[index];

        for (int i = 0; i < 4; ++i) {
            if (sums[i] + element <= possibleSquareSide) {
                sums[i] += element;
                if (dfs(index + 1)) {
                    return true;
                }
                sums[i] -= element;
            }
        }

        return false;
    }

    bool makesquare(std::vector<int>& nums) {
        if (nums.empty()) {
            return false;
        }

        int perimeter = std::accumulate(nums.begin(), nums.end(), 0);
        possibleSquareSide = perimeter / 4;
        if (possibleSquareSide * 4 != perimeter) {
            return false;
        }

        std::sort(nums.rbegin(), nums.rend());
        this->nums = nums;
        return dfs(0);
    }
};

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

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j.

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

class Solution {
public:
    int numPermsDISequence(string s) {
        const int MOD = 1e9 + 7;
        int n = s.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[i - 1] == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[n][j]) % MOD;
        }
        
        return result;
    }
};

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

Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

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

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        return containsOne(root) ? root : nullptr;
    }

private:
    bool containsOne(TreeNode* node) {
        if (!node) return false;

        bool leftContainsOne = containsOne(node->left);
        bool rightContainsOne = containsOne(node->right);

        if (!leftContainsOne) node->left = nullptr;
        if (!rightContainsOne) node->right = nullptr;

        return node->val == 1 || leftContainsOne || rightContainsOne;
    }
};

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

Задача: 404. Sum of Left Leaves
Сложность: easy

Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла.

Пример:

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

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

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

2⃣Проверка листьев
Если текущий узел является листом и флаг указывает, что это левый ребенок, добавьте значение узла к сумме.

3⃣Рекурсивный вызов для детей
Рекурсивно вызовите функцию для левого и правого детей текущего узла, передавая соответствующий флаг.

😎 Решение:

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        return dfs(root, false);
    }
    
private:
    int dfs(TreeNode* node, bool isLeft) {
        if (!node) return 0;
        if (!node->left && !node->right) return isLeft ? node->val : 0;
        return dfs(node->left, true) + dfs(node->right, false);
    }
};

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

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.
Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.
Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

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

😎 Решение:

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> pairs;
        
        for (int i = 0; i < words.size(); ++i) {
            for (int j = 0; j < words.size(); ++j) {
                if (i == j) continue;
                string combined = words[i] + words[j];
                string reversed = string(combined.rbegin(), combined.rend());
                if (combined == reversed) {
                    pairs.push_back({i, j});
                }
            }
        }
        
        return pairs;
    }
};

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        vector<tuple<int, int, int>> pairs;
        
        for (int i = 0; i < workers.size(); i++) {
            for (int j = 0; j < bikes.size(); j++) {
                int distance = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                pairs.emplace_back(distance, i, j);
            }
        }
        
        sort(pairs.begin(), pairs.end());
        
        vector<int> result(workers.size(), -1);
        vector<bool> bikeTaken(bikes.size(), false);
        vector<bool> workerAssigned(workers.size(), false);
        
        for (auto& [distance, workerIdx, bikeIdx] : pairs) {
            if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
                result[workerIdx] = bikeIdx;
                bikeTaken[bikeIdx] = true;
                workerAssigned[workerIdx] = true;
            }
        }
        
        return result;
    }
};

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Реализуйте структуру данных Trie (префиксное дерево), поддерживающую следующие операции:
insert(word) — вставка слова
search(word) — проверка, было ли слово вставлено
startsWith(prefix) — проверка, начинается ли хоть одно вставленное слово с заданного префикса

Пример:

Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, true, false, true, null, true]

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

1⃣Инициализация и вставка:
Каждый узел (TrieNode) содержит массив из 26 указателей (по одной на каждую букву алфавита) и флаг isEnd.
Метод insert создает недостающие узлы и в конце устанавливает isEnd = true для последнего символа слова.

2⃣Поиск строки:
Метод search использует вспомогательную функцию searchPrefix, которая проходит по всем символам слова. Если найденный узел существует и отмечен как конец слова, возвращаем true.

3⃣Проверка префикса:
Метод startsWith использует searchPrefix, и возвращает true, если удалось дойти до конца заданного префикса.

😎 Решение:

#include <vector>
#include <string>

class TrieNode {
private:
    TrieNode* links[26];
    bool isEnd;

public:
    TrieNode() : isEnd(false) {
        for (int i = 0; i < 26; ++i) {
            links[i] = nullptr;
        }
    }

    bool containsKey(char ch) {
        return links[ch - 'a'] != nullptr;
    }

    TrieNode* get(char ch) {
        return links[ch - 'a'];
    }

    void put(char ch, TrieNode* node) {
        links[ch - 'a'] = node;
    }

    void setEnd() {
        isEnd = true;
    }

    bool isEndNode() {
        return isEnd;
    }
};

class Trie {
private:
    TrieNode* root;

    TrieNode* searchPrefix(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->containsKey(ch)) {
                node = node->get(ch);
            } else {
                return nullptr;
            }
        }
        return node;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->containsKey(ch)) {
                node->put(ch, new TrieNode());
            }
            node = node->get(ch);
        }
        node->setEnd();
    }

    bool search(const std::string& word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isEndNode();
    }

    bool startsWith(const std::string& prefix) {
        return searchPrefix(prefix) != nullptr;
    }
};

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