#medium
Задача: 623. Add One Row to Tree

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

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

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

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

😎 Решение:

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

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

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (depth == 1) {
            TreeNode* newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        int currentDepth = 1;
        
        while (!q.empty()) {
            if (currentDepth == depth - 1) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    TreeNode* node = q.front();
                    q.pop();
                    TreeNode* tempLeft = node->left;
                    TreeNode* tempRight = node->right;
                    node->left = new TreeNode(val);
                    node->left->left = tempLeft;
                    node->right = new TreeNode(val);
                    node->right->right = tempRight;
                }
                break;
            }
            currentDepth++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return root;
    }
};

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

#medium
Задача: 624. Maximum Distance in Arrays

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

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

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

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

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

using namespace std;

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int minVal = arrays[0][0];
        int maxVal = arrays[0].back();
        int maxDistance = 0;
        
        for (int i = 1; i < arrays.size(); i++) {
            maxDistance = max(maxDistance, abs(arrays[i].back() - minVal), abs(arrays[i][0] - maxVal));
            minVal = min(minVal, arrays[i][0]);
            maxVal = max(maxVal, arrays[i].back());
        }
        
        return maxDistance;
    }
};

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

#medium
Задача: 625. Minimum Factorization

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.

😎 Решение:

class Solution {
public:
    int smallestFactorization(int num) {
        if (num == 1) return 1;
        
        vector<int> factors;
        
        for (int i = 9; i >= 2; i--) {
            while (num % i == 0) {
                factors.push_back(i);
                num /= i;
            }
        }
        
        if (num > 1) return 0;
        
        long result = 0;
        for (int i = factors.size() - 1; i >= 0; i--) {
            result = result * 10 + factors[i];
            if (result > INT_MAX) return 0;
        }
        
        return (int) result;
    }
};

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

#easy
Задача: 628. Maximum Product of Three Numbers

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

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

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

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

3⃣Верните максимальное из двух найденных произведений.

😎 Решение:

using namespace std;

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int max1 = nums[n - 1] * nums[n - 2] * nums[n - 3];
        int max2 = nums[0] * nums[1] * nums[n - 1];
        return max(max1, max2);
    }
};

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

#hard
Задача: 629. K Inverse Pairs Array

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1000000007;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                if (j >= i) {
                    dp[i][j] -= dp[i - 1][j - i];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }

        return dp[n][k];
    }
};

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

#hard
Задача: 630. Course Schedule III

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

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

1⃣Сортировка курсов
Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.

2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

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

😎 Решение:

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        priority_queue<int> maxHeap;
        int time = 0;

        for (const auto& course : courses) {
            time += course[0];
            maxHeap.push(course[0]);
            if (time > course[1]) {
                time -= maxHeap.top();
                maxHeap.pop();
            }
        }

        return maxHeap.size();
    }
};

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

#easy
Задача: 434. Number of Segments in a String

Дана строка s, верните количество сегментов в строке.

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

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

class Solution {
public:
    int countSegments(string s) {
        int segmentCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if ((i == 0 || s[i-1] == ' ') && s[i] != ' ') {
                segmentCount++;
            }
        }

        return segmentCount;
    }
};

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

#hard
Задача: 354. Russian Doll Envelopes

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for (int num : nums) {
            auto it = lower_bound(dp.begin(), dp.end(), num);
            if (it != dp.end()) {
                *it = num;
            } else {
                dp.push_back(num);
            }
        }
        return dp.size();
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];
        });
        vector<int> secondDim;
        for (const auto& envelope : envelopes) {
            secondDim.push_back(envelope[1]);
        }
        return lengthOfLIS(secondDim);
    }
};

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

#hard
Задача: 631. Design Excel Sum Formula

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

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

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

😎 Решение:

class Excel {
private:
    vector<vector<int>> mat;
    unordered_map<string, vector<string>> formulas;

public:
    Excel(int height, char width) {
        mat.resize(height, vector<int>(width - 'A' + 1, 0));
    }

