Задача: 1470. Shuffle the Array
Сложность: easy

Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].

Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].

Пример:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

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

1⃣Создайте массив result размером 2 * n.

2⃣Итеративно пройдите по массиву nums от 0 до n - 1:
Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result.
Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result.

3⃣Верните массив result.

😎 Решение:

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> result(2 * n);
        for (int i = 0; i < n; ++i) {
            result[2 * i] = nums[i];
            result[2 * i + 1] = nums[n + i];
        }
        return result;
    }
};

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

Задача: 128. Longest Consecutive Sequence
Сложность: medium

Найти длину самой длинной последовательности последовательных чисел в неотсортированном массиве. Время работы — O(n).

Пример:

Input: [100,4,200,1,3,2] → Output: 4

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

1⃣Помещаем все числа в unordered_set, чтобы можно было быстро проверять наличие элемента (O(1) время доступа).

2⃣Проходим по каждому числу, и если num - 1 не существует в сете — это начало новой последовательности. Затем увеличиваем currentNum, пока currentNum + 1 есть в сете, считая длину последовательности.

3⃣После проверки каждого числа обновляем longestStreak, если текущая последовательность длиннее.

😎 Решение:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

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

Задача: 755. Pour Water
Сложность: medium

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

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

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

😎 Решение:

class Solution {
public:
    vector<int> pourWater(vector<int>& heights, int volume, int k) {
        for (int v = 0; v < volume; v++) {
            int dropIndex = k;
            for (int d : {-1, 1}) {
                int i = k;
                while (i + d >= 0 && i + d < heights.size() && heights[i + d] <= heights[i]) {
                    if (heights[i + d] < heights[i]) {
                        dropIndex = i + d;
                    }
                    i += d;
                }
                if (dropIndex != k) {
                    break;
                }
            }
            heights[dropIndex]++;
        }
        return heights;
    }
};

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

Задача: 765. Couples Holding Hands
Сложность: hard

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

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.

😎 Решение:

class Solution {
public:
    int N;
    vector<vector<int>> pairs;

    int minSwapsCouples(vector<int>& row) {
        N = row.size() / 2;
        pairs.resize(N, vector<int>(2));
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return min(ans1, ans2);
    }
};

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

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

😎 Решение:

class WordFilter {
public:
    WordFilter(vector<string>& words) {
        for (int index = 0; index < words.size(); ++index) {
            string word = words[index];
            int length = word.length();
            for (int prefixLength = 1; prefixLength <= length; ++prefixLength) {
                for (int suffixLength = 1; suffixLength <= length; ++suffixLength) {
                    string prefix = word.substr(0, prefixLength);
                    string suffix = word.substr(length - suffixLength);
                    string key = prefix + "#" + suffix;
                    prefixSuffixMap[key] = index;
                }
            }
        }
    }
    
    int f(string pref, string suff) {
        string key = pref + "#" + suff;
        return prefixSuffixMap.count(key) ? prefixSuffixMap[key] : -1;
    }

private:
    unordered_map<string, int> prefixSuffixMap;
};

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

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Сложность: hard

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

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

Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1.
Нулевая матрица - это матрица, в которой все ячейки равны 0.

Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

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

1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой.

2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed:
Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1.
Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке.

3⃣После обработки всех строк проверьте, содержит ли lastState все нули, чтобы определить, является ли это допустимым решением. Верните минимальное количество переворотов для всех допустимых решений.

😎 Решение:

class Solution {
    int better(int x, int y) {
        return x < 0 || (y >= 0 && y < x) ? y : x;
    }

