Python | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
الشبكة:8 965
المشتركون
-424 ساعات
-327 أيام
-10530 أيام
أرشيف المشاركات
8 962
Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium
Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.
Пример:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3👨💻 Алгоритм: 1⃣Создайте двумерный массив для хранения длин общих подмассивов. 2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива. 3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива. 😎 Решение:
def findLength(nums1, nums2):
dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
max_len = 0
for i in range(len(nums1) - 1, -1, -1):
for j in range(len(nums2) - 1, -1, -1):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i + 1][j + 1] + 1
max_len = max(max_len, dp[i][j])
return max_len8 962
🔥 Бесплатный интенсив по ChatGPT и созданию НЕЙРОСТРУДНИКОВ без опыта программирования🔥
Вы узнаете, как использовать ChatGPT в профессиональных целях, создавать нейросотрудников на заказ и зарабатывать на ИИ от 150.000р в месяц.
Простое понимание основ, без сложного кода!
Что будет на интенсиве?
🧬 Теория: как создаются нейро-сотрудники с GPT на Python
🧬 Практика: мы создадим нейро-консультанта, нейро-HR, нейро-маркетолога и др.
Интенсив - максимально простой и доступный, без какого-либо сложного программирования.
Ведущий интенсива - Senior AI-разработчик нейросетей с 2003 года и основатель Университета искусственного интеллекта - Дмитрий Романов.
🤖 Присоединяйтесь к нашему бесплатному интенсиву и разберитесь в этой увлекательной теме с нами!
8 962
Задача: 36. Valid Sudoku
Сложность: medium
Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам:
Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений.
Пример:
Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: true👨💻 Алгоритм: 1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков. 2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число: Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке. 3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело. Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true. 😎 Решение:
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
N = 9
rows = [set() for _ in range(N)]
cols = [set() for _ in range(N)]
boxes = [set() for _ in range(N)]
for r in range(N):
for c in range(N):
val = board[r][c]
if val == ".":
continue
if val in rows[r]:
return False
rows[r].add(val)
if val in cols[c]:
return False
cols[c].add(val)
idx = (r // 3) * 3 + c // 3
if val in boxes[idx]:
return False
boxes[idx].add(val)
return True8 962
Университет искусственного интеллекта приглашает
💰 Стоимость вебинара:
Бесплатно!
Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях.
💻 Программа вебинара:
1) Классификация входящих/выходящих из автобуса людей
2) Классификация отзывов на Tesla
3) Оценка выброса CO2 по параметрам машины
4) Прогнозирование тренда цены доллара
5) Сегментация изображения для робота-доставщика
6) Обнаружение людей без касок на стройке/производстве
7) Трекинг людей на видео
8) Распознавание речи
9) Генерация изображения с помощью Stable Diffusion
Хочешь отучиться на передовой научного прогресса? Тогда скорее регистрируйся!
Зарегистрироваться
#реклама 16+
neural-university.ru
О рекламодателе
8 962
Задача: 1015. Smallest Integer Divisible by K
Сложность: medium
Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.
Пример:
Input: k = 1 Output: 1👨💻 Алгоритм: 1⃣Использование остатка для нахождения числа с цифрами 1: Создайте переменную num и установите ее равной 1. Создайте переменную length и установите ее равной 1 для отслеживания длины числа. 2⃣Итеративное нахождение числа: Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k. Увеличивайте length на 1 в каждой итерации. Если в какой-то итерации num % k == 0, верните length. 3⃣Проверка бесконечного цикла: Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует. 😎 Решение:
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
num, length = 1, 1
seen = set()
while num % k != 0:
if num % k in seen:
return -1
seen.add(num % k)
num = (num * 10 + 1) % k
length += 1
return length8 962
Задача: 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 962
Мечтаешь стать дизайнером?
Начни с dsgn sense — мультисенсорной олимпиады по дизайну от Школы дизайна Центрального университета для учеников 10-11-х классов.
Познакомься с профессиями графического, продуктового и промышленного дизайнера! Реши кейс от компаний-партнеров и создай проект, в котором зрение, слух, осязание, вкус и обоняние станут основой уникального дизайн-решения.
Призеры и победители получат:
— Два проекта в портфолио.
— Финал в наукограде Дубне с бесплатным проживанием, питанием и насыщенной программой.
— Крутой мерч и призы от компаний.
— Шанс выиграть грант до 100% на обучение в бакалавриате ЦУ.
Тебе не нужны специальные навыки: достаточно любопытства и желания экспериментировать.
Регистрируйся до 16 февраля по ссылке:
Зарегистрироваться
Есть противопоказания. Посоветуйтесь с врачом.
#реклама 16+
event.cu.ru
О рекламодателе
8 962
Задача: 1271. Hexspeak
Сложность: easy
Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".
Пример:
Input: num = "257" Output: "IOI"👨💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:
def toHexString(num):
hex_str = hex(int(num))[2:].upper().replace('0', 'O').replace('1', 'I')
for char in hex_str:
if char not in 'ABCDEFIO':
return "ERROR"
return hex_str8 962
Задача: 997. Find the Town Judge
Сложность: easy
В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.
Пример:
Input: n = 2, trust = [[1,2]] Output: 2👨💻 Алгоритм: 1⃣Создание счетчиков доверия: Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку. 2⃣Подсчет доверия: Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют. 3⃣Проверка условий судьи: Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1. 😎 Решение:
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
if not trust and n == 1:
return 1
trust_count = [0] * (n + 1)
trusted_by = [0] * (n + 1)
for a, b in trust:
trust_count[a] += 1
trusted_by[b] += 1
for i in range(1, n + 1):
if trust_count[i] == 0 and trusted_by[i] == n - 1:
return i
return -18 962
Задача: 1243. Array Transformation
Сложность: easy
Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.
Пример:
Input: arr = [6,2,3,4] Output: [6,3,3,4]👨💻 Алгоритм: 1⃣Инициализация нового массива с такими же значениями, как у исходного массива. Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться. 2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей. Если элемент меньше своего левого и правого соседей, увеличиваем его. Если элемент больше своего левого и правого соседей, уменьшаем его. 3⃣Первый и последний элементы массива остаются неизменными. 😎 Решение:
def transformArray(arr):
while True:
new_arr = arr[:]
changed = False
for i in range(1, len(arr) - 1):
if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
new_arr[i] += 1
changed = True
elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
new_arr[i] -= 1
changed = True
if not changed:
break
arr = new_arr
return arr8 962
Реклама для бизнеса любого уровня в Яндекс Директе
Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌
Начните прямо сейчас ⚡
Зарегистрироваться
#реклама
direct.yandex.ru
О рекламодателе
8 962
Задача: 542. 01 Matrix
Сложность: medium
Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.
Расстояние между двумя соседними ячейками равно 1.
Пример:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]]👨💻 Алгоритм: 1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen. 2⃣Выполните BFS: Пока очередь не пуста, извлекайте текущие row, col, steps из очереди. Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen. 3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix. 😎 Решение:
from collections import deque
class Solution:
def __init__(self):
self.m = 0
self.n = 0
self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def updateMatrix(self, mat):
self.m = len(mat)
self.n = len(mat[0])
matrix = [[0] * self.n for _ in range(self.m)]
seen = [[False] * self.n for _ in range(self.m)]
queue = deque()
for row in range(self.m):
for col in range(self.n):
matrix[row][col] = mat[row][col]
if matrix[row][col] == 0:
queue.append((row, col, 0))
seen[row][col] = True
while queue:
row, col, steps = queue.popleft()
for dr, dc in self.directions:
nextRow, nextCol = row + dr, col + dc
if self.valid(nextRow, nextCol) and not seen[nextRow][nextCol]:
seen[nextRow][nextCol] = True
queue.append((nextRow, nextCol, steps + 1))
matrix[nextRow][nextCol] = steps + 1
return matrix
def valid(self, row, col):
return 0 <= row < self.m and 0 <= col < self.n8 962
Бесплатный курс по дизайну: веб, графический и UX/UI
Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma!
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Этот курс для тебя, если ты:
✅ мечтаешь о новой профессии в digital, но не знаешь, с чего начать;
✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества;
✅ полный новичок и хочешь систему, а не хаос;
✅ хочешь начать зарабатывать удалённо.
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
8 962
Задача: 655. Print Binary Tree
Сложность: medium
Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.
Пример:
Input: root = [1,2] Output: [["","1",""], ["2","",""]]👨💻 Алгоритм: 1⃣Найдите высоту дерева и определите размер матрицы (m x n). 2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла. 3⃣Верните заполненную матрицу. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findHeight(root):
if not root:
return -1
return 1 + max(findHeight(root.left), findHeight(root.right))
def fill(res, root, r, c, height):
if not root:
return
res[r][c] = str(root.val)
if root.left:
fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height)
if root.right:
fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height)
def printTree(root):
height = findHeight(root)
m = height + 1
n = (1 << (height + 1)) - 1
res = [["" for _ in range(n)] for _ in range(m)]
fill(res, root, 0, (n - 1) // 2, height)
return res8 962
Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy
Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).
Пример:
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value,
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. class Solution:
def maxProduct(self, nums: List[int]) -> int:
biggest = 0
secondBiggest = 0
for num in nums:
if num > biggest:
secondBiggest = biggest
biggest = num
elif num > secondBiggest:
secondBiggest = num
return (biggest - 1) * (secondBiggest - 1)8 962
Ищу желающих заполнять карточки товаров на ВБ!
Работа полностью на удаленке с зп до150 000 рублей в месяц.
Без опыта, нужен только телефон, занятость 3-6 часов в день.
Всему обучат на бесплатном курсе и после возьму на работу:
✅ 3 дня уроков по 30 минут
✅ Домашки с проверкой и оплатой бонусами
✅ Плачу 10 тыс за каждую выполненную домашку
Все кто пройдет курс, получат сертификат от школы с образовательной лицензией.
⚡ Набор заканчивается завтра.
👍 Для регистрации жмите кнопку "Зарегистрироваться":
Зарегистрироваться
#реклама 16+
course.wildmanager.ru
О рекламодателе
8 962
Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium
Даны два целых числа n и k, верните массив всех целых чисел длины n, где разница между каждыми двумя последовательными цифрами равна k. Вы можете вернуть ответ в любом порядке.
Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.
Пример:
Input: n = 3, k = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number, because it has leading zeroes.👨💻 Алгоритм: 1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми. 2⃣Инициализируйте список очередей начальными цифрами от 1 до 9. 3⃣Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k. 😎 Решение:
class Solution:
def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
if N == 1:
return list(range(10))
queue = list(range(1, 10))
for _ in range(N - 1):
next_queue = []
for num in queue:
tail_digit = num % 10
next_digits = {tail_digit + K, tail_digit - K}
for next_digit in next_digits:
if 0 <= next_digit < 10:
next_queue.append(num * 10 + next_digit)
queue = next_queue
return queue8 962
Задача: 498. Diagonal Traverse
Сложность: medium
Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.
Пример:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9]👨💻 Алгоритм: 1⃣Инициализация и подготовка Проверьте, пуста ли матрица. Инициализируйте переменные для хранения размеров матрицы. Создайте массив result для хранения окончательных результатов и временный список intermediate для промежуточных значений диагоналей. 2⃣Итерация по диагоналям Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы. 3⃣Обработка диагоналей Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result. 😎 Решение:
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
if not mat or not mat[0]:
return []
N, M = len(mat), len(mat[0])
result = []
for d in range(N + M - 1):
intermediate = []
r = 0 if d < M else d - M + 1
c = d if d < M else M - 1
while r < N and c > -1:
intermediate.append(mat[r][c])
r += 1
c -= 1
if d % 2 == 0:
result.extend(intermediate[::-1])
else:
result.extend(intermediate)
return result8 962
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
8 962
Задача: 220. Contains Duplicate III
Сложность: hard
Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.
Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.
Верните true, если такая пара существует, или false в противном случае.
Пример:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 Output: true Explanation: We can choose (i, j) = (0, 3). We satisfy the three conditions: i != j --> 0 != 3 abs(i - j) <= indexDiff --> abs(0 - 3) <= 3 abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0👨💻 Алгоритм: 1️⃣Инициализация и вычисление корзин: Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w. 2️⃣Итерация и проверка корзин: Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна. 3️⃣Завершение: Если ни одна пара "почти дубликатов" не найдена, вернуть false. 😎 Решение:
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0: return False
buckets = {}
w = t + 1
for i in range(len(nums)):
bucket = nums[i] // w if nums[i] >= 0 else (nums[i] + 1) // w - 1
if bucket in buckets: return True
if bucket - 1 in buckets and abs(nums[i] - buckets[bucket - 1]) < w: return True
if bucket + 1 in buckets and abs(nums[i] - buckets[bucket + 1]) < w: return True
buckets[bucket] = nums[i]
if i >= k:
del buckets[nums[i - k] // w if nums[i - k] >= 0 else (nums[i - k] + 1) // w - 1]
return False