    void set(int row, char column, int val) {
        mat[row - 1][column - 'A'] = val;
        formulas.erase(to_string(row) + column);
    }

    int get(int row, char column) {
        string key = to_string(row) + column;
        if (formulas.count(key)) {
            return evaluateFormula(key);
        }
        return mat[row - 1][column - 'A'];
    }

    int sum(int row, char column, vector<string> numbers) {
        string key = to_string(row) + column;
        formulas[key] = numbers;
        return evaluateFormula(key);
    }

    int evaluateFormula(const string& key) {
        int total = 0;
        for (const string& number : formulas[key]) {
            if (number.find(':') != string::npos) {
                auto pos = number.find(':');
                string start = number.substr(0, pos);
                string end = number.substr(pos + 1);
                int startRow = stoi(start.substr(1));
                char startCol = start[0];
                int endRow = stoi(end.substr(1));
                char endCol = end[0];
                for (int r = startRow; r <= endRow; r++) {
                    for (char c = startCol; c <= endCol; c++) {
                        total += get(r, c);
                    }
                }
            } else {
                int r = stoi(number.substr(1));
                char c = number[0];
                total += get(r, c);
            }
        }
        return total;
    }
};

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

#medium
Задача: 435. Non-overlapping Intervals

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

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

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int ans = 0;
        int k = INT_MIN;
        
        for (const auto& interval : intervals) {
            int x = interval[0];
            int y = interval[1];
            if (x >= k) {
                k = y;
            } else {
                ans++;
            }
        }
        
        return ans;
    }
};

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

#hard
Задача: 358. Rearrange String k Distance Apart

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

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    string rearrangeString(string s, int k) {
        unordered_map<char, int> freqs;
        int maxFreq = 0;
        
        for (char c : s) {
            freqs[c]++;
            maxFreq = max(maxFreq, freqs[c]);
        }
        
        unordered_set<char> mostChars, secondChars;
        
        for (auto& [c, freq] : freqs) {
            if (freq == maxFreq) {
                mostChars.insert(c);
            } else if (freq == maxFreq - 1) {
                secondChars.insert(c);
            }
        }
        
        vector<string> segments(maxFreq);
        
        for (int i = 0; i < maxFreq; ++i) {
            for (char c : mostChars) {
                segments[i] += c;
            }
            if (i < maxFreq - 1) {
                for (char c : secondChars) {
                    segments[i] += c;
                }
            }
        }
        
        int segmentId = 0;
        
        for (auto& [c, freq] : freqs) {
            if (mostChars.count(c) || secondChars.count(c)) {
                continue;
            }
            
            while (freq--) {
                segments[segmentId] += c;
                segmentId = (segmentId + 1) % (maxFreq - 1);
            }
        }
        
        for (int i = 0; i < maxFreq - 1; ++i) {
            if (segments[i].size() < k) {
                return "";
            }
        }
        
        string result;
        for (auto& segment : segments) {
            result += segment;
        }
        
        return result;
    }
};

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

#easy
Задача: 559. Maximum Depth of N-ary Tree

Дано n-арное дерево, найдите его максимальную глубину.

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.

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

Пример:

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

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

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

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину.

😎 Решение:

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) {
            return 0;
        } else if (root->children.empty()) {
            return 1;
        } else {
            vector<int> heights;
            for (Node* child : root->children) {
                heights.push_back(maxDepth(child));
            }
            return *max_element(heights.begin(), heights.end()) + 1;
        }
    }
};

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

Задача: 560. Subarray Sum Equals K

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

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

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k.

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

😎 Решение:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.size(); start++) {
            for (int end = start + 1; end <= nums.size(); end++) {
                int sum = 0;
                for (int i = start; i < end; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
};

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

#easy
Задача: 561. Array Partition

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            sum += nums[i];
        }
        return sum;
    }
};

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

📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv

easyoffer
Backend

