Python | LeetCode

Задача: 838. Push Dominoes Сложность: medium Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо. Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа. Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил. В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино. Вам дано строковое представление начального состояния домино: dominoes[i] = 'L', если i-е домино толкнули влево, dominoes[i] = 'R', если i-е домино толкнули вправо, и dominoes[i] = '.', если i-е домино не было толкнуто. Верните строку, представляющую конечное состояние. Пример:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

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

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        N = len(dominoes)
        indexes = [-1]
        symbols = ['L']
        
        for i in range(N):
            if dominoes[i] != '.':
                indexes.append(i)
                symbols.append(dominoes[i])
                
        indexes.append(N)
        symbols.append('R')
        
        ans = list(dominoes)
        for idx in range(len(indexes) - 1):
            i, j = indexes[idx], indexes[idx + 1]
            x, y = symbols[idx], symbols[idx + 1]
            if x == y:
                for k in range(i + 1, j):
                    ans[k] = x
            elif x == 'R' and y == 'L':
                for k in range(i + 1, j):
                    if k - i == j - k:
                        ans[k] = '.'
                    elif k - i < j - k:
                        ans[k] = 'R'
                    else:
                        ans[k] = 'L'
                        
        return ''.join(ans)

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

Задача: 1235. Maximum Profit in Job Scheduling Сложность: hard У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X. Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

import bisect

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    dp = [(0, 0)]

    for s, e, p in jobs:
        i = bisect.bisect_right(dp, (s, float('inf')))
        if dp[i-1][1] + p > dp[-1][1]:
            dp.append((e, dp[i-1][1] + p))
    
    return dp[-1][1]

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

"Рыцари и Принцессы": средневековая ферма Выращивайте урожай, добывайте ресурсы и совершенствуйте своё королевство. Играть #реклама 16+ 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

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае. Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз. Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        count = 0
        for num in nums:
            if num == target:
                count += 1
        return count > len(nums) // 2

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

Задача: 1413. Minimum Value to Get Positive Step by Step Sum Сложность: easy Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue. На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо). Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1. Пример:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

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

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        startValue = 1
        while True:
            total = startValue
            isValid = True
            for num in nums:
                total += num
                if total < 1:
                    isValid = False
                    break
            if isValid:
                return startValue
            startValue += 1

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

👩‍💻 Стажировки и вакансии для Python разработчиков. - Вакансии которых нет на джоб-агрегаторах - Только прямые контакты HR в Telegram 👉 @jobs_python Больше тут: 🤖 ML & DS 👩‍💻 DevOps 👨‍✈️ ИБ & OSINT 👣 Go 👩‍💻 Mobile 👩‍💻 C# 👩‍💻 Node.js 👩‍💻 Python 🔎 QA 👩‍💻 Java 👩‍💻 UX/UI 👩‍💻 Frontend 🖼️ PHP 📋 Analyst 💼 1C 🖥 SQL 👩‍💻 IT HR Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.

Задача: 496. Next Greater Element I Сложность: easy Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве. Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2. Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1. Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше. Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

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

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1] * len(nums1)
        
        for i in range(len(nums1)):
            found = False
            for j in range(len(nums2)):
                if nums2[j] == nums1[i]:
                    found = True
                if found and nums2[j] > nums1[i]:
                    res[i] = nums2[j]
                    break
        
        return res

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

Задача: 247. Strobogrammatic Number II Сложность: medium Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке. Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами). Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм: 1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:

class Solution:
    def __init__(self):
        self.reversiblePairs = [
            ('0', '0'), ('1', '1'), 
            ('6', '9'), ('8', '8'), ('9', '6')
        ]

    def generateStroboNumbers(self, n, finalLength):
        if n == 0:
            return [""]
        
        if n == 1:
            return ["0", "1", "8"]
        
        prevStroboNums = self.generateStroboNumbers(n - 2, finalLength)
        currStroboNums = []
        
        for prevStroboNum in prevStroboNums:
            for a, b in self.reversiblePairs:
                if a != '0' or n != finalLength:
                    currStroboNums.append(a + prevStroboNum + b)
        
        return currStroboNums

    def findStrobogrammatic(self, n):
        return self.generateStroboNumbers(n, n)

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

