Python | LeetCode
Открыть в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Больше
8 922
Подписчики
-524 часа
-477 дней
-12930 дней
Архив постов
8 922
#medium
Задача: 90. Subsets II
Дан массив целых чисел nums, который может содержать повторяющиеся элементы. Верните все возможные подмножества (степенной набор).
Результирующий набор не должен содержать дублирующихся подмножеств. Возвращаемый результат может быть в любом порядке.
Пример:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]👨💻 Алгоритм: 1️⃣Отсортируйте массив nums. Сортировка необходима для того, чтобы все сгенерированные подмножества также были отсортированы. Это помогает идентифицировать дубликаты. 2️⃣Инициализируйте maxNumberOfSubsets максимальным количеством подмножеств, которые можно сгенерировать, т.е., 2 в степени n. Инициализируйте множество, seen, типа string, для хранения всех сгенерированных подмножеств. Добавление всех отсортированных подмножеств в множество дает нам возможность отловить любые дублирующие подмножества. 3️⃣Итерируйте от 0 до maxNumberOfSubsets - 1. Установленные биты в двоичном представлении subsetIndex указывают на позицию элементов в массиве nums, которые присутствуют в текущем подмножестве. Инициализируйте строку hashcode, которая будет хранить список чисел в текущемSubset в виде строки, разделенной запятыми. hashcode необходим для уникальной идентификации каждого подмножества с помощью множества. Выполните внутренний цикл for от j = 0 до n - 1, чтобы проверить позицию установленных битов в subsetIndex. Если на позиции j установлен бит, добавьте nums[j] в текущее подмножество currentSubset и добавьте nums[j] в строку hashcode. Добавьте текущее подмножество currentSubset в seen и в список подмножеств, если сгенерированный hashcode еще не в seen. Верните подмножества. 😎 Решение:
class Solution:
def subsetsWithDup(self, nums):
n = len(nums)
nums.sort()
maxNumberOfSubsets = 2**n
seen = set()
subsets = []
for subsetIndex in range(maxNumberOfSubsets):
currentSubset = []
hashcode = ""
for j in range(n):
mask = 2**j
isSet = mask & subsetIndex
if isSet != 0:
currentSubset.append(nums[j])
hashcode += str(nums[j]) + ","
if hashcode not in seen:
subsets.append(currentSubset)
seen.add(hashcode)
return subsets8 922
Такси для бизнеса. Яндекс Go
Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go
Узнать больше
#реклама
business.go.yandex
О рекламодателе
8 922
#medium
Задача: 89. Gray Code
Последовательность Грея с n-битами — это последовательность из 2^n целых чисел, где:
1. Каждое число находится в включающем диапазоне от 0 до 2^n - 1,
2. Первое число равно 0,
3. Каждое число встречается в последовательности не более одного раза,
4. Двоичное представление каждой пары соседних чисел отличается ровно на один бит,
5. Двоичное представление первого и последнего чисел отличается ровно на один бит.
Для заданного числа n возвращается любая допустимая последовательность Грея с n-битами.
Пример:
Input: n = 2 Output: [0,1,3,2] Explanation: The binary representation of [0,1,3,2] is [00,01,11,10]. - 00 and 01 differ by one bit - 01 and 11 differ by one bit - 11 and 10 differ by one bit - 10 and 00 differ by one bit [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01]. - 00 and 10 differ by one bit - 10 and 11 differ by one bit - 11 and 01 differ by one bit - 01 and 00 differ by one bit👨💻 Алгоритм: 1️⃣Инициализируйте список результатов для хранения последовательности решений. Добавьте 0 в список перед вызовом вспомогательного метода, так как все последовательности Грея начинаются с 0. 2️⃣Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения. Начните с числа 0. В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов. 3️⃣Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent. Продолжайте поиск с next. Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения. Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск. При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true. Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false. 😎 Решение:
class Solution:
def grayCode(self, n: int):
result = [0]
isPresent = {0}
self.grayCodeHelper(result, n, isPresent)
return result
def grayCodeHelper(self, result, n, isPresent):
if len(result) == (1 << n):
return True
current = result[-1]
for i in range(n):
nextNum = current ^ (1 << i)
if nextNum not in isPresent:
isPresent.add(nextNum)
result.append(nextNum)
if self.grayCodeHelper(result, n, isPresent):
return True
isPresent.remove(nextNum)
result.pop()
return False8 922
#easy
Задача: 88. Merge Sorted Array
Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.
Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.
Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.
Пример:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.👨💻 Алгоритм: 1️⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1. 2️⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1. Инициализируйте указатель для чтения p1 в начале nums1Copy. Инициализируйте указатель для чтения p2 в начале nums2. 3️⃣Инициализируйте указатель для записи p в начале nums1. Пока p все еще находится внутри nums1: Если nums1Copy[p1] существует и меньше или равно nums2[p2]: Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1. Иначе Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1. Увеличьте p на 1. 😎 Решение:
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
nums1_copy = nums1[:m]
p1 = 0
p2 = 0
for p in range(n + m):
if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
nums1[p] = nums1_copy[p1]
p1 += 1
else:
nums1[p] = nums2[p2]
p2 += 18 922
Для тех кто изучает любой язык программирования с нуля или уже имеет опыт, кто ищет поддержку и напарника на безвозмездной основе добавляйтесь и давайте помогать друг другу в освоении программирования.
Группа https://t.me/lp2024it
8 922
Бакалавриат и специалитет Президентской академии!
✅ Важное для абитуриентов!
🎓 🎓Хотите стать студентом одного из лучших университетов страны? Тогда не упустите шанс поступить на программы бакалавриата и специалитета в Президентскую академию (РАНХиГС).
На выбор более 100 программ обучения, стажировки и практики в органах государственной власти и крупных коммерческих компаниях, участие в реальных проектах во время обучения, стипендии и общежития.
Создавайте будущее страны вместе с РАНХиГС.
Подробности о поступлении и об Академии вы найдете на нашем сайте.
Успейте подать заявку!
Узнать больше
#реклама
ranepa.ru
О рекламодателе
8 922
#hard
Задача: 87. Scramble String
Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:
1. Если длина строки равна 1, остановиться.
2. Если длина строки больше 1, выполнить следующее:
- Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y.
- Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x.
- Применить шаг 1 рекурсивно к каждой из двух подстрок x и y.
Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false.
Пример:
Input: s1 = "great", s2 = "rgeat" Output: true Explanation: One possible scenario applied on s1 is: "great" --> "gr/eat" // divide at random index. "gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order. "gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them. "g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order. "r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t". "r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order. The algorithm stops now, and the result string is "rgeat" which is s2. As one possible scenario led s1 to be scrambled to s2, we return true.👨💻 Алгоритм: 1️⃣- Итерируйте i от 0 до n-1. - Итерируйте j от 0 до n-1. - Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования). 2️⃣- Итерируйте length от 2 до n. - Итерируйте i от 0 до n + 1 - length. - Итерируйте j от 0 до n + 1 - length. 3️⃣- Итерируйте newLength от 1 до length - 1. - Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true. - Верните dp[n][0][0]. 😎 Решение:
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n = len(s1)
dp = [
[[False for j in range(n)] for i in range(n)] for l in range(n + 1)
]
for i in range(n):
for j in range(n):
dp[1][i][j] = s1[i] == s2[j]
for length in range(2, n + 1):
for i in range(n + 1 - length):
for j in range(n + 1 - length):
for new_length in range(1, length):
dp1 = dp[new_length][i]
dp2 = dp[length - new_length][i + new_length]
dp[length][i][j] |= dp1[j] and dp2[j + new_length]
dp[length][i][j] |= (
dp1[j + length - new_length] and dp2[j]
)
return dp[n][0][0]8 922
#medium
Задача: 86. Partition List
Дана голова связного списка и значение x. Разделите его так, чтобы все узлы с значениями меньше x находились перед узлами с значениями, равными или большими x.
Необходимо сохранить исходный относительный порядок узлов в каждой из двух частей.
Пример:
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]👨💻 Алгоритм: 1️⃣Инициализация указателей: Создайте два указателя before и after, каждый из которых инициализирован временным (dummy) узлом. Это упрощает управление границами списка, минимизируя необходимость проверок условий в коде. 2️⃣Итерация по исходному связному списку: Перемещайте каждый узел в список before, если его значение меньше x, и в список after, если его значение равно или больше x. Это сохраняет относительный порядок узлов в каждой из двух частей. 3️⃣Соединение списков: После обработки всех узлов исходного списка, соедините списки before и after. Удалите временные узлы в начале каждого списка перед их соединением, чтобы исключить их из итогового связного списка. 😎 Решение:
class Solution(object):
def partition(self, head: ListNode, x: int) -> ListNode:
before = before_head = ListNode(0)
after = after_head = ListNode(0)
while head:
if head.val < x:
before.next = head
before = before.next
else:
after.next = head
after = after.next
head = head.next
after.next = None
before.next = after_head.next
return before_head.next8 922
Серверное Оборудование Купить БУ в Москве с Гарантией!
Компания WestComp продает бу серверное оборудование вендора HPE в поколении Gen8 Gen9 и Gen10 всех линеек в отличном состоянии! Купить серверы можно с НДС без повышения цены и в лизинг. Доступна услуга Colocation в ЦОД TIER III Москвы! Можно выгодно купить сервер HP Proliant DL или BL, СХД HPE 3PAR, HPE Synergy, HPE BladeSystem, HPE Apollo любой конфигурации с гарантией до 5 лет! Цены в 10 раз ниже чем на новое оборудование!
Выбрать
#реклама
westcomp.ru
О рекламодателе
8 922
#hard
Задача: 85. Maximal Rectangle
Дана бинарная матрица размером rows x cols, заполненная 0 и 1. Найдите наибольший прямоугольник, содержащий только 1, и верните его площадь.
Пример:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.👨💻 Алгоритм: 1️⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'. 2️⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea). 3️⃣Применение алгоритма для каждой точки ввода для глобального максимума: Преобразуя входные данные в набор гистограмм, где каждый столбец является новой гистограммой, мы вычисляем максимальную площадь для каждой гистограммы. 😎 Решение:
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
maxarea = 0
dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == "0":
continue
width = dp[i][j] = dp[i][j - 1] + 1 if j else 1
for k in range(i, -1, -1):
width = min(width, dp[k][j])
maxarea = max(maxarea, width * (i - k + 1))
return maxarea8 922
Пикник для ИТ-специалистов в Коломенском
Отдохните в кругу опытных ИТ-специалистов. Будут лекции, музыка, мастер-классы, интерактив — и все это в один день. Ждем вас 17.08.
Зарегистрироваться
#реклама
it-picnic.ru
О рекламодателе
8 922
#hard
Задача: 84. Largest Rectangle in Histogram
Дан массив целых чисел heights, представляющий высоту столбцов гистограммы, где ширина каждого столбца равна 1. Верните площадь наибольшего прямоугольника в гистограмме.
Пример:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.👨💻 Алгоритм: 1️⃣Введение в проблему: Прежде всего, следует учитывать, что высота прямоугольника, образованного между любыми двумя столбиками, всегда будет ограничена высотой самого низкого столбика, находящегося между ними. Это можно понять, взглянув на рисунок ниже. 2️⃣Описание метода: Таким образом, мы можем начать с рассмотрения каждой возможной пары столбиков и нахождения площади прямоугольника, образованного между ними, используя высоту самого низкого столбика между ними в качестве высоты и расстояние между ними в качестве ширины прямоугольника. 3️⃣Вычисление максимальной площади: Таким образом, мы можем найти требуемый прямоугольник с максимальной площадью. 😎 Решение:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
max_area = 0
for i in range(len(heights)):
for j in range(i, len(heights)):
min_height = inf
for k in range(i, j + 1):
min_height = min(min_height, heights[k])
max_area = max(max_area, min_height * (j - i + 1))
return max_area8 922
#easy
Задача: 83. Remove Duplicates from Sorted List
Дана голова отсортированного связного списка. Удалите все дубликаты таким образом, чтобы каждый элемент появлялся только один раз. Верните также отсортированный связный список.
Пример:
Input: head = [1,1,2] Output: [1,2]👨💻 Алгоритм: 1️⃣Это простая задача, которая проверяет вашу способность манипулировать указателями узлов списка. Поскольку входной список отсортирован, мы можем определить, является ли узел дубликатом, сравнив его значение с значением следующего узла в списке. 2️⃣Если узел является дубликатом, мы изменяем указатель next текущего узла так, чтобы он пропускал следующий узел и напрямую указывал на узел, следующий за следующим. 3️⃣Это позволяет исключить дубликаты из списка, продвигаясь вперёд по списку и корректируя связи между узлами для сохранения только уникальных элементов. 😎 Решение:
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
current = head
while current is not None and current.next is not None:
if current.next.val == current.val:
current.next = current.next.next
else:
current = current.next
return head8 922
👨💻 Нужен человек для создания постов в сети каналов Leetcode. Работа оплачивается. Писать сюда
8 922
Виртуальный сервер в аренду в Турции или России.
Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки.
- Бесплатная миграция инфраструктуры в Турцию
- Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро.
- Храните резервные копии данных за рубежом для минимизации рисков
- Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой
- Доступность сервиса — от 99,982% SLA
- Дата центры Tier III в России и Турции
- Почасовой биллинг и постоплата
Подключите услугу сегодня со скидкой 50% на инфраструктуру.
Подать заявку
#реклама
cloud4y.ru
О рекламодателе
8 922
#medium
Задача: 82. Remove Duplicates from Sorted List II
Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список.
Пример:
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]👨💻 Алгоритм: 1️⃣Инициализация "стража" и предшественника: Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены. Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж. 2️⃣Проход по списку с проверкой на дубликаты: Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val. Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов. 3️⃣Переход к следующему узлу и возврат результата: Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел. Двигаем указатель head на следующий узел в списке. После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов. 😎 Решение:
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
sentinel = ListNode(0, head)
pred = sentinel
while head:
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
pred.next = head.next
else:
pred = pred.next
head = head.next
return sentinel.next8 922
#medium
Задача: 81. Search in Rotated Sorted Array II
В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].
Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.
Необходимо сократить количество операций поиска настолько, насколько это возможно.
Пример:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true👨💻 Алгоритм: 1️⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска. 2️⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске: Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end]. Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid). Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска. Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска. 3️⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно. 😎 Решение:
class Solution:
def search(self, nums, target):
n = len(nums)
if n == 0:
return False
end = n - 1
start = 0
while start <= end:
mid = start + (end - start) // 2
if nums[mid] == target:
return True
if not self.isBinarySearchHelpful(nums, start, nums[mid]):
start += 1
continue
pivotArray = self.existsInFirst(nums, start, nums[mid])
targetArray = self.existsInFirst(nums, start, target)
if pivotArray ^ targetArray:
if pivotArray:
start = mid + 1
else:
end = mid - 1
else:
if nums[mid] < target:
start = mid + 1
else:
end = mid - 1
return False
def isBinarySearchHelpful(self, nums, start, element):
return nums[start] != element
def existsInFirst(self, nums, start, element):
return nums[start] <= element8 922
IT аутсорсинг в СПб! Обслуживание серверов и оргтехники!
АйТи аутсорсинг в СПб! Сертифицированные специалисты! Опытная команда IT специалистов!
Сертификаты Microsoft! CISCO Mikrotik! 12 лет на рынке!
Перейти на сайт
#реклама
svcnet.ru
О рекламодателе
8 922
#medium
Задача: 80. Remove Duplicates from Sorted Array II
Дан массив целых чисел nums, отсортированный в неубывающем порядке. Удалите из него некоторые дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз. Относительный порядок элементов должен быть сохранён.
Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.
Верните k после размещения итогового результата в первые k слотов массива nums.
Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).
Пример:
Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_] Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).👨💻 Алгоритм: 1️⃣Инициализация переменных: Используйте две переменные: i, которая указывает на текущий индекс в массиве, и count, которая отслеживает количество каждого элемента. Начните обработку массива с первого элемента (индекс 1), предполагая, что первый элемент всегда имеет count равный 1. 2️⃣Обработка элементов массива: Для каждого элемента в массиве: 3️⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count. Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент. Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1. Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи. 😎 Решение:
class Solution(object):
def removeDuplicates(self, nums):
i, count = 1, 1
while i < len(nums):
if nums[i] == nums[i - 1]:
count += 1
if count > 2:
nums.pop(i)
i -= 1
else:
count = 1
i += 1
return len(nums)8 922
Получи грант на обучение в Центральном университете
Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Гранты покрывают от 25 до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе
Подать заявку
#реклама
apply.centraluniversity.ru
О рекламодателе
