Задача: 204. Count Primes
Сложность: medium

Дано целое число n, верните количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

👨‍💻 Алгоритм:

1️⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2️⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3️⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎 Решение:

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        numbers = [False, False] + [True] * (n - 2)
        for p in range(2, int(sqrt(n)) + 1):
            if numbers[p]:
                for multiple in range(p * p, n, p):
                    numbers[multiple] = False
        return sum(numbers)

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

Задача: 468. Validate IP Address
Сложность: medium

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами.

Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

👨‍💻 Алгоритм:

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

class Solution:
    def validateIPv4(self, IP: str) -> str:
        nums = IP.split(".")
        for x in nums:
            if len(x) == 0 or len(x) > 3:
                return "Neither"
            if x[0] == '0' and len(x) != 1:
                return "Neither"
            if not x.isdigit():
                return "Neither"
            if int(x) > 255:
                return "Neither"
        return "IPv4"

    def validateIPv6(self, IP: str) -> str:
        nums = IP.split(":")
        hexdigits = "0123456789abcdefABCDEF"
        for x in nums:
            if len(x) == 0 or len(x) > 4:
                return "Neither"
            for ch in x:
                if ch not in hexdigits:
                    return "Neither"
        return "IPv6"

    def validIPAddress(self, IP: str) -> str:
        if IP.count(".") == 3:
            return self.validateIPv4(IP)
        elif IP.count(":") == 7:
            return self.validateIPv6(IP)
        else:
            return "Neither"

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза.

Пример:

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

👨‍💻 Алгоритм:

1️⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

2️⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова.

3️⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования.

😎 Решение:

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

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

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

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

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

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

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

Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

👨‍💻 Алгоритм:

1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину.

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:

class Solution:
    def getSumOfKthPowerOfDigits(self, n: int, k: int) -> int:
        result = 0
        while n != 0:
            result += (n % 10) ** k
            n //= 10
        return result

    def isArmstrong(self, n: int) -> bool:
        length = len(str(n))
        return self.getSumOfKthPowerOfDigits(n, length) == n

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

Задача: 953. Verifying an Alien Dictionary
Сложность: hard

В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.

Пример:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

👨‍💻 Алгоритм:

1⃣Создать словарь для хранения порядка каждой буквы в инопланетном языке.
Пройти по каждому слову и сравнить его с последующим словом.

2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка.
Если обнаружена пара слов, нарушающая порядок, вернуть false.

3⃣Если все слова отсортированы правильно, вернуть true.

😎 Решение:

def isAlienSorted(words, order):
    order_map = {char: i for i, char in enumerate(order)}
    
    def compare(word1, word2):
        for c1, c2 in zip(word1, word2):
            if order_map[c1] < order_map[c2]:
                return True
            elif order_map[c1] > order_map[c2]:
                return False
        return len(word1) <= len(word2)
    
    for i in range(len(words) - 1):
        if not compare(words[i], words[i + 1]):
            return False
    return True

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

Задача: 557. Reverse Words in a String III
Сложность: easy

Дана строка s. Необходимо изменить порядок символов в каждом слове в предложении, сохранив при этом пробелы и начальный порядок слов.

Пример:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

👨‍💻 Алгоритм:

1⃣Создайте переменную lastSpaceIndex и установите её значение в -1. Пройдите по каждому символу строки s от 0-го до n-го индекса, используя указатель strIndex.

2⃣Когда strIndex указывает на пробел, определите начало (startIndex = lastSpaceIndex + 1) и конец (endIndex = strIndex - 1) текущего слова. Используя два указателя, измените порядок символов в текущем слове.

3⃣Обновите lastSpaceIndex значением strIndex. После окончания цикла измените порядок символов в последнем слове (от lastSpaceIndex + 1 до конца строки).

😎 Решение:

class Solution:
    def reverseWords(self, s: str) -> str:
        s = list(s)
        lastSpaceIndex = -1
        length = len(s)
        
        for strIndex in range(length + 1):
            if strIndex == length or s[strIndex] == ' ':
                startIndex = lastSpaceIndex + 1
                endIndex = strIndex - 1
                while startIndex < endIndex:
                    s[startIndex], s[endIndex] = s[endIndex], s[startIndex]
                    startIndex += 1
                    endIndex -= 1
                lastSpaceIndex = strIndex
        
        return ''.join(s)

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

Задача: 231. Power of Two
Сложность: easy

Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.

Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.

Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

👨‍💻 Алгоритм:

1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.

2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций.

3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.

😎 Решение:

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False
        return (n & -n) == n

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

Задача: 127. Word Ladder
Сложность: Hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:

Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

👨‍💻 Алгоритм:

1️⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

2️⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3️⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

