Python | LeetCode

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#medium Задача: 532. K-diff Pairs in an Array Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве. Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия: 0 <= i, j < nums.length i != j |nums[i] - nums[j]| == k Обратите внимание, что |val| обозначает абсолютное значение val. Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

👨‍💻 Алгоритм: 1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣ Увеличьте счётчик результатов, если условие выполняется. 😎 Решение:

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        counter = collections.Counter(nums)
        result = 0
        
        for x in counter:
            if k > 0 and (x + k) in counter:
                result += 1
            elif k == 0 and counter[x] > 1:
                result += 1
        
        return result

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

Увеличьте число повторных покупок и средний чек клиентов TEYCA — это платформа, которая помогает вашему бизнесу расти, превращая обычных покупателей в постоянных клиентов за счет создания собственной уникальной программы лояльности с современными маркетинговыми инструментами. ✅ Возможности TEYCA для вашего бизнеса: - Гибкая настройка программы лояльности - Карты в Apple Wallet и Google Pay - Telegram-бот и мини-приложение - Бесплатные PUSH-EMAIL-TELEGRAM рассылки - Расширенная сегментация и RFM - Конструктор акций - Легкая интеграция с вашей CRM - Реферальная программа для клиентов - Автоматический сбор отзывов и повышение рейтинга на картах - и многое другое в личном кабинете TEYCA ⚡ Зарегистрируйтесь прямо сейчас и получите 1 месяц бесплатного использования сервиса! Зарегистрироваться #реклама 16+ teyca.ru О рекламодателе

#hard Задача: 302. Smallest Rectangle Enclosing Black Pixels Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель. Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали. Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели. Вы должны написать алгоритм со сложностью менее O(mn). Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно. 2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника: left = min(left, x) right = max(right, x + 1) top = min(top, y) bottom = max(bottom, y + 1) 3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top). 😎 Решение:

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        left = self.searchColumns(image, 0, y, 0, m, True)
        right = self.searchColumns(image, y + 1, n, 0, m, False)
        top = self.searchRows(image, 0, x, left, right, True)
        bottom = self.searchRows(image, x + 1, m, left, right, False)
        return (right - left) * (bottom - top)

    def searchColumns(self, image: List[List[str]], i: int, j: int, top: int, bottom: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = top, (i + j) // 2
            while k < bottom and image[k][mid] == '0':
                k += 1
            if (k < bottom) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

    def searchRows(self, image: List[List[str]], i: int, j: int, left: int, right: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = left, (i + j) // 2
            while k < right and image[mid][k] == '0':
                k += 1
            if (k < right) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

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

#medium Задача: 531. Lonely Pixel I Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей. Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей. Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

👨‍💻 Алгоритм: 1⃣ Подсчёт количества чёрных пикселей в строках и столбцах: Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1. 2⃣ Поиск одиночных чёрных пикселей: Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1. 3⃣ Возврат результата: Верните answer. 😎 Решение:

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        n = len(picture)
        m = len(picture[0])
        
        rowCount = [0] * n
        columnCount = [0] * m
        
        for i in range(n):
            for j in range(m):
                if picture[i][j] == 'B':
                    rowCount[i] += 1
                    columnCount[j] += 1
        
        answer = 0
        for i in range(n):
            for j in range(m):
                if picture[i][j] == 'B' and rowCount[i] == 1 and columnCount[j] == 1:
                    answer += 1
        
        return answer

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

Yandex DataLens Festival, 2-18 декабря Для аналитиков, тимлидов, разработчиков, продактов и маркетологов. Эксперты Яндекса поделятся опытом. Онлайн и бесплатно Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе

#easy Задача: 541. Reverse String II Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки. Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть. Пример:

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

👨‍💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:

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

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

#medium Задача: 540. Single Element in a Sorted Array Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз. Верните единственный элемент, который встречается только один раз. Ваше решение должно работать за время O(log n) и использовать O(1) памяти. Пример:

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

👨‍💻 Алгоритм: 1⃣Начиная с первого элемента, итерируемся через каждый второй элемент, проверяя, является ли следующий элемент таким же, как текущий. Если нет, то текущий элемент — это искомый элемент. 2⃣Если доходим до последнего элемента, то он является искомым элементом. Обрабатываем этот случай после завершения цикла, чтобы избежать выхода за пределы массива. 3⃣Возвращаем найденный элемент. 😎 Решение:

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        for i in range(0, len(nums) - 1, 2):
            if nums[i] != nums[i + 1]:
                return nums[i]
        return nums[-1]

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

Яндекс Музыка до конца года бесплатно! Подписка Яндекс Плюс для вас и 3-х близких до конца года бесплатно! Слушайте музыку, смотрите фильмы и читайте книги в одной подписке. Попробуйте!👍 Попробовать #реклама 18+ plus.yandex.ru О рекламодателе Реклама на Яндексе

#easy Задача: 530. Minimum Absolute Difference in BST Дано корень бинарного дерева поиска (BST), верните минимальную абсолютную разницу между значениями любых двух разных узлов в дереве. Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        inorderNodes = []
        self.inorderTraversal(root, inorderNodes)
        minDifference = float('inf')
        for i in range(1, len(inorderNodes)):
            minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1])
        return minDifference

    def inorderTraversal(self, node: TreeNode, inorderNodes: List[int]) -> None:
        if not node:
            return
        self.inorderTraversal(node.left, inorderNodes)
        inorderNodes.append(node.val)
        self.inorderTraversal(node.right, inorderNodes)

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

#medium Задача: 528. Random Pick with Weight Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i. Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w). Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%). Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