Бесплатный курс диджитал-дизайна На бесплатном курсе ты сможешь: ✨попробовать себя в диджитал-дизайне: афиши, сайты, UX/UI-дизайн (дизайн интерфейсов) ✨сделать 3 проекта для портфолио с обратной связью от наставника ✨понять, как устроена работа дизайнера ✨получить доступ к закрытой базе материалов и пошаговым инструкциям по профессии Попробовать #реклама 18+ study.logomachine.ru О рекламодателе

Задача: 1053. Previous Permutation With One Swap Сложность: medium Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j]. Пример:

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

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

def prevPermOpt1(arr):
    n = len(arr)
    for i in range(n - 2, -1, -1):
        if arr[i] > arr[i + 1]:
            break
    else:
        return arr
    
    for j in range(n - 1, i, -1):
        if arr[j] < arr[i] and (j == n - 1 or arr[j] != arr[j + 1]):
            break
    
    arr[i], arr[j] = arr[j], arr[i]
    
    return arr

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

Задача: 1801. Number of Orders in the Backlog Сложность: medium Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть: - 0, если это партия заказов на покупку, или - 1, если это партия заказов на продажу. Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i. Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее: - Если это заказ на покупку, вы просматриваете заказ на продажу с наименьшей ценой в списке невыполненных заказов. Если цена этого заказа на продажу меньше или равна цене текущего заказа на покупку, они будут сопоставлены и выполнены, и этот заказ на продажу будет удален из списка. В противном случае заказ на покупку добавляется в список невыполненных заказов. - Если это заказ на продажу, вы просматриваете заказ на покупку с наибольшей ценой в списке невыполненных заказов. Если цена этого заказа на покупку больше или равна цене текущего заказа на продажу, они будут сопоставлены и выполнены, и этот заказ на покупку будет удален из списка. В противном случае заказ на продажу добавляется в список невыполненных заказов. Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7. Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

👨‍💻 Алгоритм: 1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список. 2⃣Для заказа на продажу сравните с самыми дорогими заказами на покупку в списке и выполняйте их при возможности, иначе добавьте в список. 3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7. 😎 Решение:

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buyOrders, sellOrders = [], []
        MOD = 1_000_000_007

        for price, amount, orderType in orders:
            if orderType == 0:
                while amount > 0 and sellOrders and sellOrders[0][0] <= price:
                    sellOrder = heapq.heappop(sellOrders)
                    executedAmount = min(amount, sellOrder[1])
                    amount -= executedAmount
                    if sellOrder[1] > executedAmount:
                        heapq.heappush(sellOrders, (sellOrder[0], sellOrder[1] - executedAmount))
                if amount > 0:
                    heapq.heappush(buyOrders, (-price, amount))
            else:
                while amount > 0 and buyOrders and -buyOrders[0][0] >= price:
                    buyOrder = heapq.heappop(buyOrders)
                    executedAmount = min(amount, buyOrder[1])
                    amount -= executedAmount
                    if buyOrder[1] > executedAmount:
                        heapq.heappush(buyOrders, (buyOrder[0], buyOrder[1] - executedAmount))
                if amount > 0:
                    heapq.heappush(sellOrders, (price, amount))

        return sum(amount for _, amount in buyOrders + sellOrders) % MOD

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

Задача: 1019. Next Greater Node In Linked List Сложность: medium Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0. Пример:

Input: head = [2,1,5]
Output: [5,5,0]

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

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        values = []
        while head:
            values.append(head.val)
            head = head.next
        
        answer = [0] * len(values)
        stack = []
        
        for i, value in enumerate(values):
            while stack and values[stack[-1]] < value:
                answer[stack.pop()] = value
            stack.append(i)
        
        return answer

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

Всё, что вы любите, есть на Wildberries Все мы ищем разное, но всегда находим что-то своё на WB — со скидками и доставкой. Перейти на сайт #реклама wildberries.ru О рекламодателе