from collections import defaultdict, deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0

        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + "*" + word[i + 1:]].append(word)

        queue = deque([(beginWord, 1)])
        visited = {beginWord: True}
        while queue:
            current_word, level = queue.popleft()
            for i in range(L):
                intermediate_word = current_word[:i] + "*" + current_word[i + 1:]
                for word in all_combo_dict[intermediate_word]:
                    if word == endWord:
                        return level + 1
                    if word not in visited:
                        visited[word] = True
                        queue.append((word, level + 1))
                all_combo_dict[intermediate_word] = []
        return 0

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

Задача: 92. Reverse Linked List II
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

👨‍💻 Алгоритм:

1️⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2️⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse.
В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно.

3️⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next.
Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката.
Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.
Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎 Решение:

class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], m: int, n: int
    ) -> Optional[ListNode]:
        if not head:
            return None

        left, right = head, head
        stop = False

        def recurseAndReverse(right, m, n):
            nonlocal left, stop
            if n == 1:
                return
            right = right.next
            if m > 1:
                left = left.next
            recurseAndReverse(right, m - 1, n - 1)
            if left == right or right.next == left:
                stop = True
            if not stop:
                left.val, right.val = right.val, left.val
                left = left.next

        recurseAndReverse(right, m, n)
        return head

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

Задача: 1328. Break a Palindrome
Сложность: medium

Дана палиндромная строка из строчных английских букв palindrome. Замените ровно один символ на любую строчную английскую букву так, чтобы результирующая строка не была палиндромом и чтобы она была лексикографически наименьшей из возможных.

Верните получившуюся строку. Если нет способа заменить символ, чтобы строка перестала быть палиндромом, верните пустую строку.

Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.

Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

👨‍💻 Алгоритм:

1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае.

2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку.

3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку.

😎 Решение:

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        length = len(palindrome)
        
        if length == 1:
            return ""
        
        for i in range(length // 2):
            if palindrome[i] != 'a':
                return palindrome[:i] + 'a' + palindrome[i+1:]
        
        return palindrome[:-1] + 'b'

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

Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение Судоку должно удовлетворять всем следующим правилам:

Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки.
Символ '.' обозначает пустые ячейки.

Пример:

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: 
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

👨‍💻 Алгоритм:

1️⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки.

2️⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col).
Если число d еще не в текущей строке, столбце и блоке:
Поместите d в ячейку (row, col).
Запишите, что d теперь присутствует в текущей строке, столбце и блоке.

3️⃣Если вы на последней ячейке row == 8, col == 8:
Это означает, что судоку решено.
В противном случае продолжайте размещать дальнейшие числа.
Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col).

😎 Решение:

from collections import defaultdict

