Python | LeetCode

#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_area

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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 head

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

👨‍💻 Нужен человек для создания постов в сети каналов Leetcode. Работа оплачивается. Писать сюда

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

#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.next

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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] <= element

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

IT аутсорсинг в СПб! Обслуживание серверов и оргтехники! АйТи аутсорсинг в СПб! Сертифицированные специалисты! Опытная команда IT специалистов! Сертификаты Microsoft! CISCO Mikrotik! 12 лет на рынке! Перейти на сайт #реклама svcnet.ru О рекламодателе

#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)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Получи грант на обучение в Центральном университете Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Гранты покрывают от 25 до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

#medium Задача: 79. Word Search Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке. Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза. Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

👨‍💻 Алгоритм: 1️⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки. 2️⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова. 3️⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования. 😎 Решение:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.ROWS = len(board)
        self.COLS = len(board[0])
        self.board = board

        for row in range(self.ROWS):
            for col in range(self.COLS):
                if self.backtrack(row, col, word):
                    return True
        return False

    def backtrack(self, row: int, col: int, suffix: str) -> bool:
        if len(suffix) == 0:
            return True

        if (row < 0 or row == self.ROWS or col < 0 or col == self.COLS or self.board[row][col] != suffix[0]):
            return False

        ret = False
        self.board[row][col] = "#"
        for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
            if ret:
                break

        self.board[row][col] = suffix[0]
        return ret

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 78. Subsets Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор). Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке. Пример:

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

👨‍💻 Алгоритм: 1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов. 2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод. 3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr. 😎 Решение:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first=0, curr=[]):
            if len(curr) == k:
                output.append(curr[:])
                return
            for i in range(first, n):
                curr.append(nums[i])
                backtrack(i + 1, curr)
                curr.pop()

        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Доставка от 30 минут из кафе и ресторанов в Яндекс Еде Заказывайте без очередей в приложении или на сайте. Скидки и акции каждый день 👍 Попробовать #реклама 16+ plms.adj.st О рекламодателе

#medium Задача: 77. Combinations Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Ответ можно вернуть в любом порядке. Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

👨‍💻 Алгоритм: 1️⃣Инициализировать массив ответов ans и массив для построения комбинаций curr. 2️⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum: Если длина curr равна k, добавить копию curr в ans и вернуться. Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле. Итерировать num от firstNum до firstNum + available включительно. Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr. 3️⃣Вызвать backtrack с изначально пустым curr и firstNum = 1. Вернуть ans. 😎 Решение:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(curr, first_num):
            if len(curr) == k:
                ans.append(curr[:])
                return

            need = k - len(curr)
            remain = n - first_num + 1
            available = remain - need

            for num in range(first_num, first_num + available + 1):
                curr.append(num)
                backtrack(curr, num + 1)
                curr.pop()

        ans = []
        backtrack([], 1)
        return ans

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

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

#hard Задача: 76. Minimum Window Substring Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "". Тестовые примеры будут сформированы таким образом, что ответ будет уникальным. Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

👨‍💻 Алгоритм: 1️⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S. 2️⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T. 3️⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее. 😎 Решение:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        dict_t = Counter(t)
        required = len(dict_t)
        l, r = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None

        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                l += 1

            r += 1
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 75. Sort Colors Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета располагались в порядке красный, белый и синий. Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно. Вы должны решить эту задачу без использования функции сортировки библиотеки. Пример:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

👨‍💻 Алгоритм: 1️⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0. 2️⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2. 3️⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0. Пока curr <= p2: Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо. Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево. Если nums[curr] = 1: сдвинуть указатель curr вправо. 😎 Решение:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = curr = 0
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

🔵 Практический интенсив «Python-разработчик: основы за 2 дня» — 16-17 июля в 19:00 мск. О перспективах направления Python и многом другом расскажет Грегори Салиба, старший разработчик ЭквантаЛаб с опытом в разработке более 3 лет.  На вебинаре вы: ☑️ Самостоятельно напишете Telegram-бота с карточными мини-играми. ☑️ Познакомитесь с синтаксисом языка и сферами его применения. ☑️ Поймете как продолжить обучение, какие навыки потребуются, чтобы стать backend-разработчиком на Python. ☑️ Узнаете, чего ждут работодатели от junior-разработчиков и что делать, чтобы найти работу без опыта. 🎁 Приятные бонусы: полезный гайд для начинающего Python-разработчика и гайд о сленге в IT всем участникам интенсива!

#medium Задача: 74. Search a 2D Matrix Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами: Каждая строка отсортирована в порядке неубывания. Первое число каждой строки больше последнего числа предыдущей строки. Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае. Вы должны написать решение с временной сложностью O(log(m * n)). Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

👨‍💻 Алгоритм: 1️⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1. 2️⃣Пока left <= right: Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2. 3️⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части. Сравните pivot_element и target, чтобы определить, в какой части нужно искать target. 😎 Решение:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])

        left, right = 0, m * n - 1
        while left <= right:
            pivot_idx = (left + right) // 2
            pivot_element = matrix[pivot_idx // n][pivot_idx % n]
            if target == pivot_element:
                return True
            else:
                if target < pivot_element:
                    right = pivot_idx - 1
                else:
                    left = pivot_idx + 1
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 73. Set Matrix Zeroes Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца. Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы. Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

👨‍💻 Алгоритм: 1️⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0. 2️⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки. 3️⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми. 😎 Решение:

class Solution(object):
    def setZeroes(self, matrix: List[List[int]]) -> None:
        is_col = False
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, C):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        for i in range(1, R):
            for j in range(1, C):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        if matrix[0][0] == 0:
            for j in range(C):
                matrix[0][j] = 0

        if is_col:
            for i in range(R):
                matrix[i][0] = 0

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых