Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

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

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

1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3️⃣Верните sentinel.next.

😎 Решение:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        sentinel = ListNode(0)
        sentinel.next = head
        
        prev, curr = sentinel, head
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        
        return sentinel.next

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.group = {}
        self.maxfreq = 0

    def push(self, val: int) -> None:
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        if f > self.maxfreq:
            self.maxfreq = f
            self.group[f] = []
        self.group[f].append(val)

    def pop(self) -> int:
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

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

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

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

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        char_count = Counter(s)
        result = []
        
        while len(result) < len(s):
            for char in "abcdefghijklmnopqrstuvwxyz":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
            for char in "zyxwvutsrqponmlkjihgfedcba":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
        
        return ''.join(result)

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

def crackSafe(n, k):
    seen = set()
    result = []

    def dfs(node):
        for x in range(k):
            neighbor = node + str(x)
            if neighbor not in seen:
                seen.add(neighbor)
                dfs(neighbor[1:])
                result.append(str(x))

    start_node = '0' * (n - 1)
    dfs(start_node)
    return start_node + ''.join(result)

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.

На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

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

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [0] * (n + 1)

        for i in range(m + 1):
            temp = [0] * (n + 1)
            for j in range(n + 1):
                if i == 0 or j == 0:
                    temp[j] = i + j
                elif word1[i - 1] == word2[j - 1]:
                    temp[j] = dp[j - 1]
                else:
                    temp[j] = 1 + min(dp[j], temp[j - 1])
            dp = temp

        return dp[n]

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

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

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

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

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

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

Задача: 638. Shopping Offers
Сложность: medium

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

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

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

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

😎 Решение:

def shoppingOffers(price, special, needs):
    memo = {}
    
    def dfs(cur_needs):
        val = sum(cur_needs[i] * price[i] for i in range(len(needs)))
        for sp in special:
            new_needs = []
            for i in range(len(needs)):
                if sp[i] > cur_needs[i]:
                    break
                new_needs.append(cur_needs[i] - sp[i])
            if len(new_needs) == len(needs):
                val = min(val, memo.get(tuple(new_needs), dfs(new_needs)) + sp[-1])
        memo[tuple(cur_needs)] = val
        return val

    return dfs(needs)

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

Задача: 568. Maximum Vacation Days
Сложность: hard

LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.

Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Вы можете оставаться в городе большее количество дней, чем количество дней отпуска, но вы должны работать в дополнительные дни, которые не будут учитываться как дни отпуска.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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

1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

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

😎 Решение:

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n, k = len(flights), len(days[0])
        memo = [[-1] * k for _ in range(n)]

        def dfs(cur_city, weekno):
            if weekno == k:
                return 0
            if memo[cur_city][weekno] != -1:
                return memo[cur_city][weekno]
            max_vac = 0
            for next_city in range(n):
                if cur_city == next_city or flights[cur_city][next_city] == 1:
                    max_vac = max(max_vac, days[next_city][weekno] + dfs(next_city, weekno + 1))
            memo[cur_city][weekno] = max_vac
            return max_vac

        return dfs(0, 0)

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

Задача: 517. Super Washing Machines
Сложность: hard

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.

За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.

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

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        dressTotal = sum(machines)
        if dressTotal % n != 0:
            return -1
        
        dressPerMachine = dressTotal // n
        machines = [m - dressPerMachine for m in machines]

        currSum = maxSum = res = 0
        for m in machines:
            currSum += m
            maxSum = max(maxSum, abs(currSum))
            res = max(res, maxSum, m)
        
        return res

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.dp = []
            return
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n + 1) for _ in range(m + 1)]
        for r in range(m):
            for c in range(n):
                self.dp[r + 1][c + 1] = self.dp[r + 1][c] + self.dp[r][c + 1] + matrix[r][c] - self.dp[r][c]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - self.dp[row2 + 1][col1] + self.dp[row1][col1]

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution:
    def minSwaps(self, data):
        ones = sum(data)
        cnt_one = max_one = 0
        left = right = 0

        while right < len(data):
            cnt_one += data[right]
            right += 1
            if right - left > ones:
                cnt_one -= data[left]
                left += 1
            max_one = max(max_one, cnt_one)
        return ones - max_one

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

Задача: 117. Populating Next Right Pointers in Each Node II
Сложность: medium

Вам дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1️⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных.

2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве.

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

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

class Solution:
    def connect(self, root: Optional["Node"]) -> Optional["Node"]:
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)

            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

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

Задача: 541. Reverse String II
Сложность: easy

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.

Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        a = list(s)
        for start in range(0, len(a), 2 * k):
            i, j = start, min(start + k - 1, len(a) - 1)
            while i < j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1
        return ''.join(a)

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

Задача: 905. Sort Array By Parity
Сложность: easy

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

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

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

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

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

3⃣Объединить два списка и вернуть результат.

😎 Решение:

def sortArrayByParity(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 != 0]
    return evens + odds

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

Задача: 319. Bulb Switcher
Сложность: medium

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.

