Python | LeetCode

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

    
        Input: heights = [1,1,4,2,1,3]
Output: 3{}
    

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

    
        def heightChecker(heights):
    expected = sorted(heights)
    count = 0
    for i in range(len(heights)):
        if heights[i] != expected[i]:
            count += 1
    return count{}
    

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

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

    
        Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").{}
    

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

    
        class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1Count = Counter(s1)
        s2Count = Counter(s2[:len(s1)])
        
        if s1Count == s2Count:
            return True
        
        for i in range(len(s1), len(s2)):
            s2Count[s2[i]] += 1
            s2Count[s2[i - len(s1)]] -= 1
            if s2Count[s2[i - len(s1)]] == 0:
                del s2Count[s2[i - len(s1)]]
            if s1Count == s2Count:
                return True
        
        return False{}
    

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

Задача: 200. Number of Islands Сложность: medium Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов. Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой. Пример:

    
        Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1{}
    

👨‍💻 Алгоритм: 1️⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS). 2️⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый. 3️⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров. 😎 Решение:

    
        class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1){}
    

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

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition Сложность: medium Вам дан массив целых чисел nums и целое число target. Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

    
        Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9){}
    

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте переменные answer равным 0 и n как длину массива nums. Отсортируйте массив nums. Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7. 2⃣Итерация и бинарный поиск: Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left]. Если left <= right, добавьте количество допустимых подпоследовательностей к answer. 3⃣Возврат результата: Верните answer по модулю 10^9+7. 😎 Решение:

    
        class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        mod = 10**9 + 7
        
        power = [1] * n
        for i in range(1, n):
            power[i] = power[i - 1] * 2 % mod
        
        answer = 0
        left, right = 0, n - 1
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                answer = (answer + power[right - left]) % mod
                left += 1
            else:
                right -= 1
        
        return answer{}
    

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

Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1. Пример:

    
        Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.{}
    

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

    
        class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        logs.sort()
        uf = UnionFind(n)
        group_count = n
        
        for timestamp, friendA, friendB in logs:
            if uf.union(friendA, friendB):
                group_count -= 1
            if group_count == 1:
                return timestamp
        
        return -1{}
    

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

Щипцы с паром DEWAL BEAUTY – это забота о ваших волосах Укладка мечты без вреда для волос! Инновационные паровые щипцы Elite DEWAL BEAUTY дарят бережную укладку с фантастическим блеском. • Пар мягко увлажняет волосы во время укладки • Минимизирует повреждения и сухость • Делает волосы мягкими и блестящими • Сохраняет здоровье ваших волос ✨ Преимущества: • Керамико-турмалиновое покрытие • 4 температурных режима (160-220°C) • Нагрев за 30 секунд • Автоотключение через 30 минут • Легкие (всего 290 г) Забудьте о сухости и ломкости, только шелковистые и здоровые волосы❤️ Дарим скидку 10% по промокоду SALE10 на все товары! Купить #реклама dewalbeauty.ru О рекламодателе

Задача: 1351. Count Negative Numbers in a Sorted Matrix Сложность: easy Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid. Пример:

    
        Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.{}
    

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

    
        class Solution:
    def countNegatives(self, grid):
        count = 0
        for row in grid:
            for element in row:
                if element < 0:
                    count += 1
        return count{}
    

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

Задача: 936. Stamping The Sequence Сложность: hard Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив Пример:

    
        Input: stamp = "abc", target = "ababc"
Output: [0,2]{}
    

👨‍💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:

    
        def movesToStamp(stamp, target):
    s, t = list(stamp), list(target)
    m, n = len(s), len(t)
    res = []
    done = [False] * n

    def canStamp(i):
        for j in range(m):
            if t[i + j] != '?' and t[i + j] != s[j]:
                return False
        return True

    def doStamp(i):
        for j in range(m):
            t[i + j] = '?'
        res.append(i)
        done[i] = True

    changed = True
    while changed:
        changed = False
        for i in range(n - m + 1):
            if not done[i] and canStamp(i):
                doStamp(i)
                changed = True

    if all(c == '?' for c in t):
        return res[::-1]
    return []{}
    

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

Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons Сложность: hard Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

    
        maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index{}
    

Вам необходимо построить массив arr, который имеет следующие свойства: arr содержит ровно n целых чисел. 1 <= arr[i] <= m, где (0 <= i < n). После применения указанного алгоритма к arr, значение search_cost равно k. Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7. Пример:

    
        Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1. 2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений. 3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи. 😎 Решение:

    
        class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[[0] * (k + 1) for _ in range(m + 1)] for _ in range(n + 1)]
        
        for num in range(m + 1):
            dp[n][num][0] = 1
        
        for i in range(n - 1, -1, -1):
            for maxSoFar in range(m, -1, -1):
                for remain in range(k + 1):
                    ans = 0
                    for num in range(1, maxSoFar + 1):
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
                    
                    if remain > 0:
                        for num in range(maxSoFar + 1, m + 1):
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD
                    
                    dp[i][maxSoFar][remain] = ans
        
        return dp[0][0][k]{}
    

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

Задача: 210. Course Schedule II Сложность: medium Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai. Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1. Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив. Пример 1:

    
        Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].{}
    

👨‍💻 Алгоритм: 1️⃣Инициализация и построение графа: Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе. Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма. 2️⃣Запуск поиска в глубину (DFS): Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла. Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны. 3️⃣Обработка узлов и возвращение результата: После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке. После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания. 😎 Решение:

    
        from collections import defaultdict

class Solution:
    WHITE = 1
    GRAY = 2
    BLACK = 3

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj_list = defaultdict(list)
        for dest, src in prerequisites:
            adj_list[src].append(dest)

        topological_sorted_order = []
        is_possible = True
        color = {k: Solution.WHITE for k in range(numCourses)}

        def dfs(node: int) -> None:
            nonlocal is_possible
            if not is_possible:
                return
            color[node] = Solution.GRAY
            if node in adj_list:
                for neighbor in adj_list[node]:
                    if color[neighbor] == Solution.WHITE:
                        dfs(neighbor)
                    elif color[neighbor] == Solution.GRAY:
                        is_possible = False
            color[node] = Solution.BLACK
            topological_sorted_order.append(node)

        for vertex in range(numCourses):
            if color[vertex] == Solution.WHITE:
                dfs(vertex)

        return topological_sorted_order[::-1] if is_possible else []{}
    

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