Python | LeetCode

Задача: 1216. Valid Palindrome III Сложность: hard Дана строка s и целое число k. Верните true, если s является k-палиндромом. Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов. Пример:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

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

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        memo = [[None] * n for _ in range(n)]

        def isValidPalindromeHelper(i, j):
            if i == j:
                return 0
            if i == j - 1:
                return 1 if s[i] != s[j] else 0
            if memo[i][j] is not None:
                return memo[i][j]
            if s[i] == s[j]:
                memo[i][j] = isValidPalindromeHelper(i + 1, j - 1)
            else:
                memo[i][j] = 1 + min(isValidPalindromeHelper(i + 1, j), isValidPalindromeHelper(i, j - 1))
            return memo[i][j]

        return isValidPalindromeHelper(0, n - 1) <= k

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

Задача: 1036. Escape a Large Maze Сложность: hard Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов. Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

from collections import deque

def isEscapePossible(blocked, source, target):
    blocked = set(map(tuple, blocked))
    source = tuple(source)
    target = tuple(target)
    
    if source in blocked or target in blocked:
        return False

    def bfs(start, end):
        queue = deque([start])
        visited = set([start])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        max_area = len(blocked) * (len(blocked) - 1) // 2
        
        while queue:
            if len(visited) > max_area:
                return True
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in visited and (nx, ny) not in blocked:
                    if (nx, ny) == end:
                        return True
                    queue.append((nx, ny))
                    visited.add((nx, ny))
        return False
    
    return bfs(source, target) and bfs(target, source)

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

Задача: 212. Word Search II Сложность: hard Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске. Каждое слово должно быть составлено из букв последовательных смежных ячеек, где смежные ячейки находятся по горизонтали или вертикали рядом. Одна и та же ячейка с буквой не может использоваться более одного раза в слове. Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

👨‍💻 Алгоритм: 1️⃣ Построение Trie: Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже. 2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки: Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell). 3️⃣ Обход соседних ячеек: В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell). На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале. 😎 Решение:

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        WORD_KEY = "$"

        trie = {}
        for word in words:
            node = trie
            for letter in word:
                node = node.setdefault(letter, {})
            node[WORD_KEY] = word

        rowNum = len(board)
        colNum = len(board[0])
        matchedWords = []

        def backtracking(row, col, parent):
            letter = board[row][col]
            currNode = parent[letter]

            word_match = currNode.pop(WORD_KEY, False)
            if word_match:
                matchedWords.append(word_match)

            board[row][col] = "#"

            for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                newRow, newCol = row + rowOffset, col + colOffset
                if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
                    continue
                if board[newRow][newCol] not in currNode:
                    continue
                backtracking(newRow, newCol, currNode)

            board[row][col] = letter

            if not currNode:
                parent.pop(letter)

        for row in range(rowNum):
            for col in range(colNum):
                if board[row][col] in trie:
                    backtracking(row, col, trie)

        return matchedWords

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

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться" Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе

Задача: 668. Kth Smallest Number in Multiplication Table Сложность: hard Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1). Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n. Пример:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