class Solution:
    def solveSudoku(self, board):
        n = 3
        N = n * n
        rows, cols, boxes = [defaultdict(int) for _ in range(N)], [defaultdict(int) for _ in range(N)], [defaultdict(int) for _ in range(N)]

        def place_or_remove(d, r, c, add=True):
            idx = (r // n) * n + (c // n)
            rows[r][d] = rows[r].get(d, 0) + (1 if add else -1)
            cols[c][d] = cols[c].get(d, 0) + (1 if add else -1)
            boxes[idx][d] = boxes[idx].get(d, 0) + (1 if add else -1)
            board[r][c] = str(d) if add else '.'
            if rows[r][d] == 0: del rows[r][d]
            if cols[c][d] == 0: del cols[c][d]
            if boxes[idx][d] == 0: del boxes[idx][d]

        def can_place(d, r, c):
            idx = (r // n) * n + (c // n)
            return not (d in rows[r] or d in cols[c] or d in boxes[idx])

        def backtrack(r=0, c=0):
            if c == N:
                r, c = r + 1, 0
            if r == N:
                return True
            if board[r][c] == '.':
                for d in map(str, range(1, 10)):
                    if can_place(d, r, c):
                        place_or_remove(d, r, c, True)
                        if backtrack(r, c + 1):
                            return True
                        place_or_remove(d, r, c, False)
            else:
                return backtrack(r, c + 1)
            return False

        for r in range(N):
            for c in range(N):
                if board[r][c] != '.':
                    place_or_remove(board[r][c], r, c, True)

        backtrack()

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

Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

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

👨‍💻 Алгоритм:

1⃣Представить каждую строку и столбец как узлы в графе.

2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.

😎 Решение:

def removeStones(stones):
    parent = {}
    
    def find(x):
        if parent.setdefault(x, x) != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        parent[find(x)] = find(y)
    
    for x, y in stones:
        union(x, ~y)
    
    return len(stones) - len({find(x) for x in parent})

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

Задача: 60. Permutation Sequence
Сложность: hard

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.

Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3
Output: "213"

👨‍💻 Алгоритм:

1️⃣ Сгенерируйте входной массив nums чисел от 1 до N.

2️⃣ Вычислите все факториальные основы от 0 до (N−1)!.

3️⃣ Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).

😎 Решение:

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorials, nums = [1], ["1"]
        for i in range(1, n):
            factorials.append(factorials[i - 1] * i)
            nums.append(str(i + 1))
        k -= 1
        output = []
        for i in range(n - 1, -1, -1):
            idx = k // factorials[i]
            k -= idx * factorials[i]
            output.append(nums[idx])
            del nums[idx]
        return "".join(output)

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

Задача: 587. Erect the Fence
Сложность: hard

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.

Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.

Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке.

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

👨‍💻 Алгоритм:

1⃣ Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

2⃣ Построение верхней оболочки:
Пройдитесь по точкам в обратном порядке, чтобы построить верхнюю оболочку.
Добавляйте точки к оболочке и удаляйте последние точки, если они не образуют против часовой стрелки поворот.

3⃣ Удаление дублирующих элементов и возврат результата:
Используйте HashSet, чтобы удалить дублирующиеся точки из стека.
Преобразуйте результат в массив и верните его.

😎 Решение:

class Solution:
    def orientation(self, p, q, r):
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

    def outerTrees(self, points):
        points.sort(key=lambda x: (x[0], x[1]))
        hull = []

        for point in points:
            while len(hull) >= 2 and self.orientation(hull[-2], hull[-1], point) > 0:
                hull.pop()
            hull.append(point)

        hull.pop()

        for point in reversed(points):
            while len(hull) >= 2 and self.orientation(hull[-2], hull[-1], point) > 0:
                hull.pop()
            hull.append(point)

        return list(set(map(tuple, hull)))

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

Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

👨‍💻 Алгоритм:

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

class Solution:
    def findNumberOfLIS(self, nums):
        n = len(nums)
        length = [1] * n
        count = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = 0
                    if length[j] + 1 == length[i]:
                        count[i] += count[j]

        maxLength = max(length)
        result = 0

        for i in range(n):
            if length[i] == maxLength:
                result += count[i]

        return result

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

👨‍💻 Алгоритм:

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        n, k = len(characters), combinationLength
        for bitmask in range(1 << n):
            if bin(bitmask).count('1') == k:
                curr = [characters[j] for j in range(n) if bitmask & (1 << n - j - 1)]
                self.combinations.append(''.join(curr))

    def next(self) -> str:
        return self.combinations.pop()

    def hasNext(self) -> bool:
        return self.combinations

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

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива.

2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.

3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями.

😎 Решение:

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.

Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций.

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

👨‍💻 Алгоритм:

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        lo, hi = 1, len(s) + 1

        while lo + 1 < hi:
            mid = lo + (hi - lo) // 2
            if self.canMakeValidSubstring(s, mid, k):
                lo = mid
            else:
                hi = mid

        return lo

    def canMakeValidSubstring(self, s: str, substringLength: int, k: int) -> bool:
        freqMap = [0] * 26
        maxFrequency = 0
        start = 0

        for end in range(len(s)):
            freqMap[ord(s[end]) - ord('A')] += 1

            if end + 1 - start > substringLength:
                freqMap[ord(s[start]) - ord('A')] -= 1
                start += 1

            maxFrequency = max(maxFrequency, freqMap[ord(s[end]) - ord('A')])
            if substringLength - maxFrequency <= k:
                return True

        return False

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

Задача: 939. Minimum Area Rectangle
Сложность: medium

Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0.

Пример:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

👨‍💻 Алгоритм:

1⃣Создать множество для хранения всех точек.
Инициализировать переменную для хранения минимальной площади прямоугольника с бесконечным значением.

2⃣Пройти через все пары точек:
Если две точки могут образовать диагональ прямоугольника, то проверить, существуют ли оставшиеся две точки для замкнутого прямоугольника.
Если да, вычислить площадь прямоугольника и обновить минимальную площадь.

3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь.

😎 Решение:

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2 and (x1, y2) in point_set and (x2, y1) in point_set:
                min_area = min(min_area, abs(x2 - x1) * abs(y2 - y1))
    
    return 0 if min_area == float('inf') else min_area

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

Задача: 173. Binary Search Tree Iterator
Сложность: medium

Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order:

BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST.
boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false.
int next(): Перемещает указатель вправо, затем возвращает число на указателе.
Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST.
Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число.

Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

👨‍💻 Алгоритм:

1️⃣Инициализируйте пустой массив, который будет содержать узлы бинарного дерева поиска в отсортированном порядке.

2️⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево.

3️⃣Когда у нас будут все узлы в массиве, нам просто нужен указатель или индекс в этом массиве для реализации двух функций next и hasNext. Всякий раз, когда вызывается hasNext, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции next мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции next, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора.

😎 Решение:

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

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.nodes_sorted = []
        self.index = -1
        self._inorder(root)

    def _inorder(self, root: TreeNode) -> None:
        if not root:
            return
        self._inorder(root.left)
        self.nodes_sorted.append(root.val)
        self._inorder(root.right)

    def next(self) -> int:
        self.index += 1
        return self.nodes_sorted[self.index]

    def hasNext(self) -> bool:
        return self.index + 1 < len(self.nodes_sorted)

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