Задача: 1512. Number of Good Pairs
Сложность: easy

Дан массив целых чисел nums, верните количество хороших пар.

Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.

Пример:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

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

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

2⃣Итерируйте i от 0 до nums.length:
Итерируйте j от i + 1 до nums.length:
Если nums[i] == nums[j], увеличьте ans на 1.

3⃣Верните ans.

😎 Решение:

var numIdenticalPairs = function(nums) {
    let ans = 0
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                ans++
            }
        }
    }
    return ans
}\

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

Сложность: medium
Задача: 377. Combination Sum IV

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.
Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

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

2⃣Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию.

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

😎 Решение:

class Solution {
    constructor() {
        this.memo = new Map();
    }

    combinationSum4(nums, target) {
        return this.combs(nums, target);
    }

    combs(nums, remain) {
        if (remain === 0) {
            return 1;
        }
        if (this.memo.has(remain)) {
            return this.memo.get(remain);
        }

        let result = 0;
        for (const num of nums) {
            if (remain - num >= 0) {
                result += this.combs(nums, remain - num);
            }
        }
        this.memo.set(remain, result);
        return result;
    }
}

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

Задача: 602. Friend Requests II: Who Has the Most Friends
Сложность: medium

Напишите решение для нахождения людей, у которых больше всего друзей, и количества их друзей.
Тестовые случаи сгенерированы так, что только у одного человека больше всего друзей.
Формат результата приведён в следующем примере.

Пример:

Input: 
RequestAccepted table:
+--------------+-------------+-------------+
| requester_id | accepter_id | accept_date |
+--------------+-------------+-------------+
| 1            | 2           | 2016/06/03  |
| 1            | 3           | 2016/06/08  |
| 2            | 3           | 2016/06/08  |
| 3            | 4           | 2016/06/09  |
+--------------+-------------+-------------+
Output: 
+----+-----+
| id | num |
+----+-----+
| 3  | 3   |
+----+-----+
Explanation: 
The person with id 3 is a friend of people 1, 2, and 4, so he has three friends in total, which is the most number than any others.

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

1⃣Поскольку человек может подружиться, отправив или приняв запрос дружбы, для подсчета количества друзей у каждого человека объединяем столбцы requester_id и accepter_id в один.

2⃣Используем UNION ALL для сохранения всех дублирующихся значений и переименовываем столбцы в id.

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

😎 Решение:

WITH Combined AS (
    SELECT requester_id AS id
    FROM friendships
    UNION ALL
    SELECT accepter_id AS id
    FROM friendships
),
FriendCounts AS (
    SELECT id, COUNT(*) AS friend_count
    FROM Combined
    GROUP BY id
    ORDER BY friend_count DESC
)
SELECT id, friend_count
FROM FriendCounts
LIMIT 1;

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

Задача: 209. Minimum Size Subarray Sum
Сложность: medium

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1️⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2️⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3️⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

class Solution {
    minSubArrayLen(target, nums) {
        let left = 0, sumOfCurrentWindow = 0;
        let res = Number.MAX_VALUE;

        for (let right = 0; right < nums.length; right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = Math.min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left];
                left++;
            }
        }

        return res === Number.MAX_VALUE ? 0 : res;
    }
}

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

Задача: 268. Missing Number
Сложность: easy

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1️⃣Сначала отсортируйте массив nums.

2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.

😎 Решение:

var missingNumber = function(nums) {
    nums.sort((a, b) => a - b)
    if (nums[nums.length - 1] != nums.length) {
        return nums.length
    } else if (nums[0] != 0) {
        return 0
    }
    for (let i = 1; i < nums.length; i++) {
        let expectedNum = nums[i - 1] + 1
        if (nums[i] != expectedNum) {
            return expectedNum
        }
    }
    return -1
}

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

Задача: 859. Buddy Strings
Сложность: easy

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

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

var buddyStrings = function(s, goal) {
    if (s.length !== goal.length) return false;
    if (s === goal) {
        const freq = new Map();
        for (const ch of s) {
            if (freq.has(ch)) return true;
            freq.set(ch, 1);
        }
        return false;
    }

    let firstIndex = -1, secondIndex = -1;
    for (let i = 0; i < s.length; ++i) {
        if (s[i] !== goal[i]) {
            if (firstIndex === -1) firstIndex = i;
            else if (secondIndex === -1) secondIndex = i;
            else return false;
        }
    }

    return secondIndex !== -1 &&
           s[firstIndex] === goal[secondIndex] &&
           s[secondIndex] === goal[firstIndex];
};

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

Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

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

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

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

😎 Решение:

class Solution {
    storeFirstOptions(s, startPos, firstOptions) {
        if (s[startPos] !== '{') {
            firstOptions.push(s[startPos]);
        } else {
            startPos++;
            while (s[startPos] !== '}') {
                if (s[startPos] >= 'a' && s[startPos] <= 'z') {
                    firstOptions.push(s[startPos]);
                }
                startPos++;
            }
            firstOptions.sort();
        }
        return startPos + 1;
    }