    int dfs(const vector<vector<int>>& mat, vector<int>& operations) {
        if (operations.size() == mat[0].size()) {
            vector<int> changed(mat[0].size());
            vector<int> last_state = operations;
            int maybe = 0;
            for (const vector<int>& row : mat) {
                vector<int> state = changed;
                for (int j = 0; j < row.size(); ++j) {
                    state[j] ^= row[j];
                    if (last_state[j]) {
                        state[j] ^= 1;
                        if (j) {
                            state[j - 1] ^= 1;
                        }
                        if (j + 1 < row.size()) {
                            state[j + 1] ^= 1;
                        }
                        ++maybe;
                    }
                }
                changed = last_state;
                last_state = state;
            }
            for (int x : last_state) {
                if (x) {
                    return -1;
                }
            }
            return maybe;
        }
        operations.push_back(0);
        const int maybe1 = dfs(mat, operations);
        operations.back() = 1;
        const int maybe2 = dfs(mat, operations);
        operations.pop_back();
        return better(maybe1, maybe2);
    }

public:
    int minFlips(vector<vector<int>>& mat) {
        vector<int> operations;
        return dfs(mat, operations);
    }
};

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> addToArrayForm(std::vector<int>& num, int k) {
        std::vector<int> result;
        int n = num.size();
        
        for (int i = n - 1; i >= 0; i--) {
            k += num[i];
            result.push_back(k % 10);
            k /= 10;
        }
        while (k > 0) {
            result.push_back(k % 10);
            k /= 10;
        }
        std::reverse(result.begin(), result.end());
        return result;
    }
};

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

Задача: 92. Reverse Linked List II
Сложность: medium

Дан односвязный список и два числа left и right.
Нужно перевернуть часть списка от позиции left до right (включительно)
и вернуть изменённый список, сохранив остальные узлы нетронутыми.

Пример:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

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

1⃣Запускаем рекурсивную функцию recurseAndReverse, передавая указатель right (начинается с head), а также значения m и n — относительные позиции для переворота.

2⃣Перед каждым рекурсивным вызовом сдвигаем right = right->next,
и если m > 1, то сдвигаем left = left->next.
Таким образом, когда n == 1, left указывает на начало, а right — на конец подсписка.

3⃣Во время отката рекурсии — обмениваем значения в left и right,
затем двигаем left = left->next.
Останавливаем обмены, если указатели пересеклись (left == right) или пересекаются (right->next == left).

😎 Решение:

class Solution {
public:
    ListNode* left = nullptr;
    bool stop = false;

    void recurseAndReverse(ListNode* right, int m, int n) {
        if (n == 1) return;

        right = right->next;

        if (m > 1) this->left = this->left->next;

        recurseAndReverse(right, m - 1, n - 1);

        if (this->left == right || right->next == this->left) stop = true;

        if (!stop) {
            int t = this->left->val;
            this->left->val = right->val;
            right->val = t;
            this->left = this->left->next;
        }
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        this->left = head;
        recurseAndReverse(head, m, n);
        return head;
    }
};

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

Задача: 281. Zigzag Iterator
Сложность: medium

Даны два вектора v1 и v2. Необходимо реализовать итератор, который будет поочередно возвращать элементы из этих двух векторов: сначала из первого, затем из второго и так далее.

Пример:

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

👨‍💻 Алгоритм

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

2⃣Метод next()
Извлекаем пару (номер вектора, индекс элемента), возвращаем соответствующее значение.
Если в этом векторе есть еще элементы — добавляем следующую пару в очередь.

3⃣Метод hasNext()
Просто проверяет, пуста ли очередь. Если нет — значит остались элементы.

😎 Решение

#include <vector>
#include <queue>
#include <utility>

class ZigzagIterator {
private:
    std::vector<std::vector<int>> vectors;
    std::queue<std::pair<int, int>> queue;

public:
    ZigzagIterator(std::vector<int>& v1, std::vector<int>& v2) {
        vectors.push_back(v1);
        vectors.push_back(v2);
        for (int i = 0; i < vectors.size(); ++i) {
            if (!vectors[i].empty()) {
                queue.push({i, 0});
            }
        }
    }

    int next() {
        auto [vecIndex, elemIndex] = queue.front();
        queue.pop();
        int nextElemIndex = elemIndex + 1;
        if (nextElemIndex < vectors[vecIndex].size()) {
            queue.push({vecIndex, nextElemIndex});
        }
        return vectors[vecIndex][elemIndex];
    }

    bool hasNext() {
        return !queue.empty();
    }
};

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

Задача: 204. Count Primes
Сложность: medium