👨‍💻 Алгоритм: 1⃣ Инициализация и предобработка весов: В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно. Также в конструкторе сохраните общую сумму весов totalSum. 2⃣ Генерация случайного числа и выбор индекса: В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum. Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу. 3⃣ Возврат результата: Верните найденный индекс. 😎 Решение:

import random

class Solution:
    def __init__(self, w: List[int]):
        self.prefixSums = []
        prefixSum = 0
        for weight in w:
            prefixSum += weight
            self.prefixSums.append(prefixSum)
        self.totalSum = prefixSum

    def pickIndex(self) -> int:
        target = self.totalSum * random.random()
        for i, prefixSum in enumerate(self.prefixSums):
            if target < prefixSum:
                return i
        return len(self.prefixSums) - 1

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

Помощь в трудоустройстве в IT-сфере! В России из-за дефицита айтишников запустили бесплатную программу по обучению IT-специалистов. Теперь любой желающий может попробовать себя в IT с полного нуля и начать обучение бесплатно! Узнайте про дальнейшее трудоустройство в ведущие IT-компании для восполнения кадрового дефицита. Для этого нужно: - Перейти по ссылке - Заполнить анкету и ответить на вопросы (занимает менее 3 минут) - На основании ваших ответов вы сразу узнаете, подходит ли вам сфера IT и сможете ли вы в ней работать Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#hard Задача: 239. Sliding Window Maximum Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию. Верните максимальные значения скользящего окна. Пример:

Input: nums = [1], k = 1
Output: [1]

👨‍💻 Алгоритм: 1⃣Инициализация и заполнение первой части окна: Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов. Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента: Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]]. 2⃣Сканирование оставшейся части массива: Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента: Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна. Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]]. 3⃣Возвращение результата: Верните список res, содержащий максимальные элементы для каждого скользящего окна. 😎 Решение:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = collections.deque()
        res = []

        for i in range(k):
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
        res.append(nums[dq[0]])

        for i in range(k, len(nums)):
            if dq[0] == i - k:
                dq.popleft()
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
            res.append(nums[dq[0]])

        return res

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

#hard Задача: 527. Word Abbreviation Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова. Правила сокращения строки следующие: Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ. Если более одного слова имеют одинаковое сокращение, выполните следующее: Увеличьте префикс (символы в первой части) каждого из их сокращений на 1. Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"]. Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным. В конце, если сокращение не сделало слово короче, оставьте его в исходном виде. Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

class Solution:
    def wordsAbbreviation(self, words: List[str]) -> List[str]:
        n = len(words)
        ans = [self.abbrev(word, 0) for word in words]
        prefix = [0] * n

        for i in range(n):
            while True:
                dupes = set()
                for j in range(i + 1, n):
                    if ans[i] == ans[j]:
                        dupes.add(j)

                if not dupes:
                    break

                dupes.add(i)
                for k in dupes:
                    prefix[k] += 1
                    ans[k] = self.abbrev(words[k], prefix[k])

        return ans

    def abbrev(self, word: str, i: int) -> str:
        n = len(word)
        if n - i <= 3:
            return word
        return word[:i + 1] + str(n - i - 2) + word[-1]

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

#medium Задача: 238. Product of Array Except Self Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i]. Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число. Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления. Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм: 1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1]. 2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево. 3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его. 😎 Решение:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        L = [1] * length
        R = [1] * length
        answer = [1] * length

        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]

        for i in range(length - 2, -1, -1):
            R[i] = nums[i + 1] * R[i + 1]

        for i in range(length):
            answer[i] = L[i] * R[i]

        return answer

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

#medium Задача: 526. Beautiful Arrangement Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий: perm[i] делится на i. i делится на perm[i]. Дано целое число n, верните количество красивых перестановок, которые вы можете создать. Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

class Solution:
    def __init__(self):
        self.count = 0

    def countArrangement(self, N: int) -> int:
        nums = list(range(1, N + 1))
        self.permute(nums, 0)
        return self.count
    
    def permute(self, nums, l):
        if l == len(nums):
            self.count += 1
        for i in range(l, len(nums)):
            nums[i], nums[l] = nums[l], nums[i]
            if nums[l] % (l + 1) == 0 or (l + 1) % nums[l] == 0:
                self.permute(nums, l + 1)
            nums[i], nums[l] = nums[l], nums[i]

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#hard Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента. Реализуйте класс RandomizedCollection: RandomizedCollection(): Инициализирует пустой объект RandomizedCollection. bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае. bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них. int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество. Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени. Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

👨‍💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:

import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        self.dict = defaultdict(set)
        self.list = []

    def insert(self, val: int) -> bool:
        self.dict[val].add(len(self.list))
        self.list.append(val)
        return len(self.dict[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.dict[val]:
            return False
        index = self.dict[val].pop()
        last_element = self.list[-1]
        self.list[index] = last_element
        self.dict[last_element].add(index)
        self.dict[last_element].discard(len(self.list) - 1)
        self.list.pop()
        if not self.dict[val]:
            del self.dict[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)

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

#medium Задача: 237. Delete Node in a Linked List Дан односвязный список с головой head, и требуется удалить узел node в этом списке. Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head. Все значения в односвязном списке уникальны, и гарантируется, что данный узел node не является последним узлом в списке. Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду: - Значение данного узла не должно существовать в односвязном списке. - Количество узлов в односвязном списке должно уменьшиться на один. - Все значения перед узлом должны оставаться в том же порядке. - Все значения после узла должны оставаться в том же порядке. Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

👨‍💻 Алгоритм: 1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле. 2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка. 3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка. 😎 Решение:

class Solution:
    def deleteNode(self, node: ListNode) -> None:
        node.val = node.next.val
        node.next = node.next.next

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