Python | LeetCode

Задача: 948. Bag of Tokens Сложность: medium Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов. Пример:

Input: tokens = [100], power = 50

Output: 0

👨‍💻 Алгоритм: 1⃣Отсортировать массив tokens. Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов. Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore 2⃣Повторять следующие шаги, пока left не превысит right: Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет. Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет. Обновить максимальный счет, если текущий счет больше максимального. 3⃣Вернуть максимальный счет. 😎 Решение:

def bagOfTokensScore(tokens, power):
    tokens.sort()
    left, right = 0, len(tokens) - 1
    score, maxScore = 0, 0
    
    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            score += 1
            left += 1
            maxScore = max(maxScore, score)
        elif score > 0:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break
    
    return maxScore

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

Задача: 433. Minimum Genetic Mutation Сложность: medium Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'. Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке. Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией. Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой. Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1. Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк. Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:

from collections import deque

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        queue = deque([start])
        seen = set([start])
        steps = 0
        
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                
                if node == end:
                    return steps
                
                for c in "ACGT":
                    for i in range(len(node)):
                        neighbor = node[:i] + c + node[i+1:]
                        if neighbor not in seen and neighbor in bank:
                            queue.append(neighbor)
                            seen.add(neighbor)
            steps += 1
        
        return -1

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

Задача: 216. Combination Sum III Сложность: medium Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что: Используются только числа от 1 до 9. Каждое число используется не более одного раза. Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке. Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

👨‍💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []

        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                return

            for i in range(next_start, 9):
                comb.append(i + 1)
                backtrack(remain - i - 1, comb, i + 1)
                comb.pop()

        backtrack(n, [], 0)

        return results

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

Большая распродажа: скидки на серверы Dell, HPE В Сервер Молл выгодное предложение на серверы Dell, HPE предыдущих поколений — самое время для апгрейда и масштабирования. Модели серверов под любые задачи: 1С, базы данных, виртуализация, видеонаблюдение, файловое хранилище, VPN и иные нагрузки. Конфигурации — от бюджетных до некогда топов с двумя процессорами Intel Xeon Gold. Все серверы в наличии и готовы к отправке! Выберите готовый вариант или сконфигурируйте под свои задачи. Консультации в любом объёме. ⚡ Бесплатная Гарантия 5 лет ⚡Доставка по всей России = 0 руб ⚡Постпродажная поддержка Если вы ждали повод собрать инфраструктуру с нуля, масштабировать или заменить старую технику — он перед вами. Акция продлится, пока серверы есть в наличии ✅ Пишите в наш Чат или Звоните — 8 800 755-25-51 📞 Узнать цену #реклама 16+ servermall.ru О рекламодателе

Задача: 556. Next Greater Element III Сложность: medium Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм: Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1. Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1. Пример:

Input: n = 12
Output: 21

👨‍💻 Алгоритм: 1⃣Нахождение и перестановка цифр Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j. 2⃣Обратный порядок оставшихся цифр Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной. 3⃣Проверка результата и преобразование обратно в число Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число. 😎 Решение:

class Solution:
    def swap(self, s, i0, i1):
        if i0 == i1:
            return s
        s = list(s)
        s[i0], s[i1] = s[i1], s[i0]
        return ''.join(s)
    
    def permute(self, a, l, r):
        if l == r:
            self.list.append(a)
        else:
            for i in range(l, r + 1):
                a = self.swap(a, l, i)
                self.permute(a, l + 1, r)
                a = self.swap(a, l, i)
    
    def nextGreaterElement(self, n: int) -> int:
        s = str(n)
        self.list = []
        self.permute(s, 0, len(s) - 1)
        self.list.sort()
        if s in self.list:
            index = self.list.index(s)
            if index < len(self.list) - 1:
                result = int(self.list[index + 1])
                if result <= 2**31 - 1:
                    return result
        return -1

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

Конференция для блогеров ПОСТ РОСТ 12 сентября В самом начале сентября Яндекс собирает авторов контента на первую конференцию для блогеров! Что вас ждёт: — Выступления топ-экспертов о том, как блогеру расти и развивать свой контент — Спонтанный нетворкинг — Классные активности — Консультации специалистов по монетизации контента Участие бесплатное Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 914. X of a Kind in a Deck of Cards Сложность: easy Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае. Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

👨‍💻 Алгоритм: 1⃣Создать словарь для подсчета частоты каждого числа в массиве deck. 2⃣Найти наибольший общий делитель (НОД) всех частот. 3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы. 😎 Решение:

from collections import Counter
from math import gcd
from functools import reduce

def hasGroupsSizeX(deck):
    count = Counter(deck)
    freq_values = list(count.values())
    g = reduce(gcd, freq_values)
    return g > 1

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1182. Shortest Distance to Target Color Сложность: medium Дан массив colors, содержащий три цвета: 1, 2 и 3. Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1. Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

👨‍💻 Алгоритм: 1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы. 2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка. 3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее. 😎 Решение:

from collections import defaultdict
import bisect

class Solution:
    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        queryResults = []
        hashmap = defaultdict(list)

        for i, color in enumerate(colors):
            hashmap[color].append(i)

        for target, color in queries:
            if color not in hashmap:
                queryResults.append(-1)
                continue

            indexList = hashmap[color]
            insert = bisect.bisect_left(indexList, target)

            if insert == 0:
                queryResults.append(indexList[0] - target)
            elif insert == len(indexList):
                queryResults.append(target - indexList[-1])
            else:
                leftNearest = target - indexList[insert - 1]
                rightNearest = indexList[insert] - target
                queryResults.append(min(leftNearest, rightNearest))

        return queryResults

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 686. Repeated String Match Сложность: medium Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1. Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc". Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

👨‍💻 Алгоритм: 1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)). 2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1. 3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1. 😎 Решение:

class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:
        q = 1
        S = A
        while len(S) < len(B):
            S += A
            q += 1
        if B in S:
            return q
        if B in S + A:
            return q + 1
        return -1

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

Внимание ученики 1-9 класса и их родители! С 1 июня стартует бесплатная 3-х месячная программа по углубленному изучению школьных предметов с 1 по 4 класс, с 5 по 8 класс и с 9 по 11 класс от резидента Сколково. Программа предлагает подтянуть знания по основным предметам: — Математика: 83% учеников повышают оценку до 4 или 5 за 2 месяца — Подготовиться к контрольным и ВПР — Подготовка к ОГЭ и ЕГЭ без стресса — Русский язык: средний балл ВПР 87 при общешкольном показателе 65 — Английский: 72% учащихся переходят на уровень выше за 4 месяца Для участия достаточно заполнить заявку. Жмите "Записаться" Записаться #реклама 16+ mrqz.me О рекламодателе

Задача: 1332. Remove Palindromic Subsequences Сложность: easy Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s. Верните минимальное количество шагов, чтобы сделать данную строку пустой. Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной. Строка называется палиндромом, если она читается одинаково как вперед, так и назад. Пример:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

👨‍💻 Алгоритм: 1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг. 2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот). 3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом. 😎 Решение:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        if s == s[::-1]:
            return 1
        return 2

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

Задача: 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

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование! 🎉 Что нового: 🟢Анализ IT собеседований на основе 4500+ реальных интервью 🟢Вопросы из собеседований с вероятностью встречи 🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов 🟢Пример лучшего ответа 🟢Задачи из собеседований 🟢Тестовые задания 🟢Примеры собеседований 🟢Фильтрация всего контента по грейдам, компаниям 🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек 🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро) 🟢Автоотклики на HeadHunter 🟢Закрытое сообщество easyoffer 💎 Акция в честь открытия для первых 500 покупателей: 🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽) 🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 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 специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 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

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

Получите IT профессию с официальным ДОКУМЕНТОМ! Не просто курсы – а полноценное образование с дипломом о профессиональной переподготовке или удостоверением о повышении квалификации, внесенным в Росреестр! Выбирайте направление: -Web-разработчик -Инженер MikroTik -Специалист по AI и машинному обучению -Сетевой инженер -Linux-администратор -Python-программист -DevOps-инженер -Администратор Windows Server -Специалист по слаботочным сетям (СКС) Ваши гарантии: ✅Законный документ о квалификации ✅Право на ведение профдеятельности ✅Весомое преимущество при трудоустройстве ✅Поддержка ментора ✅Дистанционное обучение Инвестируйте в будущее – получите не только знания, но и официальную профессию! Перейти на сайт #реклама 16+ dms-it.ru О рекламодателе

Задача: №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

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