Python | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
شبکه:8 969
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-297 روز
-10530 روز
آرشیو پست ها
8 966
Не грузится? Понимаем.
Бесплатный мессенджер для вашей компании - Битрикс24.
Личные и групповые чаты, видеозвонки, каналы и нейросеть. Всё привычно и удобно.
Начните работать на бесплатном тарифе уже сейчас.
Узнать больше
#реклама 16+
bitrix24.ru
О рекламодателе
8 966
Задача: 634. Find the Derangement of An Array
Сложность: medium
В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3 Output: 2👨💻 Алгоритм: 1⃣Инициализация массива для хранения результатов Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:
def countDerangements(n: int) -> int:
MOD = 10**9 + 7
if n == 0:
return 1
if n == 1:
return 0
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 0
for i in range(2, n + 1):
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
return dp[n]8 966
Задача: 918. Maximum Sum Circular Subarray
Сложность: medium
Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.
Пример:
Input: nums = [1,-2,3,-2] Output: 3👨💻 Алгоритм: 1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане. 2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива. 3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные). 😎 Решение:
def maxSubarraySumCircular(nums):
def kadane(arr):
current_sum = max_sum = arr[0]
for num in arr[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
max_kadane = kadane(nums)
total_sum = sum(nums)
min_kadane = kadane([-num for num in nums])
return max(max_kadane, total_sum + min_kadane if total_sum + min_kadane != 0 else max_kadane)8 966
Задача: 811. Subdomain Visit Count
Сложность: medium
Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".
Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.
Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.
Пример:
Input: cpdomains = ["9001 discuss.leetcode.com"] Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"] Explanation: We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.👨💻 Алгоритм: 1⃣Следуем указаниям из условия задачи. 2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y. 3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split. 😎 Решение:
from collections import Counter
class Solution:
def subdomainVisits(self, cpdomains):
ans = Counter()
for domain in cpdomains:
count, domain = domain.split()
count = int(count)
frags = domain.split('.')
for i in range(len(frags)):
ans[".".join(fr8 966
Получи грант до 1,35 млн руб. на обучение в магистратуре
Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой?
Поступай в магистратуру Центрального университета!
— 4 офлайн программы по востребованным направлениям ИТ
— 2 онлайн-программы: машинное обучение и продуктовый менеджмент
— 550 грантов до 75%
— Вечерние занятия и учеба по выходным — удобно совмещать с работой
— Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса
— Возможность стажировок и трудоустройства в ведущих компаниях
— Государственный диплом за 2 года
Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас!
Зарегистрироваться
#реклама 16+
cu.ru
О рекламодателе
8 966
Задача: 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> на основе массива флагов. 😎 Решение:
def addBoldTags(keywords, s):
n = len(s)
bold = [False] * n
for word in keywords:
start = s.find(word)
while start != -1:
for i in range(start, start + len(word)):
bold[i] = True
start = s.find(word, start + 1)
result = []
i = 0
while i < n:
if bold[i]:
result.append("<b>")
while i < n and bold[i]:
result.append(s[i])
i += 1
result.append("</b>")
else:
result.append(s[i])
i += 1
return "".join(result)8 966
Хочешь начать карьеру в ИТ на оплачиваемой стажировке?
Присоединяйся к ИТ-лагерю Т1 для студентов вузов технических и ИТ-специальностей. Теперь в обновлённом формате: ещё больше практики, доступ к платформам Т1, а участие — оплачивается и оформляется как стажировка.
За 2,5 месяца вместе с проектной командой ты пройдешь полный цикл создания ИТ-продукта: от идеи до разработки прототипа и финальной защиты. Превратить идею в проект помогут мастер-классы, общение с экспертами и погружение в процессы Т1.
Направления подготовки:
✅ ручное тестирование;
✅ прикладное администрирование (DevOps);
✅ системный анализ;
✅ фронтенд-разработка (React);
✅ бэкэнд-разработка (Java).
Подай заявку до 30 июня! Старт — в июле.
Узнать больше
#реклама 16+
career.t1.ru
О рекламодателе
8 966
Задача: 65. Valid Number
Сложность: hard
Учитывая строку s, определите, является ли s валидным числом.
Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".
Формально, валидное число определяется с использованием одного из следующих определений:
Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.
Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:
Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.
Цифры определяются как одна или более цифр.
Пример:
Input: s = "0" Output: true👨💻 Алгоритм: 1️⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true. 2️⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число. 3️⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры. 😎 Решение:
class Solution:
def isNumber(self, s: str) -> bool:
seen_digit = seen_exponent = seen_dot = False
for i, c in enumerate(s):
if c.isdigit():
seen_digit = True
elif c in ["+", "-"]:
if i > 0 and s[i - 1] != "e" and s[i - 1] != "E":
return False
elif c in ["e", "E"]:
if seen_exponent or not seen_digit:
return False
seen_exponent = True
seen_digit = False
elif c == ".":
if seen_dot or seen_exponent:
return False
seen_dot = True
else:
return False
return seen_digit8 966
Онлайн-магистратура для IT: ИТМО, МИФИ + Яндекс
Программы онлайн-магистратуры ИТМО и МИФИ в партнёрстве с Яндексом. Актуальные знания, практическое обучение и гибкий график. Учитесь, совмещая с работой. Доступна господдержка оплаты, отсрочка от армии
Перейти на сайт
#реклама 16+
practicum.yandex.ru
О рекламодателе
8 966
Задача: 1533. Find the Index of the Large Integer
Сложность: medium
У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:
int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].
int length(): Возвращает размер массива.
Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.
Верните индекс массива arr, который содержит наибольший элемент.
Пример:
Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.class Solution:
def getIndex(self, reader: 'ArrayReader') -> int:
left = 0
length = reader.length()
while length > 1:
length //= 2
cmp = reader.compareSub(left, left + length - 1, left + length, left + 2 * length - 1)
if cmp == 0:
return left + 2 * length
if cmp < 0:
left += length
return left8 966
Выигрывайте мечты с Черноголовкой!
Покупайте Колу и Лимонады Черноголовка в Магните
Выигрывайте 1 000 000 р. и другие призы
Узнать больше
#реклама
sitelinker.prod.ya.magnit.ru
О рекламодателе
8 966
Задача: 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⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным. Вернуть количество удаленных столбцов. 😎 Решение:
def minDeletionSize(strs):
n = len(strs)
m = len(strs[0])
delete_count = [False] * m
def is_sorted():
for i in range(n - 1):
for j in range(m):
if delete_count[j]:
continue
if strs[i][j] > strs[i + 1][j]:
return False
if strs[i][j] < strs[i + 1][j]:
break
return True
while not is_sorted():
for j in range(m):
if delete_count[j]:
continue
for i in range(n - 1):
if strs[i][j] > strs[i + 1][j]:
delete_count[j] = True
break
if delete_count[j]:
break
return sum(delete_count)8 966
Задача: 927. Three Equal Parts
Сложность: hard
Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.
Пример:
Input: arr = [1,0,1,0,1] Output: [0,3]👨💻 Алгоритм: 1⃣Подсчитать количество единиц в массиве. 2⃣Если количество единиц не делится на три, вернуть [-1, -1]. Найти индексы начала каждой части, игнорируя ведущие нули. Использовать эти индексы для проверки, могут ли три части быть одинаковыми. 3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1]. 😎 Решение:
def threeEqualParts(arr):
ones = sum(arr)
if ones % 3 != 0:
return [-1, -1]
if ones == 0:
return [0, len(arr) - 1]
part_ones = ones // 3
first = second = third = cnt = 0
for i, val in enumerate(arr):
if val == 1:
if cnt == 0:
first = i
elif cnt == part_ones:
second = i
elif cnt == 2 * part_ones:
third = i
cnt += 1
while third < len(arr) and arr[first] == arr[second] == arr[third]:
first += 1
second += 1
third += 1
if third == len(arr):
return [first - 1, second]
return [-1, -1]8 966
Вебинар 10.06.2026: про быстрый запуск ИИ-моделей в прод
Приглашаем ИТ-специалистов, ML-инженеров и всех, кто внедряет ИИ в компаниях!
Запуск ИИ-моделей может превратиться в головную боль: нужно собирать стек, нанимать DevOps/ML-инженеров, вручную управлять серверами с GPU и переплачивать за простой. А мониторинг показывает только «железо», но не поведение самой модели как сервиса.
На вебинаре расскажем про готовую среду для запуска моделей — Inference Platform, чтобы вы могли перейти от настройки инфраструктуры к использованию моделей.
Вы узнаете:
• Как использовать ваши модели без DevOps инженеров
• Как экономично работать с переменной нагрузкой
• Как запускать большие модели для агентских сценариев
• Как разработчик AI-ассистента развертывает модели и масштабирует ресурсы без простоя
Приходите!
Записаться
#реклама 16+
my.mts-link.ru
О рекламодателе
8 966
Задача: 161. One Edit Distance
Сложность: medium
Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.
Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.
Пример:
Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.👨💻 Алгоритм: 1️⃣Проверка длины строк: Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку. Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false. 2️⃣Сравнение строк посимвольно: Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t. Если находите различающийся символ: Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false. Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false 3️⃣Проверка на возможное добавление символа в конец s: Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true. В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования. 😎 Решение:
class Solution:
def isOneEditDistance(self, s: "str", t: "str") -> "bool":
ns, nt = len(s), len(t)
if ns > nt:
return self.isOneEditDistance(t, s)
if nt - ns > 1:
return False
for i in range(ns):
if s[i] != t[i]:
if ns == nt:
return s[i + 1 :] == t[i + 1 :]
else:
return s[i:] == t[i + 1 :]
return ns + 1 == nt8 966
Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy
Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.
Пример:
Input: nums = [12,345,2,6,7896] Output: 2 Explanation: 12 contains 2 digits (even number of digits). 345 contains 3 digits (odd number of digits). 2 contains 1 digit (odd number of digits). 6 contains 1 digit (odd number of digits). 7896 contains 4 digits (even number of digits). Therefore only 12 and 7896 contain an even number of digits.👨💻 Алгоритм: 1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false. 2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0. 3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount. 😎 Решение:
class Solution:
def hasEvenDigits(self, num: int) -> bool:
digitCount = 0
while num > 0:
digitCount += 1
num //= 10
return (digitCount & 1) == 0
def findNumbers(self, nums: list[int]) -> int:
evenDigitCount = 0
for num in nums:
if self.hasEvenDigits(num):
evenDigitCount += 1
return evenDigitCount8 966
Большая летняя распродажа курсов на Stepik
На смене сезонов всегда появляется немного больше времени для себя: весенние дедлайны постепенно остаются позади, дни становятся светлее, а планы – легче.
Чтобы помочь вам провести его с пользой – Stepik запускает сезонную распродажу онлайн-курсов. Она пройдет с 27 мая по 9 июня 2026 года и распространяется на многие курсы, представленные на платформе 👌
Вы можете подтянуть свои знания в программировании, дизайне, маркетинге, выучить английский язык, научиться готовить роллы и играть на гитаре с летней легкостью ❤️
Переходите в наш каталог распродажи найдите походящий курс на любую тему.
Учитесь новому!
Посмотреть каталог
#реклама 16+
stepik.org
О рекламодателе
8 966
Задача: 1041. Robot Bounded In Circle
Сложность: medium
На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.
Пример:
Input: instructions = "GGLLGG" Output: true👨💻 Алгоритм: 1⃣Понимание поведения робота: Мы анализируем, как робот движется в пределах одной серии команд. Если он вернется в начальную точку или изменит направление после выполнения всех команд, значит, он будет двигаться по замкнутой траектории, что соответствует условию задачи. 2⃣Изменение направления: Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0). 3⃣Обработка команд: Пройдите по всем командам и обновите позицию робота и направление, в котором он движется. Проверка состояния робота: После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории. 😎 Решение:
def isRobotBounded(instructions):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
x = y = 0
direction = 0
for instruction in instructions:
if instruction == 'G':
x += directions[direction][0]
y += directions[direction][1]
elif instruction == 'L':
direction = (direction + 3) % 4
elif instruction == 'R':
direction = (direction + 1) % 4
return (x == 0 and y == 0) or direction != 08 966
Яндекс Музыка до 360 дней бесплатно
Яндекс Музыка для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Слушать
#реклама 18+
music.yandex.ru
О рекламодателе
8 966
Задача: 1035. Uncrossed Lines
Сложность: medium
Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.
Пример:
Input: nums1 = [1,4,2], nums2 = [1,2,4] Output: 2👨💻 Алгоритм: 1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS): Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2. 2⃣Построение таблицы динамического программирования: Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1]. Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым. 3⃣Заполнение таблицы динамического программирования: Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1]. Результат будет находиться в ячейке dp[nums1.length][nums2.length]. 😎 Решение:
def maxUncrossedLines(nums1, nums2):
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]