Python | Вопросы
Python | Удалёнка
Python | LeetCode
Python | Тесты

Frontend | Вопросы
Frontend | Удалёнка
JavaScript | LeetCode
Frontend | Тесты

Java | Вопросы
Java | Удалёнка
Java | LeetCode
Java | Тесты

Тестировщик | Вопросы
Тестировщик | Удалёнка
Тестировщик | Тесты

Data Science | Вопросы
Data Science | Удалёнка
Data Science | Тесты

C# | Вопросы
C# | Удалёнка
C# | LeetCode
C# | Тесты

C/C++ | Вопросы
C/C++ | Удалёнка
C/C++ | LeetCode
C/C++ | Тесты

Golang | Вопросы
Golang | Удалёнка
Golang | LeetCode
Golang | Тесты

DevOps | Вопросы
DevOps | Удалёнка
DevOps | Тесты

PHP | Вопросы
PHP | Удалёнка
PHP | LeetCode
PHP | Тесты

Kotlin | Вопросы
Kotlin | Удалёнка
Kotlin | LeetCode
Kotlin | Тесты

Swift | Вопросы
Swift | Удалёнка
Swift | LeetCode
Swift | Тесты

📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv

#medium
Задача: 562. Longest Line of Consecutive One in Matrix

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

class Solution {
public:
    int longestLine(vector<vector<int>>& mat) {
        if (mat.empty() || mat[0].empty()) return 0;
        
        int m = mat.size();
        int n = mat[0].size();
        int maxLength = 0;
        
        vector<vector<int>> horizontal(m, vector<int>(n, 0));
        vector<vector<int>> vertical(m, vector<int>(n, 0));
        vector<vector<int>> diagonal(m, vector<int>(n, 0));
        vector<vector<int>> antiDiagonal(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    horizontal[i][j] = (j > 0 ? horizontal[i][j-1] : 0) + 1;
                    vertical[i][j] = (i > 0 ? vertical[i-1][j] : 0) + 1;
                    diagonal[i][j] = (i > 0 && j > 0 ? diagonal[i-1][j-1] : 0) + 1;
                    antiDiagonal[i][j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1][j+1] : 0) + 1;
                    
                    maxLength = max(maxLength, horizontal[i][j]);
                    maxLength = max(maxLength, vertical[i][j]);
                    maxLength = max(maxLength, diagonal[i][j]);
                    maxLength = max(maxLength, antiDiagonal[i][j]);
                }
            }
        }
        
        return maxLength;
    }
};

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

#easy
Задача: 563. Binary Tree Tilt

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

Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

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

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

3⃣Верните общую сумму наклонов всех узлов.

😎 Решение:

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

class Solution {
public:
    int findTilt(TreeNode* root) {
        int totalTilt = 0;
        
        function<int(TreeNode*)> sumAndTilt = [&](TreeNode* node) -> int {
            if (node == nullptr) {
                return 0;
            }
            int leftSum = sumAndTilt(node->left);
            int rightSum = sumAndTilt(node->right);
            int nodeTilt = abs(leftSum - rightSum);
            totalTilt += nodeTilt;
            return node->val + leftSum + rightSum;
        };
        
        sumAndTilt(root);
        return totalTilt;
    }
};

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

#medium
Задача: 565. Array Nesting

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

Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:

Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.

Верните длину самого длинного множества s[k].

Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

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

1⃣Создайте массив для отслеживания посещенных элементов.

2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.

3⃣Обновите максимальную длину найденного множества.

😎 Решение:

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        int maxLength = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = max(maxLength, count);
            }
        }
        
        return maxLength;
    }
};

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

#medium
Задача: 669. Trim a Binary Search Tree

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

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

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

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

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

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

#medium
Задача: 309. Best Time to Buy and Sell Stock with Cooldown

Дан массив prices, где prices[i] — цена данной акции в i-й день.

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

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

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

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

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.size(); i++) {
            int newHold = max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return max(sold, cooldown);
    }
};

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