Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium

Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

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

1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0.

2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0):
Сдвигайте max_xor влево, чтобы освободить следующий бит.
Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы.

3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums:
Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i.
Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите.

😎 Решение:

class Solution {
    findMaximumXOR(nums) {
        let maxNum = nums[0];
        for (const num of nums) {
            if (num > maxNum) {
                maxNum = num;
            }
        }
        const L = maxNum.toString(2).length;

        let maxXor = 0;
        for (let i = L - 1; i >= 0; i--) {
            maxXor <<= 1;
            const currXor = maxXor | 1;
            const prefixes = new Set();
            for (const num of nums) {
                prefixes.add(num >> i);
            }
            for (const p of prefixes) {
                if (prefixes.has(currXor ^ p)) {
                    maxXor = currXor;
                    break;
                }
            }
        }
        return maxXor;
    }
}

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

Задача: 1425. Constrained Subsequence Sum
Сложность: hard

Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.

Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.

Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

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

1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums.

2⃣Итерируйте i по индексам nums:
Если i минус первый элемент queue больше k, удалите элемент из начала queue.
Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()].
Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue.
Если dp[i] > 0, добавьте i в конец queue.

3⃣Верните максимальное значение в массиве dp.

😎 Решение:

class Solution {
    constrainedSubsetSum(nums, k) {
        const queue = [];
        const dp = new Array(nums.length).fill(0);
        let maxSum = Number.MIN_SAFE_INTEGER;
        
        for (let i = 0; i < nums.length; i++) {
            if (queue.length > 0 && i - queue[0] > k) {
                queue.shift();
            }
            
            dp[i] = (queue.length > 0 ? dp[queue[0]] : 0) + nums[i];
            
            while (queue.length > 0 && dp[queue[queue.length - 1]] < dp[i]) {
                queue.pop();
            }
            
            if (dp[i] > 0) {
                queue.push(i);
            }
            
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

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

Задача: 392. Is Subsequence
Сложность: easy

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов.

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

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

😎 Решение:

function isSubsequence(s, t) {
    let leftBound = s.length, rightBound = t.length;
    let pLeft = 0, pRight = 0;

    while (pLeft < leftBound && pRight < rightBound) {
        if (s[pLeft] === t[pRight]) {
            pLeft += 1;
        }
        pRight += 1;
    }
    return pLeft === leftBound;
}

// Example usage
console.log(isSubsequence("abc", "ahbgdc")); // Output: true
console.log(isSubsequence("axc", "ahbgdc")); // Output: false

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

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

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

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

😎 Решение:

class Solution {
    videoStitching(clips, T) {
        clips.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
        let end = -1, end2 = 0, res = 0;
        
        for (const [start, finish] of clips) {
            if (end2 >= T || start > end2) break;
            if (end < start && start <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.max(end2, finish);
        }
        return end2 >= T ? res : -1;
    }
}

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

Задача: 639. Decode Ways II
Сложность: hard

Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

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

3⃣Модульное вычисление
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

var numDecodings = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= n; i++) {
        if (s[i - 1] === '*') {
            dp[i] = 9 * dp[i - 1];
        } else if (s[i - 1] !== '0') {
            dp[i] = dp[i - 1];
        }

        if (i > 1) {
            if (s[i - 2] === '*') {
                if (s[i - 1] === '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '1') {
                if (s[i - 1] === '*') {
                    dp[i] += 9 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '2') {
                if (s[i - 1] === '*') {
                    dp[i] += 6 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += dp[i - 2];
                }
            }
        }

        dp[i] %= MOD;
    }

    return dp[n];
};

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

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

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

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение

class Solution {
    findKthPositive(arr, k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        const n = arr.length;
        for (let i = 0; i < n - 1; i++) {
            const currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

function minSubsequences(source, target) {
    let subsequencesCount = 0;
    let targetIndex = 0;

    while (targetIndex < target.length) {
        let sourceIndex = 0;
        subsequencesCount++;
        let startIndex = targetIndex;

        while (sourceIndex < source.length && targetIndex < target.length) {
            if (source[sourceIndex] === target[targetIndex]) {
                targetIndex++;
            }
            sourceIndex++;
        }

        if (targetIndex === startIndex) {
            return -1;
        }
    }

    return subsequencesCount;
}

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

Задача: 974. Subarray Sums Divisible by K
Сложность: medium

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

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

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

1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1.

2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений.

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

😎 Решение:

var subarraysDivByK = function(nums, k) {
    let prefixMod = 0, result = 0;
    const modGroups = new Array(k).fill(0);
    modGroups[0] = 1;

    for (let num of nums) {
        prefixMod = (prefixMod + num % k + k) % k;
        result += modGroups[prefixMod];
        modGroups[prefixMod]++;
    }

    return result;
};

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

Задача: 55. Jump Game
Сложность: medium

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

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

Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

1️⃣ Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2️⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.

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

😎 Решение:

let memo;
const canJumpFromPosition = (position, nums) => {
    if (memo[position] != "UNKNOWN") {
        return memo[position] == "GOOD";
    }
    let furthestJump = Math.min(position + nums[position], nums.length - 1);
    for (
        let nextPosition = position + 1;
        nextPosition <= furthestJump;
        nextPosition++
    ) {
        if (canJumpFromPosition(nextPosition, nums)) {
            memo[position] = "GOOD";
            return true;
        }
    }
    memo[position] = "BAD";
    return false;
};
var canJump = function (nums) {
    memo = new Array(nums.length).fill("UNKNOWN");
    memo[memo.length - 1] = "GOOD";
    return canJumpFromPosition(0, nums);
};

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

Задача: 122. Best Time to Buy and Sell Stock II
Сложность: medium

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

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

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

1️⃣Предположим, что дан массив:
\[ 7, 1, 5, 3, 6, 4 \]
Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение*

2️⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики.
Математически говоря:
Общая прибыль = ∑ (высота(пик i) - высота(впадина i))

3️⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли.
Например, в вышеуказанном случае, если мы пропустим пик i и впадину j, пытаясь получить больше прибыли, рассматривая точки с большей разницей в высотах, чистая прибыль всегда будет меньше, чем та, которая была бы получена при их учете, поскольку C всегда будет меньше, чем A+B.

😎 Решение:

var maxProfit = function (prices) {
    let i = 0;
    let valley = prices[0];
    let peak = prices[0];
    let maxprofit = 0;
    while (i < prices.length - 1) {
        while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
        valley = prices[i];
        while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
        peak = prices[i];
        maxprofit += peak - valley;
    }
    return maxprofit;
};

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

Задача: 38. Count and Say
Сложность: medium

Последовательность count-and-say — это последовательность строк, определяемая рекурсивно:
countAndSay(1) = "1"
countAndSay(n) — это проговаривание предыдущей строки: сколько подряд идущих одинаковых символов, и какой символ.

Пример:

Input: n = 4  
Output: "1211"

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

1️⃣Если n = 1, вернуть "1" — это базовый случай.

2️⃣Инициализировать строку temp = "1" — с неё всё начинается.

3️⃣Для i от 2 до n:
- Пройти по строке temp, считая подряд одинаковые символы
- Когда символ меняется — добавить в строку ans количество + символ
- В конце каждой итерации: temp = ans, ans = ""

😎 Решение:

class Solution {
  countAndSay(n) {
    if (n === 1) return "1";

    let temp = "1";
    let ans = "";

    for (let i = 2; i <= n; i++) {
      let cnt = 1;
      let prev = temp[0];

      for (let j = 1; j < temp.length; j++) {
        const char = temp[j];
        if (char === prev) {
          cnt++;
        } else {
          ans += cnt.toString() + prev;
          prev = char;
          cnt = 1;
        }
      }

      ans += cnt.toString() + prev;
      temp = ans;
      ans = "";
    }

    return temp;
  }
}

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

Задача: 969. Pancake Sorting
Сложность: medium

Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.

При одном перевороте блина мы выполняем следующие шаги:

Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.

Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.

Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

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

1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0
] (в Python).

2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего.

3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте.

😎 Решение:

var pancakeSort = function(A) {
    const ans = [];

    for (let valueToSort = A.length; valueToSort > 0; valueToSort--) {
        const index = find(A, valueToSort);
        if (index === valueToSort - 1) continue;
        if (index !== 0) {
            ans.push(index + 1);
            flip(A, index + 1);
        }
        ans.push(valueToSort);
        flip(A, valueToSort);
    }

    return ans;
};

function flip(sublist, k) {
    let i = 0;
    while (i < k / 2) {
        [sublist[i], sublist[k - i - 1]] = [sublist[k - i - 1], sublist[i]];
        i++;
    }
}

function find(a, target) {
    for (let i = 0; i < a.length; i++) {
        if (a[i] === target) {
            return i;
        }
    }
    return -1;
}

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

Задача: 224. Basic Calculator
Сложность: hard

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

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.

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

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

class Solution {
    evaluateExpr(stack) {
        if (stack.length === 0 || typeof stack[stack.length - 1] !== 'number') {
            stack.push(0);
        }

        let res = stack.pop();

        while (stack.length !== 0 && stack[stack.length - 1] !== ')') {
            let sign = stack.pop();

            if (sign === '+') {
                res += stack.pop();
            } else {
                res -= stack.pop();
            }
        }
        return res;
    }

    calculate(s) {
        let operand = 0;
        let n = 0;
        let stack = [];

        for (let i = s.length - 1; i >= 0; i--) {
            let ch = s[i];

            if (/\d/.test(ch)) {
                operand = Math.pow(10, n) * (parseInt(ch)) + operand;
                n += 1;
            } else if (ch !== ' ') {
                if (n !== 0) {
                    stack.push(operand);
                    n = 0;
                    operand = 0;
                }
                if (ch === '(') {
                    let res = this.evaluateExpr(stack);
                    stack.pop();
                    stack.push(res);
                } else {
                    stack.push(ch);
                }
            }
        }

        if (n !== 0) {
            stack.push(operand);
        }

        return this.evaluateExpr(stack);
    }
}

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

Задача: 933. Number of Recent Calls
Сложность: easy

У вас есть класс RecentCounter, который подсчитывает количество последних запросов за определенный промежуток времени. Реализуйте класс RecentCounter: RecentCounter() Инициализирует счетчик нулем последних запросов. int ping(int t) Добавляет новый запрос в момент времени t, где t представляет собой некоторое время в миллисекундах, и возвращает количество запросов, произошедших за последние 3000 миллисекунд (включая новый запрос). Точнее, возвращается количество запросов, произошедших в диапазоне [t - 3000, t]. Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.

Пример:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

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

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

2⃣Реализовать метод ping, который принимает время запроса t:
Добавить t в очередь.
Удалить из очереди все запросы, которые не попадают в диапазон [t - 3000, t].

3⃣Вернуть размер очереди.

😎 Решение:

class RecentCounter {
    constructor() {
        this.q = [];
    }

    ping(t) {
        this.q.push(t);
        while (this.q[0] < t - 3000) {
            this.q.shift();
        }
        return this.q.length;
    }
}

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

Задача: 477. Total Hamming Distance
Сложность: medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.

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

😎 Решение:

function totalHammingDistance(nums) {
    let ans = 0;

    if (nums.length === 0) {
        return ans;
    }

    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            ans += (nums[i] ^ nums[j]).toString(2).split('1').length - 1;
        }
    }

    return ans;
}

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

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

Вам дан диапазон [lower, upper] и отсортированный массив уникальных целых чисел nums, где все элементы находятся в этом диапазоне.
Число x считается пропущенным, если оно находится в диапазоне [lower, upper] и его нет в массиве nums.
Верните кратчайший отсортированный список диапазонов, который точно покрывает все пропущенные числа. То есть ни один элемент из nums не включен в какой-либо из диапазонов, и каждое пропущенное число покрыто одним из диапазонов..

Пример:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

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

1️⃣Инициализация и проверка начальных условий:
Создайте переменную n и инициализируйте её размером массива nums.
Создайте список missingRanges, который будет содержать решение задачи.
Если массив nums пуст, верните диапазон [lower, upper].
Проверьте, совпадает ли первый элемент массива с lower. Если lower < nums[0], добавьте в missingRanges диапазон [lower, nums[0] - 1].

2️⃣Итерация по элементам массива:
Проитерируйте по всем элементам в nums с помощью цикла от i = 0 до n - 2 (до предпоследнего элемента):
Если текущий элемент nums[i] и следующий элемент nums[i + 1] отличаются на 1 или меньше, между этими двумя числами нет пропущенных чисел.
В противном случае, если nums[i + 1] - nums[i] > 1, то пропущены числа от nums[i] + 1 до nums[i + 1] - 1 (включительно). В этом случае диапазон [nums[i] + 1, nums[i + 1] - 1] добавляется в missingRanges.

3️⃣Проверка и добавление последнего пропущенного диапазона:
Проверьте, совпадает ли последний элемент массива с upper. Если nums[n - 1] < upper, добавьте в missingRanges диапазон [nums[n - 1] + 1, upper].

😎 Решение:

var findMissingRanges = function (nums, lower, upper) {
    let n = nums.length;
    let missingRanges = [];
    if (n === 0) {
        missingRanges.push([lower, upper]);
        return missingRanges;
    }
    if (lower < nums[0]) {
        missingRanges.push([lower, nums[0] - 1]);
    }
    for (let i = 0; i < n - 1; i++) {
        if (nums[i + 1] - nums[i] <= 1) {
            continue;
        }
        missingRanges.push([nums[i] + 1, nums[i + 1] - 1]);
    }
    if (upper > nums[n - 1]) {
        missingRanges.push([nums[n - 1] + 1, upper]);
    }

    return missingRanges;
};

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

Сложность: hard
Задача: 302. Smallest Rectangle Enclosing Black Pixels

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

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    minArea(image, x, y) {
        const m = image.length, n = image[0].length;
        const left = this.searchColumns(image, 0, y, 0, m, true);
        const right = this.searchColumns(image, y + 1, n, 0, m, false);
        const top = this.searchRows(image, 0, x, left, right, true);
        const bottom = this.searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

    searchColumns(image, i, j, top, bottom, opt) {
        while (i !== j) {
            const k = Math.floor((i + j) / 2);
            let t = top;
            while (t < bottom && image[t][k] === '0') t++;
            if ((t < bottom) === opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }

    searchRows(image, i, j, left, right, opt) {
        while (i !== j) {
            const k = Math.floor((i + j) / 2);
            let l = left;
            while (l < right && image[k][l] === '0') l++;
            if ((l < right) === opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }
}

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

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

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

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

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

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

2⃣Сортировка и удаление элементов:
Создайте массив частот и заполните его значениями из хеш-таблицы.
Отсортируйте массив частот.
Инициализируйте переменную для отслеживания числа удаленных элементов и итеративно добавляйте частоты, пока количество удаленных элементов не превысит k.

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

var findLeastNumOfUniqueInts = function(arr, k) {
    let freqMap = new Map();
    for (let num of arr) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    
    let frequencies = Array.from(freqMap.values());
    frequencies.sort((a, b) => a - b);
    
    let elementsRemoved = 0;
    for (let i = 0; i < frequencies.length; i++) {
        elementsRemoved += frequencies[i];
        if (elementsRemoved > k) {
            return frequencies.length - i;
        }
    }
    
    return 0;
};

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.
Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы.

Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

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

1️⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

2️⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки.

3️⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

var setZeroes = function (matrix) {
    let isCol = false;
    let R = matrix.length;
    let C = matrix[0].length;
    for (let i = 0; i < R; i++) {
        if (matrix[i][0] == 0) {
            isCol = true;
        }
        for (let j = 1; j < C; j++) {
            if (matrix[i][j] == 0) {
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    for (let i = 1; i < R; i++) {
        for (let j = 1; j < C; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if (matrix[0][0] == 0) {
        for (let j = 0; j < C; j++) {
            matrix[0][j] = 0;
        }
    }
    if (isCol) {
        for (let i = 0; i < R; i++) {
            matrix[i][0] = 0;
        }
    }
};

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

Задача: 1120. Maximum Average Subtree
Сложность: medium

Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.

Поддерево дерева — это любой узел этого дерева плюс все его потомки.

Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

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

2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.

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

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    maximumAverageSubtree(root) {
        return this.maxAverage(root).maxAverage;
    }

    maxAverage(node) {
        if (!node) {
            return { nodeCount: 0, valueSum: 0, maxAverage: 0 };
        }

        const left = this.maxAverage(node.left);
        const right = this.maxAverage(node.right);

        const nodeCount = left.nodeCount + right.nodeCount + 1;
        const valueSum = left.valueSum + right.valueSum + node.val;
        const currentAverage = valueSum / nodeCount;
        const maxAverage = Math.max(currentAverage, left.maxAverage, right.maxAverage);

        return { nodeCount, valueSum, maxAverage };
    }
}

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