Дано целое число n.
Нужно вернуть количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10 Output: 4
Объяснение: простые числа: 2, 3, 5, 7

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

1⃣Инициализируем булев массив numbers длиной n, где numbers[i] == true означает, что число i — потенциально простое.

2⃣Начинаем с p = 2 и до sqrt(n):
– Если numbers[p] == true, обнуляем все кратные p, начиная с p * p.

3⃣После завершения прохода, все индексы, где numbers[i] == true (и i >= 2), являются простыми.

😎 Решение:

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        vector<bool> numbers(n, true);
        for (int p = 2; p <= sqrt(n); ++p) {
            if (numbers[p]) {
                for (int j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }

        int numberOfPrimes = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
};

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

Задача: 846. Hand of Straights
Сложность: medium

У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.

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

Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

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

1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.

3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎 Решение:

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

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }

        unordered_map<int, int> cardCount;
        for (int card : hand) {
            cardCount[card]++;
        }

        sort(hand.begin(), hand.end());

        for (int card : hand) {
            if (cardCount[card] == 0) {
                continue;
            }

            for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
                if (cardCount[nextCard] == 0) {
                    return false;
                }
                cardCount[nextCard]--;
            }
        }

        return true;
    }
};

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.iss.one/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 366. Find Leaves of Binary Tree
Сложность: medium

Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

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

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

class Solution {
private:
    vector<pair<int, int>> pairs;

    int getHeight(TreeNode* node) {
        if (!node) return -1;
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        int currHeight = max(leftHeight, rightHeight) + 1;
        pairs.push_back({currHeight, node->val});
        return currHeight;
    }

public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        getHeight(root);
        sort(pairs.begin(), pairs.end());
        vector<vector<int>> solution;
        int currentHeight = -1;
        for (const auto& p : pairs) {
            if (p.first != currentHeight) {
                solution.push_back(vector<int>());
                currentHeight = p.first;
            }
            solution.back().push_back(p.second);
        }
        return solution;
    }
};

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

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One
Сложность: medium

Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.

Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

1⃣Инициализируйте переменную operations значением 0.

2⃣Повторяйте операции, пока длина строки s больше 1: Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит. В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.

3⃣Верните количество операций.

😎 Решение:

class Solution {
public:
    int numSteps(string s) {
        int operations = 0;
        while (s.size() > 1) {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int i = s.size() - 1;
                while (i >= 0 && s[i] == '1') {
                    s[i] = '0';
                    i--;
                }
                if (i < 0) {
                    s.insert(s.begin(), '1');
                } else {
                    s[i] = '1';
                }
            }
            operations++;
        }
        return operations;
    }
};

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        if (edges.empty()) return 0;

        unordered_map<int, vector<int>> graph;
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int farthest_node = 0;
        auto dfs = [&](int node, int parent) {
            int max_depth = 0;
            for (int neighbor : graph[node]) {
                if (neighbor != parent) {
                    int depth = dfs(neighbor, node);
                    if (depth + 1 > max_depth) {
                        max_depth = depth + 1;
                        farthest_node = neighbor;
                    }
                }
            }
            return max_depth;
        };

        dfs(0, -1);
        int start_node = farthest_node;

        dfs(start_node, -1);
        return dfs(farthest_node, -1);
    }
};

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив цен, где prices[i] — цена акции в i-й день. Можно совершить не более двух транзакций. Найдите максимальную прибыль.

Пример:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6

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

1⃣Проходим массив слева направо и сохраняем в leftProfits[i] максимальную прибыль от одной транзакции от начала до дня i.

2⃣Проходим массив справа налево и сохраняем в rightProfits[i] максимальную прибыль от одной транзакции от дня i до конца.

3⃣Для каждой точки разбиения i считаем сумму leftProfits[i] + rightProfits[i+1], и выбираем максимум из всех таких сумм.

