Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

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

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    return Math.max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reverse(), secondLen, firstLen));
};

function maxSumNonOverlap(nums, firstLen, secondLen) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const maxFirst = new Array(n).fill(0);
    for (let i = firstLen - 1; i < n; i++) {
        maxFirst[i] = Math.max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
    }
    
    const maxSecond = new Array(n).fill(0);
    for (let i = secondLen - 1; i < n; i++) {
        maxSecond[i] = Math.max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
    }
    
    let maxSum = 0;
    for (let i = firstLen + secondLen - 1; i < n; i++) {
        maxSum = Math.max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
    }
    
    return maxSum;
}

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

Задача: 710. Random Pick with Blacklist
Сложность: hard

Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.

Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

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

1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

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

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

😎 Решение:

class Solution {
    constructor(n, blacklist) {
        this.map = new Map();
        this.bound = n - blacklist.length;
        let blackset = new Set(blacklist);
        let whitelist = this.bound;
        
        for (let b of blacklist) {
            if (b < this.bound) {
                while (blackset.has(whitelist)) {
                    whitelist++;
                }
                this.map.set(b, whitelist);
                whitelist++;
            }
        }
    }
    
    pick() {
        let r = Math.floor(Math.random() * this.bound);
        return this.map.get(r) ?? r;
    }
}

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

Задача: 112. Path Sum
Сложность: easy

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

Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

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

1️⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.

2️⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.

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

😎 Решение:

var hasPathSum = function (root, sum) {
    if (!root) return false;
    let nodeStack = [];
    let sumStack = [];
    nodeStack.push(root);
    sumStack.push(sum - root.val);
    while (nodeStack.length > 0) {
        let currentNode = nodeStack.pop();
        let currSum = sumStack.pop();
        if (!currentNode.left && !currentNode.right && currSum === 0)
            return true;
        if (currentNode.right) {
            nodeStack.push(currentNode.right);
            sumStack.push(currSum - currentNode.right.val);
        }
        if (currentNode.left) {
            nodeStack.push(currentNode.left);
            sumStack.push(currSum - currentNode.left.val);
        }
    }
    return false;
};

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