На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.

Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Инициализация
Лампочка остается включенной, если она переключалась нечетное количество раз. Лампочка будет переключаться на каждом делителе её номера.

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

3⃣Подсчет включенных лампочек
Количество лампочек, которые будут включены после n раундов.

😎 Решение:

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(n ** 0.5)

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

Задача: №16. 3Sum Closest
Сложность: medium

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

Пример:

Input: nums = [-1,2,1,-4], target = 1  
Output: 2  

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

1️⃣Отсортировать массив для удобства работы с двумя указателями.

2️⃣Использовать фиксированный индекс i и два указателя j и k, двигаясь навстречу друг другу.

3️⃣На каждом шаге проверять разницу между текущей суммой и target, обновляя result, если найдено более точное значение.

😎 Решение:

class Solution:  
    def threeSumClosest(self, num, target):  
        num.sort()  
        result = num[0] + num[1] + num[2]  
        for i in range(len(num) - 2):  
            j, k = i + 1, len(num) - 1  
            while j < k:  
                sum = num[i] + num[j] + num[k]  
                if sum == target:  
                    return sum  

                if abs(sum - target) < abs(result - target):  
                    result = sum  

                if sum < target:  
                    j += 1  
                else:  
                    k -= 1  

        return result

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

Задача: 353. Design Snake Game
Сложность: medium

Разработайте игру "Змейка", которая играется на устройстве с экраном размером height x width. Поиграйте в игру онлайн, если вы не знакомы с ней.

Змейка изначально находится в верхнем левом углу (0, 0) с длиной в 1 единицу.
Вам дан массив food, где food[i] = (ri, ci) представляет собой строку и столбец позиции пищи, которую змейка может съесть. Когда змейка съедает кусочек пищи, ее длина и очки игры увеличиваются на 1.
Каждый кусочек пищи появляется по очереди на экране, то есть второй кусочек пищи не появится, пока змейка не съест первый кусочек пищи.
Когда кусочек пищи появляется на экране, гарантируется, что он не появится на блоке, занятом змейкой.
Игра заканчивается, если змейка выходит за пределы экрана (врезается в стену) или если ее голова занимает пространство, которое занимает ее тело после движения (например, змейка длиной 4 не может врезаться в себя).

Реализуйте класс SnakeGame:
SnakeGame(int width, int height, int[][] food) Инициализирует объект с экраном размером height x width и позициями пищи.
int move(String direction) Возвращает счет игры после применения одного движения змейки в направлении. Если игра окончена, верните -1.

Пример:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

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

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

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

3⃣Обновите положение змейки и проверьте условия завершения игры. Верните текущий счет или -1, если игра закончена.

😎 Решение:

class SnakeGame:
    def __init__(self, width, height, food):
        self.width = width
        self.height = height
        self.food = food
        self.score = 0
        self.snake = [(0, 0)]
        self.snake_set = set([(0, 0)])
        self.food_index = 0

    def move(self, direction):
        head = self.snake[0]
        new_head = list(head)

        if direction == "U":
            new_head[0] -= 1
        elif direction == "D":
            new_head[0] += 1
        elif direction == "L":
            new_head[1] -= 1
        elif direction == "R":
            new_head[1] += 1

        new_head = tuple(new_head)

        if new_head[0] < 0 or new_head[0] >= self.height or new_head[1] < 0 or new_head[1] >= self.width:
            return -1

        if new_head in self.snake_set and new_head != self.snake[-1]:
            return -1

        if self.food_index < len(self.food) and new_head == tuple(self.food[self.food_index]):
            self.food_index += 1
        else:
            tail = self.snake.pop()
            self.snake_set.remove(tail)

        self.snake.insert(0, new_head)
        self.snake_set.add(new_head)

        return len(self.snake) - 1

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.

Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

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

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) == 0 or k > len(s):
            return 0
        n = len(s)
        result = 0
        
        for start in range(n):
            count_map = [0] * 26
            for end in range(start, n):
                count_map[ord(s[end]) - ord('a')] += 1
                if self.is_valid(count_map, k):
                    result = max(result, end - start + 1)
        
        return result
    
    def is_valid(self, count_map, k):
        count_letters = 0
        count_at_least_k = 0
        for count in count_map:
            if count > 0:
                count_letters += 1
            if count >= k:
                count_at_least_k += 1
        return count_letters == count_at_least_k

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

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

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


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

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

Задача: 1345. Jump Game IV
Сложность: hard

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

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

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

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

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

1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

class Solution:
    def minJumps(self, arr):
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] not in graph:
                graph[arr[i]] = []
            graph[arr[i]].append(i)

        curs = [0]
        visited = {0}
        step = 0

        while curs:
            nex = []

            for node in curs:
                if node == n - 1:
                    return step

                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                graph[arr[node]] = []

                if node + 1 < n and node + 1 not in visited:
                    visited.add(node + 1)
                    nex.append(node + 1)
                if node - 1 >= 0 and node - 1 not in visited:
                    visited.add(node - 1)
                    nex.append(node - 1)

            curs = nex
            step += 1

        return -1

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