Python | LeetCode

Задача: 80. Remove Duplicates from Sorted Array II Сложность: medium Дан массив целых чисел 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)

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

Задача: 553. Optimal Division Сложность: medium Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой. Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4". Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным. Верните соответствующее выражение, которое имеет максимальное значение в строковом формате. Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

👨‍💻 Алгоритм: 1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе. 2⃣Для каждой цифры первого числа: умножьте цифру второго числа на цифру первого числа и добавьте предыдущий перенос к результату умножения. Возьмите остаток от деления на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру к массиву currentResult. Разделите результат умножения на 10, чтобы получить новое значение переноса. 3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его. 😎 Решение:

class Solution:
    def addStrings(self, num1, num2):
        ans = []
        carry = 0
        n1, n2 = len(num1), len(num2)

        for i in range(max(n1, n2) + 1):
            digit1 = num1[i] if i < n1 else 0
            digit2 = num2[i] if i < n2 else 0
            s = digit1 + digit2 + carry
            carry = s // 10
            ans.append(s % 10)
        return ans

    def multiplyOneDigit(self, firstNumber, secondNumberDigit, numZeros):
        currentResult = [0] * numZeros
        carry = 0

        for digit in firstNumber:
            multiplication = (int(secondNumberDigit) * int(digit)) + carry
            carry = multiplication // 10
            currentResult.append(multiplication % 10)
        if carry:
            currentResult.append(carry)
        return currentResult

    def multiply(self, firstNumber, secondNumber):
        if firstNumber == "0" or secondNumber == "0":
            return "0"

        firstNumber = firstNumber[::-1]
        secondNumber = secondNumber[::-1]

        ans = [0] * (len(firstNumber) + len(secondNumber))

        for i, digit in enumerate(secondNumber):
            ans = self.addStrings(self.multiplyOneDigit(firstNumber, digit, i), ans)

        while ans[-1] == 0:
            ans.pop()

        return ''.join(map(str, ans[::-1]))

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

Задача: 1192. Critical Connections in a Network Сложность: hard Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть. Критическое соединение — это соединение, удаление которого сделает невозможным достижение некоторыми серверами других серверов. Верните все критические соединения в сети в любом порядке. Пример:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

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

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        self.graph = defaultdict(list)
        self.rank = {}
        self.connDict = {}
        
        self.formGraph(n, connections)
        self.dfs(0, 0)
        
        result = []
        for conn in self.connDict:
            result.append(list(conn))
        return result

    def dfs(self, node, discoveryRank):
        if node in self.rank:
            return self.rank[node]
        
        self.rank[node] = discoveryRank
        minRank = discoveryRank + 1
        
        for neighbor in self.graph[node]:
            if neighbor in self.rank and self.rank[neighbor] == discoveryRank - 1:
                continue
            
            recursiveRank = self.dfs(neighbor, discoveryRank + 1)
            
            if recursiveRank <= discoveryRank:
                self.connDict.pop((min(node, neighbor), max(node, neighbor)), None)
            
            minRank = min(minRank, recursiveRank)
        
        return minRank

    def formGraph(self, n, connections):
        for i in range(n):
            self.graph[i]
            self.rank[i] = None
        
        for u, v in connections:
            self.graph[u].append(v)
            self.graph[v].append(u)
            self.connDict[(min(u, v), max(u, v))] = True

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

Клиенты уходят, а вы не знаете почему? Менеджеры упускают клиентов, но в отчетах все хорошо. AI в CRM разбирает звонки, находит слабые места и помогает исправить их без лишнего контроля. Попробуйте. Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 771. Jewels and Stones Сложность: medium Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        ans = 0
        for s in S:
            for j in J:
                if j == s:
                    ans += 1
                    break
        return ans

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

Задача: 622. Design Circular Queue Сложность: medium Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования. Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

👨‍💻 Алгоритм: 1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди. 2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу. 3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди. 😎 Решение:

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [-1] * k
        self.front = 0
        self.rear = -1
        self.size = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.queue[self.front]

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.queue[self.rear]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

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