Задача: 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 {
    numPairsDivisibleBy60(time) {
        const remainders = new Array(60).fill(0);
        let count = 0;
        
        for (const t of time) {
            if (t % 60 === 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

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

Задача: 162. Find Peak Element
Сложность: medium

Пиковым элементом называется элемент, который строго больше своих соседей.
Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков.
Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.
Необходимо написать алгоритм, который работает за время O(log n).

Пример:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

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

1️⃣Начальная проверка:
Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.

2️⃣Определение направления поиска:
Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.
Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.

3️⃣Завершение поиска:
Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности.

😎 Решение:

var findPeakElement = function (nums) {
    return search(nums, 0, nums.length - 1);
};

var search = function (nums, l, r) {
    if (l == r) return l;
    let mid = Math.floor((l + r) / 2);
    if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
    return search(nums, mid + 1, r);
};

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

Задача: 1192. Critical Connections in a Network
Сложность: hard

Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть.

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

Пример:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

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

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

2⃣Поиск в глубину (DFS):
Реализуйте функцию dfs для обхода графа.
Обновите ранги узлов и определите минимальный ранг для текущего узла.
Проверьте, можно ли удалить текущее соединение, и обновите минимальный ранг.

3⃣Поиск критических соединений:
После завершения обхода DFS преобразуйте оставшиеся соединения в список и верните его.

😎 Решение:

class Solution {
    constructor() {
        this.graph = {};
        this.rank = {};
        this.connDict = {};
    }

    criticalConnections(n, connections) {
        this.formGraph(n, connections);
        this.dfs(0, 0);
        let result = [];
        for (let key in this.connDict) {
            result.push(key.split(',').map(Number));
        }
        return result;
    }

    dfs(node, discoveryRank) {
        if (this.rank[node] !== undefined) {
            return this.rank[node];
        }

        this.rank[node] = discoveryRank;
        let minRank = discoveryRank + 1;

        for (let neighbor of this.graph[node]) {
            if (this.rank[neighbor] !== undefined && this.rank[neighbor] === discoveryRank - 1) {
                continue;
            }

            let recursiveRank = this.dfs(neighbor, discoveryRank + 1);

            if (recursiveRank <= discoveryRank) {
                delete this.connDict[[Math.min(node, neighbor), Math.max(node, neighbor)]];
            }

            minRank = Math.min(minRank, recursiveRank);
        }

        return minRank;
    }

    formGraph(n, connections) {
        for (let i = 0; i < n; i++) {
            this.graph[i] = [];
            this.rank[i] = undefined;
        }

        for (let [u, v] of connections) {
            this.graph[u].push(v);
            this.graph[v].push(u);
            this.connDict[[Math.min(u, v), Math.max(u, v)]] = true;
        }
    }
}

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

Задача: 1006. Clumsy Factorial
Сложность: medium

Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n.

Пример:

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

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

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

2⃣Выполнение операций в цикле:
Создайте цикл, который будет обрабатывать числа от n до 1 в порядке убывания.
В цикле выполняйте операции *, /, +, и - последовательно.
Обновляйте текущий результат на каждом шаге в зависимости от остатка от деления текущего индекса на 4.

Учет оставшихся операций и возврат результата:
После завершения цикла добавьте или вычтите оставшиеся числа (если есть) к результату.
Верните окончательный результат.

😎 Решение:

class Solution {
    clumsy(n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2 * 1;
        if (n == 3) return 3 * 2 / 1;
        
        let res = n * (n - 1) / (n - 2);
        n -= 3;
        if (n > 0) res += n--;
        
        while (n > 0) {
            res -= n * (n - 1) / (n - 2);
            n -= 3;
            if (n > 0) res += n--;
        }
        
        return res;
    }
}

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

Задача: 85. Maximal Rectangle
Сложность: hard

Дана бинарная матрица размером rows x cols, заполненная 0 и 1. Найдите наибольший прямоугольник, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

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

1️⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'.

2️⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea).

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

😎 Решение:

var maximalRectangle = function (matrix) {
    if (matrix.length === 0) return 0;
    let maxarea = 0;
    let dp = Array(matrix.length)
        .fill(0)
        .map(() => Array(matrix[0].length).fill(0));
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === "1") {
                dp[i][j] = j === 0 ? 1 : dp[i][j - 1] + 1;
                let width = dp[i][j];
                for (let k = i; k >= 0; k--) {
                    width = Math.min(width, dp[k][j]);
                    maxarea = Math.max(maxarea, width * (i - k + 1));
                }
            }
        }
    }
    return maxarea;
};

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard

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

В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].

Если нет способа сделать arr1 строго возрастающим, верните -1.

Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

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

1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.

2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).

3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.

😎 Решение:

var makeArrayIncreasing = function(arr1, arr2) {
    arr2 = [...new Set(arr2)].sort((a, b) => a - b);
    let dp = new Map();
    
    const dfs = (i, prev) => {
        if (i === arr1.length) return 0;
        let key = `${i}-${prev}`;
        if (dp.has(key)) return dp.get(key);
        
        let cost = 2001;
        if (arr1[i] > prev) {
            cost = dfs(i + 1, arr1[i]);
        }
        
        let idx = bisectRight(arr2, prev);
        if (idx < arr2.length) {
            cost = Math.min(cost, 1 + dfs(i + 1, arr2[idx]));
        }
        
        dp.set(key, cost);
        return cost;
    };
    
    const bisectRight = (arr, value) => {
        let left = 0, right = arr.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] <= value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };

    let result = dfs(0, -1);
    return result < 2001 ? result : -1;
};

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

Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

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

Пример:

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

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

1️⃣Инициализация "стража" и предшественника:
Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.
Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2️⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

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

😎 Решение:

var deleteDuplicates = function (head) {
    let sentinel = new ListNode(0, head);
    let pred = sentinel;
    while (head !== null) {
        if (head.next !== null && head.val === head.next.val) {
            while (head.next !== null && head.val === head.next.val) {
                head = head.next;
            }
            pred.next = head.next;
        } else {
            pred = pred.next;
        }
        head = head.next;
    }
    return sentinel.next;
};

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

Задача: 617. Merge Two Binary Trees
Сложность: medium

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

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

1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

2⃣Если оба узла не пустые, создаем новый узел, значение которого равно сумме значений двух узлов. Рекурсивно объединяем левые и правые поддеревья.

3⃣Возвращаем новый узел, который является корнем объединенного дерева.

😎 Решение:

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function mergeTrees(root1, root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    
    const mergedNode = new TreeNode(root1.val + root2.val);
    mergedNode.left = mergeTrees(root1.left, root2.left);
    mergedNode.right = mergeTrees(root1.right, root2.right);
    
    return mergedNode;
}

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

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

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

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

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

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

😎 Решение:

var minDeletionSize = function(strs) {
    const n = strs.length;
    const m = strs[0].length;
    const deleteCount = new Array(m).fill(false);
    
    const isSorted = () => {
        for (let i = 0; i < n - 1; i++) {
            for (let j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                if (strs[i][j] > strs[i + 1][j]) return false;
                if (strs[i][j] < strs[i + 1][j]) break;
            }
        }
        return true;
    };
    
    while (!isSorted()) {
        for (let j = 0; j < m; j++) {
            if (deleteCount[j]) continue;
            for (let i = 0; i < n - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    deleteCount[j] = true;
                    break;
                }
            }
            if (deleteCount[j]) break;
        }
    }
    
    return deleteCount.filter(Boolean).length;
};

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

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

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

function addBoldTags(keywords, s) {
    const n = s.length;
    const bold = Array(n).fill(false);
    
    for (const word of keywords) {
        let start = s.indexOf(word);
        while (start !== -1) {
            for (let i = start; i < start + word.length; i++) {
                bold[i] = true;
            }
            start = s.indexOf(word, start + 1);
        }
    }
    
    let result = '';
    let i = 0;
    while (i < n) {
        if (bold[i]) {
            result += '<b>';
            while (i < n && bold[i]) {
                result += s[i];
                i++;
            }
            result += '</b>';
        } else {
            result += s[i];
            i++;
        }
    }
    
    return result;
}

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

Задача: 74. Search a 2D Matrix
Сложность: medium

Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами:
Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.
Вы должны написать решение с временной сложностью O(log(m * n)).

Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

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

1️⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1.

2️⃣Пока left <= right:
Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2.

3️⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части.
Сравните pivot_element и target, чтобы определить, в какой части нужно искать target.

😎 Решение:

var searchMatrix = function (matrix, target) {
    let m = matrix.length;
    if (m == 0) return false;
    let n = matrix[0].length;
    let left = 0,
        right = m * n - 1;
    let pivotIdx, pivotElement;
    while (left <= right) {
        pivotIdx = Math.floor((left + right) / 2);
        pivotElement = matrix[Math.floor(pivotIdx / n)][pivotIdx % n];
        if (target == pivotElement) return true;
        else {
            if (target < pivotElement) right = pivotIdx - 1;
            else left = pivotIdx + 1;
        }
    }
    return false;
};

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

Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: medium

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

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

Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

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

1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1.

2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]:
Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:
- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].
- в противном случае, установите before_a = 0.
Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).

3⃣Верните answer после завершения итерации.

😎 Решение:

var longestSubsequence = function(arr, difference) {
    let dp = new Map();
    let answer = 1;
    
    for (let a of arr) {
        let beforeA = dp.get(a - difference) || 0;
        dp.set(a, beforeA + 1);
        answer = Math.max(answer, dp.get(a));
    }
    
    return answer;
};

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

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

Дан массив из k отсортированных связанных списков.
Нужно объединить их в один отсортированный связанный список и вернуть его голову.

Пример:

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

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

1️⃣ Создаем мин-кучу (приоритетную очередь), в которую помещаем первые узлы всех непустых списков.
Приоритет — по значению узла.

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

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