👨‍💻 Алгоритм: 1⃣Установка границ поиска: Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n. 2⃣Бинарный поиск: Используйте бинарный поиск, чтобы найти k-й наименьший элемент. Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid. 3⃣Проверка количества элементов: Если количество элементов меньше k, увеличьте нижнюю границу (left). Если количество элементов больше или равно k, уменьшите верхнюю границу (right). 😎 Решение:

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def count_less_equal(x):
            count = 0
            for i in range(1, m + 1):
                count += min(x // i, n)
            return count
        
        left, right = 1, m * n
        while left < right:
            mid = (left + right) // 2
            if count_less_equal(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left

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

Задача: 1038. Binary Search Tree to Greater Sum Tree Сложность: medium Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска. Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

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

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.sum = 0
        
        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)
            self.sum += node.val
            node.val = self.sum
            reverse_inorder(node.left)
        
        reverse_inorder(root)
        return root

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

Задача: 1025. Divisor Game Сложность: easy Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 2
Output: true

👨‍💻 Алгоритм: 1⃣Определение выигрыша: Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом. Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом. 2⃣Проверка четности числа: Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false. 3⃣Возврат результата: Возвращаем результат в зависимости от четности числа n. 😎 Решение:

class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0

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

Задача: 261. Graph Valid Tree Сложность: medium У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе. Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае. Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

import collections
from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        adj_list = [[] for _ in range(n)]
        for A, B in edges:
            adj_list[A].append(B)
            adj_list[B].append(A)
        
        parent = {0: -1}
        queue = collections.deque([0])
        
        while queue:
            node = queue.popleft()
            for neighbour in adj_list[node]:
                if neighbour == parent[node]:
                    continue
                if neighbour in parent:
                    return False
                parent[neighbour] = node
                queue.append(neighbour)
        
        return len(parent) == n

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

Задача: 384. Shuffle an Array Сложность: medium Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания. Реализуйте класс Solution: Solution(int[] nums): Инициализирует объект целочисленным массивом nums. int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его. int[] shuffle(): Возвращает случайное перемешивание массива. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

import random

class Solution:
    def __init__(self, nums: list[int]):
        self.array = nums[:]
        self.original = nums[:]
    
    def reset(self) -> list[int]:
        self.array = self.original[:]
        return self.original
    
    def shuffle(self) -> list[int]:
        for i in range(len(self.array)):
            rand_index = random.randint(i, len(self.array) - 1)
            self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
        return self.array

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 718. Maximum Length of Repeated Subarray Сложность: medium Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах. Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

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

def findLength(nums1, nums2):
    dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
    max_len = 0
    for i in range(len(nums1) - 1, -1, -1):
        for j in range(len(nums2) - 1, -1, -1):
            if nums1[i] == nums2[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

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

🔥 Бесплатный интенсив по ChatGPT и созданию НЕЙРОСТРУДНИКОВ без опыта программирования🔥 Вы узнаете, как использовать ChatGPT в профессиональных целях, создавать нейросотрудников на заказ и зарабатывать на ИИ от 150.000р в месяц. Простое понимание основ, без сложного кода! Что будет на интенсиве? 🧬 Теория: как создаются нейро-сотрудники с GPT на Python 🧬 Практика: мы создадим нейро-консультанта, нейро-HR, нейро-маркетолога и др. Интенсив - максимально простой и доступный, без какого-либо сложного программирования. Ведущий интенсива - Senior AI-разработчик нейросетей с 2003 года и основатель Университета искусственного интеллекта - Дмитрий Романов. 🤖 Присоединяйтесь к нашему бесплатному интенсиву и разберитесь в этой увлекательной теме с нами!

Задача: 36. Valid Sudoku Сложность: medium Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам: Каждая строка должна содержать цифры от 1 до 9 без повторений. Каждый столбец должен содержать цифры от 1 до 9 без повторений. Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений. Пример:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

👨‍💻 Алгоритм: 1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков. 2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число: Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке. 3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело. Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true. 😎 Решение:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N = 9

        rows = [set() for _ in range(N)]
        cols = [set() for _ in range(N)]
        boxes = [set() for _ in range(N)]

        for r in range(N):
            for c in range(N):
                val = board[r][c]
                if val == ".":
                    continue

                if val in rows[r]:
                    return False
                rows[r].add(val)

                if val in cols[c]:
                    return False
                cols[c].add(val)

                idx = (r // 3) * 3 + c // 3
                if val in boxes[idx]:
                    return False
                boxes[idx].add(val)

        return True

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

Университет искусственного интеллекта приглашает 💰 Стоимость вебинара: Бесплатно! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. 💻 Программа вебинара: 1) Классификация входящих/выходящих из автобуса людей 2) Классификация отзывов на Tesla 3) Оценка выброса CO2 по параметрам машины 4) Прогнозирование тренда цены доллара 5) Сегментация изображения для робота-доставщика 6) Обнаружение людей без касок на стройке/производстве 7) Трекинг людей на видео 8) Распознавание речи 9) Генерация изображения с помощью Stable Diffusion Хочешь отучиться на передовой научного прогресса? Тогда скорее регистрируйся! Зарегистрироваться #реклама 16+ neural-university.ru О рекламодателе

