Python | LeetCode

Задача: 867. Transpose Matrix Сложность: easy Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу. Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами. Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

👨‍💻 Алгоритм: 1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк. 2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c]. 3⃣Верните матрицу ans. 😎 Решение:

class Solution:
    def transpose(self, A):
        return [[A[r][c] for r in range(len(A))] for c in range(len(A[0]))]

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

Получи грант до 1,35 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! — 4 офлайн программы по востребованным направлениям ИТ — 2 онлайн-программы: машинное обучение и продуктовый менеджмент — 550 грантов до 75% — Вечерние занятия и учеба по выходным — удобно совмещать с работой — Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса — Возможность стажировок и трудоустройства в ведущих компаниях — Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Зарегистрироваться #реклама 16+ cu.ru О рекламодателе

Предзаказ Samsung Galaxy Z серии на сайте МТС! Оформите предзаказ на Samsung Galaxy Z серии с выгодой до 20 000р. и повышенным кешбэком 10% на сайте МТС! Рассрочка 0-0-24 Узнать больше #реклама shop.mts.ru О рекламодателе

VPS- твой надёжный сервер! VPS нового поколения ⚡ 3 дня бесплатно по промокоду «ВПС67» Первый месяц всего 75₽ 💰 ✅ Работает на всех устройствах! 👌 Пользуйся современными технологиями без ограничений! Подключайся 📱 Попробовать #реклама 16+ vpss67.ru О рекламодателе

Задача: 1248. Count Number of Nice Subarrays Сложность: medium Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример:

Input: arr = [1,2]
Output: 2

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

def numberOfSubarrays(nums, k):
    def atMost(nums, k):
        count = 0
        left = 0
        res = 0
        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                count += 1
            while count > k:
                if nums[left] % 2 == 1:
                    count -= 1
                left += 1
            res += right - left + 1
        return res
    return atMost(nums, k) - atMost(nums, k - 1)

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

Кинопоиск до 360 дней бесплатно Кинопоиск — тысячи фильмов и сериалов без рекламы, в высоком качестве. Яндекс Музыка и Книги тоже в мультиподписке Плюс. Попробуйте бесплатно ❤️ Попробовать #реклама 18+ kinopoisk.ru О рекламодателе

Задача: 1057. Campus Bikes Сложность: medium В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

def assignBikes(workers, bikes):
    pairs = []
    
    for i, (wx, wy) in enumerate(workers):
        for j, (bx, by) in enumerate(bikes):
            distance = abs(wx - bx) + abs(wy - by)
            pairs.append((distance, i, j))
    
    pairs.sort()
    
    result = [-1] * len(workers)
    bike_taken = [False] * len(bikes)
    worker_assigned = [False] * len(workers)
    
    for distance, worker_idx, bike_idx in pairs:
        if not worker_assigned[worker_idx] and not bike_taken[bike_idx]:
            result[worker_idx] = bike_idx
            bike_taken[bike_idx] = True
            worker_assigned[worker_idx] = True
    
    return result

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

Получите 400 рублей на счет мобильного телефона Выберите Яндекс Поиск в настройках браузера, ищите в нём — и они ваши! Узнать больше #реклама 16+ portal.yandex.ru О рекламодателе

Задача: 418. Sentence Screen Fitting Сложность: medium Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом. Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

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

def wordsTyping(sentence, rows, cols):
    sentence_str = " ".join(sentence) + " "
    length = len(sentence_str)
    pos = 0
    
    for _ in range(rows):
        pos += cols
        if sentence_str[pos % length] == " ":
            pos += 1
        else:
            while pos > 0 and sentence_str[(pos - 1) % length] != " ":
                pos -= 1
    
    return pos // length

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

И вы знаете Поэтому просто ещё раз обозначим, что промокод NETSIL скинет 5000 рублей при бронировании жилья на Яндекс Путешествиях. Забронировать #реклама travel.yandex.ru О рекламодателе