    findAllWords(s, startPos) {
        if (startPos === s.length) {
            return [""];
        }

        const firstOptions = [];
        const remStringStartPos = this.storeFirstOptions(s, startPos, firstOptions);
        const wordsWithRemString = this.findAllWords(s, remStringStartPos);

        const expandedWords = [];
        for (const c of firstOptions) {
            for (const word of wordsWithRemString) {
                expandedWords.push(c + word);
            }
        }
        return expandedWords;
    }

    expand(s) {
        return this.findAllWords(s, 0);
    }
}

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

Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

class Solution {
    minTransfers(transactions) {
        const creditMap = new Map();
        for (const t of transactions) {
            creditMap.set(t[0], (creditMap.get(t[0]) || 0) + t[2]);
            creditMap.set(t[1], (creditMap.get(t[1]) || 0) - t[2]);
        }
        
        const creditList = [];
        for (const amount of creditMap.values()) {
            if (amount !== 0) {
                creditList.push(amount);
            }
        }
        
        const n = creditList.length;
        
        const dfs = (cur) => {
            while (cur < n && creditList[cur] === 0) {
                cur++;
            }
            if (cur === n) {
                return 0;
            }
            let cost = Infinity;
            for (let nxt = cur + 1; nxt < n; nxt++) {
                if (creditList[nxt] * creditList[cur] < 0) {
                    creditList[nxt] += creditList[cur];
                    cost = Math.min(cost, 1 + dfs(cur + 1));
                    creditList[nxt] -= creditList[cur];
                }
            }
            return cost;
        };
        
        return dfs(0);
    }
}

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

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

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution {
  kLengthApart(nums, k) {
    let count = k;
    for (const num of nums) {
      if (num === 1) {
        if (count < k) {
          return false;
        }
        count = 0;
      } else {
        count++;
      }
    }
    return true;
  }
}

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

Задача: 917. Reverse Only Letters
Сложность: easy

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

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1⃣Создать массив для хранения только английских букв из строки s.

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

var reverseOnlyLetters = function(s) {
    const letters = s.split('').filter(c => /[a-zA-Z]/.test(c));
    letters.reverse();
    let idx = 0;
    return s.split('').map(c => {
        if (/[a-zA-Z]/.test(c)) {
            return letters[idx++];
        } else {
            return c;
        }
    }).join('');
};

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

Задача: 205. Isomorphic Strings
Сложность: easy

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1️⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2️⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3️⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

class Solution {
    isIsomorphic(s, t) {
        let mappingStoT = {};
        let mappingTtoS = {};

        for (let i = 0; i < s.length; i++) {
            let c1 = s[i];
            let c2 = t[i];

            if (mappingStoT[c1] === undefined && mappingTtoS[c2] === undefined) {
                mappingStoT[c1] = c2;
                mappingTtoS[c2] = c1;
            } else if (mappingStoT[c1] !== c2 || mappingTtoS[c2] !== c1) {
                return false;
            }
        }

        return true;
    }
}

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

class MaxStack {
    constructor() {
        this.stack = [];
        this.maxStack = [];
    }

    push(x) {
        this.stack.push(x);
        if (!this.maxStack.length || x >= this.maxStack[this.maxStack.length - 1]) {
            this.maxStack.push(x);
        }
    }