Задача: 1342. Number of Steps to Reduce a Number to Zero Сложность: easy Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля. На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1. Пример:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

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

def numberOfSteps(num):
    steps = 0
    while num != 0:
        if num % 2 == 0:
            num //= 2
        else:
            num -= 1
        steps += 1
    return steps

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

Задача: 1473. Paint House III Сложность: hard Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены. Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет. Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}]. Дан массив домов, матрица m x n стоимости и целое число target, где: houses[i]: цвет дома i, и 0, если дом ещё не покрашен. cost[i][j]: стоимость покраски дома i в цвет j + 1. Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1. Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

👨‍💻 Алгоритм: 1⃣Инициализация и базовые случаи: Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1. Создайте метод findMinCost, который проверяет базовые случаи: - если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST. - если количество соседств больше target, возвращайте MAX_COST. Если результат уже вычислен, возвращайте его из memo. 2⃣Рекурсивное вычисление минимальной стоимости: Если дом уже покрашен, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Если дом не покрашен, попробуйте покрасить его в каждый возможный цвет, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Храните минимальную стоимость. 3⃣Метод minCost: Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1. 😎 Решение:

class Solution:
    def __init__(self):
        self.MAX_COST = 1000001
        self.memo = {}

    def findMinCost(self, houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor):
        if currIndex == len(houses):
            return 0 if neighborhoodCount == targetCount else self.MAX_COST
        
        if neighborhoodCount > targetCount:
            return self.MAX_COST

        if (currIndex, neighborhoodCount, prevHouseColor) in self.memo:
            return self.memo[(currIndex, neighborhoodCount, prevHouseColor)]
        
        minCost = self.MAX_COST
        
        if houses[currIndex] != 0:
            newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor)
            minCost = self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        else:
            for color in range(1, len(cost[0]) + 1):
                newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor)
                currCost = cost[currIndex][color - 1] + self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = min(minCost, currCost)
        
        self.memo[(currIndex, neighborhoodCount, prevHouseColor)] = minCost
        return minCost
    
    def minCost(self, houses, cost, m, n, target):
        answer = self.findMinCost(houses, cost, target, 0, 0, 0)
        return -1 if answer == self.MAX_COST else answer

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

Куда срочно перенести рабочие чаты? Битрикс24 — мессенджер для работы и бизнеса. Личные и групповые чаты, видеозвонки и каналы в одном сервисе. Приглашайте коллег и внешние команды. Работает как привычный мессенджер. Есть бесплатный тариф. Начните работать уже сейчас. Попробовать #реклама 16+ bitrix24.ru О рекламодателе

Задача: 459. Repeated Substring Pattern Сложность: easy Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом. Пример:

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⃣Создайте целочисленную переменную n, равную длине строки s. 2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2: Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s. Если pattern равен s, вернуть true. 3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false. 😎 Решение:

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                pattern = s[:i] * (n // i)
                if s == pattern:
                    return True
        return False

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

Задача: 635. Design Log Storage System Сложность: medium Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения. int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать. Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

👨‍💻 Алгоритм: 1⃣Инициализация и хранение журналов Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения. 2⃣Формирование диапазона Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity. 3⃣Фильтрация и возврат результатов Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон. 😎 Решение:

class LogSystem:
    def __init__(self):
        self.logs = []

    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((id, timestamp))

    def retrieve(self, start: str, end: str, granularity: str) -> [int]:
        index = {
            'Year': 4,
            'Month': 7,
            'Day': 10,
            'Hour': 13,
            'Minute': 16,
            'Second': 19
        }[granularity]
        
        start = start[:index]
        end = end[:index]
        
        result = []
        for id, timestamp in self.logs:
            if start <= timestamp[:index] <= end:
                result.append(id)
        return result

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

Задача: 733. Flood Fill Сложность: easy Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

def floodFill(image, sr, sc, color):
    original_color = image[sr][sc]
    if original_color == color:
        return image
    
    def dfs(x, y):
        if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != original_color:
            return
        image[x][y] = color
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
    
    dfs(sr, sc)
    return image

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