😎 Решение:

var mergeKLists = function (lists) {
    const pq = new MinPriorityQueue({ priority: node => node.val });

    for (const head of lists) {
        if (head) pq.enqueue(head);
    }

    const dummy = new ListNode();
    let cur = dummy;

    while (!pq.isEmpty()) {
        const node = pq.dequeue().element;
        cur.next = node;
        cur = cur.next;

        if (node.next) pq.enqueue(node.next);
    }

    return dummy.next;
};

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

Задача: 150. Evaluate Reverse Polish Notation
Сложность: medium

Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации.
Вычислите это выражение. Верните целое число, которое представляет значение этого выражения.
Обратите внимание на следующие моменты:
Допустимые операторы: '+', '-', '*' и '/'.
Каждый операнд может быть целым числом или другим выражением.
Деление двух целых чисел всегда округляется к нулю.
Деление на ноль в выражении отсутствует.
Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации.
Ответ и все промежуточные вычисления можно представить 32-битным целым числом.

Пример:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

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

1️⃣Обработка входных массивов:
Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n).

2️⃣Обработка типов и деление в Python:

Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом.

3️⃣Использование лямбда-функций:
Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом.

😎 Решение:

const OPERATORS = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "/": (a, b) => Math.trunc(a / b),
    "*": (a, b) => a * b,
};

var evalRPN = function (tokens) {
    let currentPosition = 0;

    while (tokens.length > 1) {

        while (!(tokens[currentPosition] in OPERATORS)) {
            currentPosition += 1;
        }

        const operator = tokens[currentPosition];
        const operation = OPERATORS[operator];
        const number1 = Number(tokens[currentPosition - 2]);
        const number2 = Number(tokens[currentPosition - 1]);

        tokens[currentPosition] = operation(number1, number2);

        tokens.splice(currentPosition - 2, 2);
        currentPosition -= 1;
    }

    return tokens[0];
};

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

Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium

Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].

Пример:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]

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

1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах.

2⃣Решите систему уравнений:
4J + 2S = tomatoSlices
J + S = cheeseSlices

3⃣Если решение существует, верните его, иначе верните пустой список.

😎 Решение:

var numOfBurgers = function(tomatoSlices, cheeseSlices) {
    if (tomatoSlices % 2 !== 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
        return [];
    }
    let total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
    let total_small = cheeseSlices - total_jumbo;
    return [total_jumbo, total_small];
};

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

Задача: 635. Design Log Storage System
Сложность: medium

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.

Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

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

1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.

2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.

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

😎 Решение:

class LogSystem {
    constructor() {
        this.logs = [];
        this.granularity = {
            "Year": 4,
            "Month": 7,
            "Day": 10,
            "Hour": 13,
            "Minute": 16,
            "Second": 19
        };
    }

    put(id, timestamp) {
        this.logs.push({ id, timestamp });
    }

    retrieve(start, end, granularity) {
        const length = this.granularity[granularity];
        start = start.slice(0, length);
        end = end.slice(0, length);
        return this.logs.filter(log => {
            const ts = log.timestamp.slice(0, length);
            return start <= ts && ts <= end;
        }).map(log => log.id);
    }
}

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

Задача: 861. Score After Flipping Matrix
Сложность: hard

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

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

Пример:

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

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

1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались.

2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались.

3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека.

😎 Решение:

var shortestSubarray = function(A, K) {
    const N = A.length;
    const P = new Array(N + 1).fill(0);
    for (let i = 0; i < N; ++i) {
        P[i + 1] = P[i] + A[i];
    }

    let ans = N + 1;
    const monoq = [];

    for (let y = 0; y < P.length; ++y) {
        while (monoq.length > 0 && P[y] <= P[monoq[monoq.length - 1]]) {
            monoq.pop();
        }
        while (monoq.length > 0 && P[y] >= P[monoq[0]] + K) {
            ans = Math.min(ans, y - monoq.shift());
        }
        monoq.push(y);
    }

    return ans < N + 1 ? ans : -1;
};

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