    pop() {
        const x = this.stack.pop();
        if (x === this.maxStack[this.maxStack.length - 1]) {
            this.maxStack.pop();
        }
        return x;
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    peekMax() {
        return this.maxStack[this.maxStack.length - 1];
    }

    popMax() {
        const maxVal = this.maxStack.pop();
        const buffer = [];
        while (this.stack[this.stack.length - 1] !== maxVal) {
            buffer.push(this.stack.pop());
        }
        this.stack.pop();
        while (buffer.length) {
            this.push(buffer.pop());
        }
        return maxVal;
    }
}

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

Задача: 322. Coin Change
Сложность: medium

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

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

var coinChange = function(coins, amount) {
    return coinChangeHelper(0, coins, amount);
};

var coinChangeHelper = function(idxCoin, coins, amount) {
    if (amount === 0) return 0;
    if (idxCoin < coins.length && amount > 0) {
        let maxVal = Math.floor(amount / coins[idxCoin]);
        let minCost = Number.MAX_SAFE_INTEGER;
        for (let x = 0; x <= maxVal; x++) {
            if (amount >= x * coins[idxCoin]) {
                let res = coinChangeHelper(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                if (res !== -1) {
                    minCost = Math.min(minCost, res + x);
                }
            }
        }
        return minCost === Number.MAX_SAFE_INTEGER ? -1 : minCost;
    }
    return -1;
};

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

Задача: 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 {
    getSum(a, b) {
        let x = Math.abs(a), y = Math.abs(b);
        if (x < y) return this.getSum(b, a);
        const sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y !== 0) {
                const carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y !== 0) {
                const borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}

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

Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

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

Пример:

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

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

1️⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.

2️⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

3️⃣Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент.

😎 Решение:

var zigzagLevelOrder = function (root) {
    if (root === null) return [];
    const results = [];
    const node_queue = [root, null];
    const level_list = [];
    let is_order_left = true;
    while (node_queue.length > 0) {
        const curr_node = node_queue.shift();
        if (curr_node !== null) {
            if (is_order_left) level_list.push(curr_node.val);
            else level_list.unshift(curr_node.val);
            if (curr_node.left !== null) node_queue.push(curr_node.left);
            if (curr_node.right !== null) node_queue.push(curr_node.right);
        } else {
            results.push([...level_list]);
            level_list.length = 0;
            if (node_queue.length > 0) node_queue.push(null);
            is_order_left = !is_order_left;
        }
    }
    return results;
};

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

var advantageCount = function(A, B) {
    let sortedA = A.slice().sort((a, b) => a - b);
    let sortedB = B.map((val, idx) => [val, idx]).sort((a, b) => a[0] - b[0]);
    let assigned = {}, remaining = [], j = 0;

    B.forEach(b => assigned[b] = []);

    sortedA.forEach(a => {
        if (a > sortedB[j][0]) {
            assigned[sortedB[j][0]].push(a);
            j++;
        } else {
            remaining.push(a);
        }
    });

    return B.map(b => assigned[b].length ? assigned[b].pop() : remaining.pop());
};

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

Задача: 954. Array of Doubled Pairs
Сложность: medium

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:
Input: arr = [3,1,3,6]
Output: false

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

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

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

var canReorderDoubled = function(arr) {
    let count = new Map();
    for (let num of arr) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    arr.sort((a, b) => Math.abs(a) - Math.abs(b));
    for (let num of arr) {
        if (count.get(num) === 0) continue;
        if (count.get(num * 2) === 0) return false;
        count.set(num, count.get(num) - 1);
        count.set(num * 2, count.get(num * 2) - 1);
    }
    return true;
};

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

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

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

3⃣Вернуть размер множества.

😎 Решение:

var subarrayBitwiseORs = function(arr) {
    let result = new Set();
    let current = new Set();
    for (let num of arr) {
        let next = new Set();
        for (let x of current) {
            next.add(x | num);
        }
        next.add(num);
        current = next;
        for (let x of current) {
            result.add(x);
        }
    }
    return result.size;
};

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

var minCostPath = function(coins, maxJump) {
    const n = coins.length;
    if (coins[0] === -1) return [];
    
    const dp = new Array(n).fill(Infinity);
    dp[0] = coins[0];
    const path = Array.from({ length: n }, () => []);
    path[0] = [1];
    
    const heap = [[coins[0], 0]];
    
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]);
        const [current_cost, i] = heap.shift();
        if (current_cost > dp[i]) continue;
        for (let k = 1; k <= maxJump; k++) {
            if (i + k < n && coins[i + k] !== -1) {
                const new_cost = current_cost + coins[i + k];
                if (new_cost < dp[i + k] || (new_cost === dp[i + k] && path[i].concat(i + k + 1) < path[i + k])) {
                    dp[i + k] = new_cost;
                    path[i + k] = path[i].concat(i + k + 1);
                    heap.push([new_cost, i + k]);
                }
            }
        }
    }
    
    return dp[n - 1] === Infinity ? [] : path[n - 1];
};

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

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

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

var balanceBST = function(root) {
    if (!root) return null;

    const vineHead = new TreeNode(0);
    vineHead.right = root;
    let current = vineHead;

    while (current.right) {
        if (current.right.left) {
            rightRotate(current, current.right);
        } else {
            current = current.right;
        }
    }

    let nodeCount = 0;
    current = vineHead.right;
    while (current) {
        nodeCount++;
        current = current.right;
    }

    let m = 2 ** Math.floor(Math.log2(nodeCount + 1)) - 1;
    makeRotations(vineHead, nodeCount - m);
    while (m > 1) {
        m = Math.floor(m / 2);
        makeRotations(vineHead, m);
    }

    return vineHead.right;
};

function rightRotate(parent, node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    parent.right = tmp;
}

function leftRotate(parent, node) {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    parent.right = tmp;
}

function makeRotations(vineHead, count) {
    let current = vineHead;
    for (let i = 0; i < count; i++) {
        const tmp = current.right;
        leftRotate(current, tmp);
        current = current.right;
    }
}

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

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

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.

3⃣Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.

😎 Решение:

var numsSameConsecDiff = function(N, K) {
    if (N === 1) return [...Array(10).keys()];

    let queue = [...Array(9).keys()].map(i => i + 1);
    for (let level = 1; level < N; ++level) {
        let nextQueue = [];
        for (let num of queue) {
            let tailDigit = num % 10;
            let nextDigits = [tailDigit + K, tailDigit - K];
            for (let nextDigit of nextDigits) {
                if (nextDigit >= 0 && nextDigit < 10) {
                    nextQueue.push(num * 10 + nextDigit);
                }
            }
        }
        queue = nextQueue;
    }

    return queue;
};

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