Задача: 1015. Smallest Integer Divisible by K Сложность: medium Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число. Пример:

Input: k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Использование остатка для нахождения числа с цифрами 1: Создайте переменную num и установите ее равной 1. Создайте переменную length и установите ее равной 1 для отслеживания длины числа. 2⃣Итеративное нахождение числа: Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k. Увеличивайте length на 1 в каждой итерации. Если в какой-то итерации num % k == 0, верните length. 3⃣Проверка бесконечного цикла: Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует. 😎 Решение:

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        num, length = 1, 1
        seen = set()
        
        while num % k != 0:
            if num % k in seen:
                return -1
            seen.add(num % k)
            num = (num * 10 + 1) % k
            length += 1
        
        return length

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

Задача: 65. Valid Number Сложность: hard Учитывая строку s, определите, является ли s валидным числом. Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53". Формально, валидное число определяется с использованием одного из следующих определений: Целое число с необязательным показателем степени. Десятичное число с необязательным показателем степени. Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры. Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений: Цифры, за которыми следует точка '.'. Цифры, за которыми следует точка '.', за которой следуют цифры. Точка '.', за которой следуют цифры. Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число. Цифры определяются как одна или более цифр. Пример:

Input: s = "0"
Output: true

👨‍💻 Алгоритм: 1️⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true. 2️⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число. 3️⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры. 😎 Решение:

class Solution:
    def isNumber(self, s: str) -> bool:
        seen_digit = seen_exponent = seen_dot = False
        for i, c in enumerate(s):
            if c.isdigit():
                seen_digit = True
            elif c in ["+", "-"]:
                if i > 0 and s[i - 1] != "e" and s[i - 1] != "E":
                    return False
            elif c in ["e", "E"]:
                if seen_exponent or not seen_digit:
                    return False
                seen_exponent = True
                seen_digit = False
            elif c == ".":
                if seen_dot or seen_exponent:
                    return False
                seen_dot = True
            else:
                return False

        return seen_digit

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

Мечтаешь стать дизайнером? Начни с dsgn sense — мультисенсорной олимпиады по дизайну от Школы дизайна Центрального университета для учеников 10-11-х классов. Познакомься с профессиями графического, продуктового и промышленного дизайнера! Реши кейс от компаний-партнеров и создай проект, в котором зрение, слух, осязание, вкус и обоняние станут основой уникального дизайн-решения. Призеры и победители получат: — Два проекта в портфолио. — Финал в наукограде Дубне с бесплатным проживанием, питанием и насыщенной программой. — Крутой мерч и призы от компаний. — Шанс выиграть грант до 100% на обучение в бакалавриате ЦУ. Тебе не нужны специальные навыки: достаточно любопытства и желания экспериментировать. Регистрируйся до 16 февраля по ссылке: Зарегистрироваться Есть противопоказания. Посоветуйтесь с врачом. #реклама 16+ event.cu.ru О рекламодателе

Задача: 1271. Hexspeak Сложность: easy Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR". Пример:

Input: num = "257"
Output: "IOI"

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

def toHexString(num):
    hex_str = hex(int(num))[2:].upper().replace('0', 'O').replace('1', 'I')
    for char in hex_str:
        if char not in 'ABCDEFIO':
            return "ERROR"
    return hex_str

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

Задача: 997. Find the Town Judge Сложность: easy В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае. Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if not trust and n == 1:
            return 1

        trust_count = [0] * (n + 1)
        trusted_by = [0] * (n + 1)

        for a, b in trust:
            trust_count[a] += 1
            trusted_by[b] += 1

        for i in range(1, n + 1):
            if trust_count[i] == 0 and trusted_by[i] == n - 1:
                return i

        return -1

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

Задача: 1243. Array Transformation Сложность: easy Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив. Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

def transformArray(arr):
    while True:
        new_arr = arr[:]
        changed = False
        for i in range(1, len(arr) - 1):
            if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
                new_arr[i] += 1
                changed = True
            elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
                new_arr[i] -= 1
                changed = True
        if not changed:
            break
        arr = new_arr
    return arr

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