😎 Решение:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        if (length <= 1) return 0;

        int leftMin = prices[0];
        int rightMax = prices[length - 1];

        vector<int> leftProfits(length, 0);
        vector<int> rightProfits(length + 1, 0);

        for (int l = 1; l < length; ++l) {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = min(leftMin, prices[l]);

            int r = length - 1 - l;
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r]);
            rightMax = max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < length; ++i) {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1]);
        }

        return maxProfit;
    }
};

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

Задача: 304. Range Sum Query 2D - Immutable
Сложность: medium

Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Реализуйте класс NumMatrix:
- NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени.

Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

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

1⃣Инициализация:
Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями.

2⃣Предварительное вычисление сумм:
Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени.

😎 Решение:

class NumMatrix {
private:
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
};

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60
Сложность: medium

Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.

Пример:

Input: time = [30,20,150,100,40]
Output: 3

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

1⃣Инициализация и вычисление остатков:
Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями.

2⃣Подсчет пар:
Пройдитесь по каждой песне в списке и для каждого элемента:
Вычислите остаток от деления времени песни на 60.
Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).
Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).
Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.

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

😎 Решение:

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> remainders(60, 0);
        int count = 0;
        
        for (int t : time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
};

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        const int MOD = 1337;

        auto powmod = [](int x, int y, int mod) -> int {
            int result = 1;
            x = x % mod;
            while (y > 0) {
                if (y % 2 == 1) {
                    result = (result * x) % mod;
                }
                y = y / 2;
                x = (x * x) % mod;
            }
            return result;
        };

        function<int(int, vector<int>&, int)> superPowHelper = [&](int a, vector<int>& b, int mod) -> int {
            if (b.empty()) {
                return 1;
            }
            int last_digit = b.back();
            b.pop_back();
            int part1 = powmod(a, last_digit, mod);
            int part2 = powmod(superPowHelper(a, b, mod), 10, mod);
            return (part1 * part2) % mod;
        };

        return superPowHelper(a, b, MOD);
    }
};

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

Задача: 370. Range Addition
Сложность: medium

Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].
У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.
Верните arr после применения всех обновлений.

Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

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

1⃣Для каждого обновления (start, end, val) выполните две операции:
Увеличьте значение в позиции start на val: arr[start] = arr[start] + val.
Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val.

2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0).

3⃣Верните обновленный массив arr.

😎 Решение:

vector<int> getModifiedArray(int length, vector<vector<int> > updates)
{
    vector<int> result(length, 0);

    for (auto& tuple : updates) {
        int start = tuple[0], end = tuple[1], val = tuple[2];

        for (int i = start; i <= end; i++) {
            result[i] += val;
        }
    }

    return result;
}

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

Задача: 980. Unique Paths III
Сложность: hard

Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:

1, представляющая начальную клетку. Существует ровно одна начальная клетка.
2, представляющая конечную клетку. Существует ровно одна конечная клетка.
0, представляющая пустые клетки, по которым можно ходить.
-1, представляющая препятствия, по которым нельзя ходить.
Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.

Пример:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

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

1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.

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

3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.

😎 Решение:

class Solution {
public:
    int rows, cols;
    vector<vector<int>> grid;
    int path_count;

    void backtrack(int row, int col, int remain) {
        if (grid[row][col] == 2 && remain == 1) {
            path_count += 1;
            return;
        }

        int temp = grid[row][col];
        grid[row][col] = -4;
        remain -= 1;

        int row_offsets[4] = {0, 0, 1, -1};
        int col_offsets[4] = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int next_row = row + row_offsets[i];
            int next_col = col + col_offsets[i];

            if (0 > next_row || next_row >= rows || 0 > next_col || next_col >= cols)
                continue;

            if (grid[next_row][next_col] < 0)
                continue;

            backtrack(next_row, next_col, remain);
        }

        grid[row][col] = temp;
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
        int non_obstacles = 0, start_row = 0, start_col = 0;

        rows = grid.size();
        cols = grid[0].size();
        this->grid = grid;

        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row][col];
                if (cell >= 0)
                    non_obstacles += 1;
                if (cell == 1) {
                    start_row = row;
                    start_col = col;
                }
            }

        path_count = 0;

        backtrack(start_row, start_col, non_obstacles);

        return path_count;
    }
};

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