Задача: 1024. Video Stitching Сложность: medium Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1. Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        int end = -1, end2 = 0, res = 0;
        for (const auto& clip : clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
};

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

Получи грант до 1,35 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! — 4 офлайн программы по востребованным направлениям ИТ — 2 онлайн-программы: машинное обучение и продуктовый менеджмент — 550 грантов до 75% — Вечерние занятия и учеба по выходным — удобно совмещать с работой — Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса — Возможность стажировок и трудоустройства в ведущих компаниях — Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Зарегистрироваться #реклама 16+ cu.ru О рекламодателе

Задача: 652. Find Duplicate Subtrees Сложность: medium Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов. Пример:

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

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

from collections import defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findDuplicateSubtrees(root):
    def serialize(node):
        if not node:
            return "#"
        serial = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
        count[serial] += 1
        if count[serial] == 2:
            result.append(node)
        return serial
    
    count = defaultdict(int)
    result = []
    serialize(root)
    return result

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

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

И вы знаете Поэтому просто ещё раз обозначим, что промокод NETSIL скинет 5000 рублей при бронировании жилья на Яндекс Путешествиях. Забронировать #реклама travel.yandex.ru О рекламодателе

Пластиковая карта Пэй — мгновенный кешбэк до 50% баллами ✨ Оформите пластиковую карту Пэй c мгновенным кешбэком. 0₽ — выпуск карты и её обслуживание. Закажите в приложении Яндекс Пэй ❤️ Узнать больше Финансовые услуги оказывает: АО "Яндекс Банк". #реклама 16+ pay.yandex.ru О рекламодателе

Получите 400 рублей на счет мобильного телефона Выберите Яндекс Поиск в настройках браузера, ищите в нём — и они ваши! Узнать больше #реклама 16+ portal.yandex.ru О рекламодателе

Задача: 716. Max Stack Сложность: hard Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова. Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:

class MaxStack:

    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.max_stack or x >= self.max_stack[-1]:
            self.max_stack.append(x)

    def pop(self):
        x = self.stack.pop()
        if x == self.max_stack[-1]:
            self.max_stack.pop()
        return x

    def top(self):
        return self.stack[-1]

    def peekMax(self):
        return self.max_stack[-1]

    def popMax(self):
        max_val = self.max_stack.pop()
        buffer = []
        while self.stack[-1] != max_val:
            buffer.append(self.stack.pop())
        self.stack.pop()
        while buffer:
            self.push(buffer.pop())
        return max_val

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

Больше выгоды с подпиской Kaspersky Premium Купите подписку Kaspersky Premium сейчас и получите скидку до 28%, гарантированные призы от наших партнёров, а также шанс выиграть путешествие! Узнать больше #реклама 16+ kaspersky.ru О рекламодателе

Задача: 320. Generalized Abbreviation Сложность: medium Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины. Например, "abcde" можно сократить следующим образом: "a3e" ("bcd" заменено на "3") "1bcd1" ("a" и "e" заменены на "1") "5" ("abcde" заменено на "5") "abcde" (без замены подстрок) Однако следующие аббревиатуры недействительны: "23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные. "22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются. Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке. Пример:

Input: word = "a"
Output: ["1","a"]

👨‍💻 Алгоритм: 1⃣Создание битовых масок Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур. 2⃣Генерация аббревиатур Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик. 3⃣Перебор всех комбинаций Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1. 😎 Решение:

class Solution:
    def generateAbbreviations(self, word: str):
        def abbr(word, x):
            builder = []
            k = 0
            for i in range(len(word)):
                if x & 1 == 0:
                    if k != 0:
                        builder.append(str(k))
                        k = 0
                    builder.append(word[i])
                else:
                    k += 1
                x >>= 1
            if k != 0:
                builder.append(str(k))
            return ''.join(builder)
        
        ans = []
        for x in range(1 << len(word)):
            ans.append(abbr(word, x))
        return ans

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