🚀Хотите улучшить качество своего кода и повысить его надежность? Присоединяйтесь к открытому вебинару «Основы аннотаций типов в Python» от OTUS! На вебинаре мы: - Разберем, что такое аннотации типов и зачем они нужны в Python; - Ознакомимся с синтаксисом аннотаций типов и их применением; - Углубимся в mypy — инструмент для статической типизации; - Обсудим, как аннотации помогают улучшить читаемость кода и выявлять ошибки на этапе разработки. Этот вебинар подойдет как для начинающих разработчиков, так и для опытных специалистов, стремящихся повысить качество и поддерживаемость своего кода. ⚡️Присоединяйтесь 26 июня в 20:00 и узнайте, как аннотации типов сделают ваш код более безопасным и надежным! Запишитесь прямо сейчас и получите доступ к вебинару:  https://otus.pw/y58u/ Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Аптечка финансового директора ⚡30 проверенных инструментов, которые должны быть всегда под рукой у финансиста. Все эти материалы можно получить бесплатно 📊 13 Эксель-моделей и форм для финансового анализа - Методичка. Что ответить собственнику на вопросы о деньгах компании - Инструкция по выгрузке отчетов из 1С - 12 Промптов для ИИ под основные финансовые задачи - Чек-лист перед защитой отчетности - Шаблон Резюме, которое точно понравится рекрутеру - 15 практических схем налоговой оптимизации 📞 Закрытый телеграм-чат с топами и вакансиями - среди участников телеграм-канала финдиры Газпром Нефть, Азбука Вкуса, Подружка, АндерСон, и 3000 других ✅ Чтобы забрать инструменты в работу, вам нужно подписаться на канал Финансовый директор Скачать #реклама 16+ click.tgtrack.ru О рекламодателе

Задача: 766. Toeplitz Matrix Сложность: easy Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false. Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы. Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

👨‍💻 Алгоритм: 1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м 2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой. 3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true. 😎 Решение:

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        groups = {}
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if (r - c) not in groups:
                    groups[r - c] = matrix[r][c]
                elif groups[r - c] != matrix[r][c]:
                    return False
        return True

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent Сложность: medium Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0. A grandparent of a node is the parent of its parent if it exists. Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

👨‍💻 Алгоритм: 1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму. 2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу. 3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла. 😎 Решение:

class Solution:
    def solve(self, root: TreeNode, parent: int, gParent: int) -> int:
        if not root:
            return 0
        return self.solve(root.left, root.val, parent) + self.solve(root.right, root.val, parent) + (root.val if gParent % 2 == 0 else 0)

    def sumEvenGrandparent(self, root: TreeNode) -> int:
        return self.solve(root, -1, -1)

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

Задача: 223. Rectangle Area Сложность: medium Даны координаты двух прямоугольных прямоугольников на двумерной плоскости, верните общую площадь, покрытую этими двумя прямоугольниками. Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2). Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2). Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

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

class Solution:
    def computeArea(self,
                    ax1: int, ay1: int,
                    ax2: int, ay2: int,
                    bx1: int, by1: int,
                    bx2: int, by2: int) -> int:
        area_of_a = (ay2 - ay1) * (ax2 - ax1)
        area_of_b = (by2 - by1) * (bx2 - bx1)

        left = max(ax1, bx1)
        right = min(ax2, bx2)
        x_overlap = right - left

        top = min(ay2, by2)
        bottom = max(ay1, by1)
        y_overlap = top - bottom

        area_of_overlap = 0
        if x_overlap > 0 and y_overlap > 0:
            area_of_overlap = x_overlap * y_overlap

        total_area = area_of_a + area_of_b - area_of_overlap

        return total_area

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

🧑🏻‍💻Хотите освоить один из самых востребованных языков программирования и стать Python-разработчиком? Присоединяйтесь к курсу «Python Developer. Basic» от OTUS! В рамках курса вы: - освоите базовый синтаксис Python; - изучите фреймворки FastAPI и Django; - научитесь работать с базами данных и API; - поймете основы автотестирования, асинхронного программирования и разработки на Python. Вы научитесь создавать веб-приложения, чат-ботов, парсить сайты и работать с данными — всё это сделает вас ценным специалистом. Программа курса составлена практикующими экспертами и обновляется в соответствии с актуальными требованиями рынка. ⚡️Оставьте заявку прямо сейчас и получите скидку на обучение: https://otus.pw/zuf6/ Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Задача: 1043. Partition Array for Maximum Sum Сложность: medium Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число. Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

👨‍💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение:

def maxSumAfterPartitioning(arr, k):
    n = len(arr)
    dp = [0] * n

    for i in range(n):
        max_val = 0
        for j in range(1, k + 1):
            if i - j + 1 >= 0:
                max_val = max(max_val, arr[i - j + 1])
                if i - j >= 0:
                    dp[i] = max(dp[i], dp[i - j] + max_val * j)
                else:
                    dp[i] = max(dp[i], max_val * j)

    return dp[-1]

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

VK Weekend Offer: отправьте заявку, пройдите интервью и получите офер! 28–29 июня VK проведёт Weekend Offer для бэкендеров с опытом от трёх лет. Участников со знанием Java, Go, Python или C++ ждут технические собеседования, знакомство с продуктами и, если всё сложится, офер уже в конце выходных. Ребята много лет создают облачные решения, системы рекомендаций и поисковые движки — всё с миллионами пользователей в проде — и сейчас ищут новых коллег. Поэтому оставляйте заявку до 25 июня, чтобы попасть в команду за выходные! Подробности — на сайте.

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

Задача: 378. Kth Smallest Element in a Sorted Matrix Сложность: medium Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице. Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент. Вы должны найти решение с использованием памяти лучше, чем O(n²). Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:

import heapq

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        
        N = len(matrix)
                minHeap = []
        for r in range(min(k, N)):
            
            minHeap.append((matrix[r][0], r, 0))
        
        heapq.heapify(minHeap)    
        
        while k:
            
            element, r, c = heapq.heappop(minHeap)
            
            if c < N - 1:
                heapq.heappush(minHeap, (matrix[r][c+1], r, c+1))
            
            k -= 1
        
        return element

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

Задача: 336. Palindrome Pairs Сложность: hard Вам дан массив уникальных строк words, индексируемый с 0. Пара палиндромов — это пара целых чисел (i, j), таких что: 0 <= i, j < words.length, i != j, и words[i] + words[j] (конкатенация двух строк) является палиндромом. Верните массив всех пар палиндромов из слов. Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words). Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        pairs = []
        
        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue
                combined = words[i] + words[j]
                if combined == combined[::-1]:
                    pairs.append([i, j])
        
        return pairs

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

Гайд МТС Линк для РОПов по эффективным онлайн-встречам План не выполняется, текучка среди новых менеджеров, а обучение сейлзов не влияет на продажи? Гайд МТС Линк для РОПов: 37 страниц полезных материалов, чек-листов и кейсов для ускорения адаптации новичков, вовлечения команды и управления распределенным отделом продаж с помощью онлайн-встреч. ✅ В гайде: - Как создать постоянную переговорку и подключаться на встречи в 2 клика; - Как ускорить адаптацию новичков и сократить отток на испытательном сроке; - Как наладить систему обучения, когда нет времени на каждого; - Как автоматически фиксировать задачи и итоги обучения с ИИ; - Как сократить время выхода новичков на результат и повысить % выполнения плана. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1272. Remove Interval Сложность: medium Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше. Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

def removeInterval(intervals, toBeRemoved):
    result = []
    for start, end in intervals:
        if start < toBeRemoved[0]:
            result.append([start, min(end, toBeRemoved[0])])
        if end > toBeRemoved[1]:
            result.append([max(start, toBeRemoved[1]), end])
    return result

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

Задача: 1065. Index Pairs of a String Сложность: easy Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words. Верните пары [i, j] в отсортированном порядке (то есть отсортируйте их по первой координате, а в случае совпадения сортируйте их по второй координате). Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

👨‍💻 Алгоритм: 1⃣Поддерживайте хэш-набор слов. 2⃣Итерируйте i от 0 до text.length-1. Итерируйте j от i до text.length-1. Если подстрока text[i...j] принадлежит хэш-набору слов, добавьте пару [i, j] в ответ. 3⃣Верните ответ. 😎 Решение:

class Solution:
    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        wordsSet = set(words)
        ans = []
        
        for i in range(len(text)):
            for j in range(i, len(text)):
                if text[i:j+1] in wordsSet:
                    ans.append([i, j])
        
        return ans

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