#medium
Задача: 567. Permutation in String

Даны две строки 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

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

#hard
Задача: 642. Design Search Autocomplete System

Разработайте систему автозаполнения поиска для поисковой системы. Пользователь может ввести предложение (не менее одного слова и заканчивающееся специальным символом '#'). Вам дается строковый массив sentences и целочисленный массив times длиной n, где sentences[i] - ранее набранное предложение, а times[i] - соответствующее количество раз, когда предложение было набрано. Для каждого входного символа, кроме '#', верните 3 лучших исторически горячих предложения, которые имеют тот же префикс, что и уже набранная часть предложения. Вот конкретные правила: степень горячести предложения определяется как количество раз, когда пользователь набирал точно такое же предложение ранее. 3 лучших горячих предложения должны быть отсортированы по степени горячести (первое - самое горячее). Если несколько предложений имеют одинаковую степень горячести, используйте порядок ASCII-кодов (меньшее предложение отображается первым). Если существует менее 3 горячих предложений, верните столько, сколько сможете. Если на входе находится специальный символ, это означает, что предложение закончилось, и в этом случае нужно вернуть пустой список.
Реализуйте класс AutocompleteSystem: AutocompleteSystem(String[] sentences, int[] times) Инициализирует объект с массивами sentences и times. List<String> input(char c) Это указывает, что пользователь ввел символ c. Возвращает пустой массив [], если c == '#', и сохраняет введенное предложение в системе. Возвращает 3 лучших исторических горячих предложения, имеющих тот же префикс, что и часть уже введенного предложения. Если совпадений меньше 3, возвращает их все.

Пример:

Input
["AutocompleteSystem", "input", "input", "input", "input"]
[[["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
Output
[null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]

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

1⃣Инициализация структуры данных: Реализуйте класс AutocompleteSystem, который будет хранить предложения и их частоту в виде словаря или хэша. Инициализируйте структуру с входными массивами sentences и times, заполняя словарь.

2⃣Обработка ввода символов: Создайте метод input, который обрабатывает ввод каждого символа. Если символ не является #, обновите текущий префикс и найдите все предложения, которые его содержат. Отсортируйте найденные предложения по частоте и по алфавиту.

3⃣Обработка завершения предложения: Если ввод символа равен #, сохраните текущий префикс как новое предложение или обновите частоту существующего предложения в словаре. Очистите текущий префикс для новой сессии.

😎 Решение:

import collections
import heapq

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.trie = {}
        self.history = collections.defaultdict(int)
        self.keyword = ""

        for i in range(len(sentences)):
            self.history[sentences[i]] += times[i]
            self.add_to_trie(sentences[i])
    
    def add_to_trie(self, sentence):
        node = self.trie
        for char in sentence:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['#'] = sentence
    
    def input(self, c):
        if c == '#':
            self.history[self.keyword] += 1
            self.add_to_trie(self.keyword)
            self.keyword = ""
            return []
        
        self.keyword += c
        node = self.trie
        for char in self.keyword:
            if char not in node:
                return []
            node = node[char]

        return self.search_in_trie(node)

    def search_in_trie(self, node):
        pq = []
        self.dfs(node, pq)
        return [item[1] for item in heapq.nsmallest(3, pq)]
    
    def dfs(self, node, pq):
        for char in node:
            if char == '#':
                heapq.heappush(pq, (-self.history[node[char]], node[char]))
            else:
                self.dfs(node[char], pq)

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

#hard
Задача: 568. Maximum Vacation Days

LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.

Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Вы можете оставаться в городе большее количество дней, чем количество дней отпуска, но вы должны работать в дополнительные дни, которые не будут учитываться как дни отпуска.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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

1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

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

😎 Решение:

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n, k = len(flights), len(days[0])
        memo = [[-1] * k for _ in range(n)]

        def dfs(cur_city, weekno):
            if weekno == k:
                return 0
            if memo[cur_city][weekno] != -1:
                return memo[cur_city][weekno]
            max_vac = 0
            for next_city in range(n):
                if cur_city == next_city or flights[cur_city][next_city] == 1:
                    max_vac = max(max_vac, days[next_city][weekno] + dfs(next_city, weekno + 1))
            memo[cur_city][weekno] = max_vac
            return max_vac

        return dfs(0, 0)

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

#easy
Задача: 643. Maximum Average Subarray I

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

1⃣Инициализация скользящего окна: Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.
2⃣Перемещение окна: Перемещайте окно длиной k по массиву, добавляя следующий элемент и убирая предыдущий, чтобы поддерживать сумму текущего окна.
3⃣Обновление максимальной суммы: На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎 Решение:

def findMaxAverage(nums, k):
    current_sum = sum(nums[:k])
    max_sum = current_sum
    
    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, current_sum)
    
    return max_sum / k

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

#hard
Задача: 644. Maximum Average Subarray II

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

😎 Решение:

def findMaxAverage(nums, k):
    n = len(nums)
    max_avg = curr_sum = sum(nums[:k])
    for i in range(k, n):
        curr_sum += nums[i] - nums[i - k]
        max_avg = max(max_avg, curr_sum)
    return max_avg / k

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

#easy
Задача: 645. Set Mismatch

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

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

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

1⃣Пройдите по массиву, используя набор для отслеживания чисел, чтобы определить дублированное число.
2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.
3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

def findErrorNums(nums):
    n = len(nums)
    num_set = set()
    duplicate = -1
    for num in nums:
        if num in num_set:
            duplicate = num
        num_set.add(num)
    missing = (n * (n + 1)) // 2 - sum(num_set)
    return [duplicate, missing]

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

#medium
Задача: 646. Maximum Length of Pair Chain

Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример:

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

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

1⃣Отсортируйте пары по второму элементу каждой пары (righti).
2⃣Используйте динамическое программирование или жадный алгоритм, чтобы построить цепочку максимальной длин
3⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки.

😎 Решение:

def findLongestChain(pairs):
    pairs.sort(key=lambda x: x[1])
    current_end = float('-inf')
    count = 0
    for pair in pairs:
        if current_end < pair[0]:
            current_end = pair[1]
            count += 1
    return count

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

#hard
Задача: 656. Coin Path

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

import heapq

def minCostPath(coins, maxJump):
    n = len(coins)
    if coins[0] == -1:
        return []
    
    dp = [float('inf')] * n
    dp[0] = coins[0]
    path = [[] for _ in range(n)]
    path[0] = [1]
    
    heap = [(coins[0], 0)]  # (cost, index)
    
    while heap:
        current_cost, i = heapq.heappop(heap)
        if current_cost > dp[i]:
            continue
        for k in range(1, maxJump + 1):
            if i + k < n and coins[i + k] != -1:
                new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] or (new_cost == dp[i + k] and path[i] + [i + k + 1] < path[i + k]):
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heapq.heappush(heap, (new_cost, i + k))
    
    return path[-1] if dp[-1] != float('inf') else []

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

#medium
Задача: 655. Print Binary Tree

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

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

def findHeight(root):
    if not root:
        return -1
    return 1 + max(findHeight(root.left), findHeight(root.right))

def fill(res, root, r, c, height):
    if not root:
        return
    res[r][c] = str(root.val)
    if root.left:
        fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height)
    if root.right:
        fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height)

def printTree(root):
    height = findHeight(root)
    m = height + 1
    n = (1 << (height + 1)) - 1
    res = [["" for _ in range(n)] for _ in range(m)]
    fill(res, root, 0, (n - 1) // 2, height)
    return res

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

#medium
Задача: 654. Maximum Binary Tree

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения.

😎 Решение:

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

def constructMaximumBinaryTree(nums):
    if not nums:
        return None
    max_index = nums.index(max(nums))
    root = TreeNode(nums[max_index])
    root.left = constructMaximumBinaryTree(nums[:max_index])
    root.right = constructMaximumBinaryTree(nums[max_index + 1:])
    return root

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

#easy
Задача: 653. Two Sum IV - Input is a BST

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

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

def findTarget(root, k):
    def find(node, k, seen):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return find(node.left, k, seen) or find(node.right, k, seen)
    
    return find(root, k, set())

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

#medium
Задача: 652. Find Duplicate Subtrees

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

Пример:

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

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

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

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.

😎 Решение:

from collections import defaultdict

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

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

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

#medium
Задача: 651. 4 Keys Keyboard

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:

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

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

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

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

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:

def maxA(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 1
        for j in range(2, i):
            dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))
    return dp[n]

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

#medium
Задача: 650. 2 Keys Keyboard

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

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

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

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

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

def minSteps(n):
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = i
        for j in range(1, i // 2 + 1):
            if i % j == 0:
                dp[i] = min(dp[i], dp[j] + i // j)
    return dp[n]

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

#medium
Задача: 649. Dota2 Senate

В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".

Пример:

Input: senate = "RD"
Output: "Radiant"

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

1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.

2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.

3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.

😎 Решение:

from collections import deque

def predictPartyVictory(senate):
    radiant = deque()
    dire = deque()
    
    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)
    
    while radiant and dire:
        r = radiant.popleft()
        d = dire.popleft()
        if r < d:
            radiant.append(r + len(senate))
        else:
            dire.append(d + len(senate))
    
    return "Radiant" if radiant else "Dire"

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

#medium
Задача: 648. Replace Words

В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. Верните предложение после замены.

Пример:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

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

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

2⃣Пройдите по каждому слову в предложении и найдите самый короткий корень, который является префиксом этого слова.

3⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

def replaceWords(roots, sentence):
    root_set = set(roots)
    
    def replace(word):
        for i in range(1, len(word) + 1):
            if word[:i] in root_set:
                return word[:i]
        return word
    
    return ' '.join(map(replace, sentence.split()))

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

#medium
Задача: 647. Palindromic Substrings

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

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

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

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

def countSubstrings(s):
    def expandAroundCenter(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
    
    total_count = 0
    for i in range(len(s)):
        total_count += expandAroundCenter(i, i)  # For odd length palindromes
        total_count += expandAroundCenter(i, i + 1)  # For even length palindromes
    return total_count

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

#medium
Задача: 677. Map Sum Pairs

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

class MapSum:
    def __init__(self):
        self.map = {}
    def insert(self, key: str, val: int) -> None:
        self.map[key] = val
    def sum(self, prefix: str) -> int:
        return sum(val for key, val in self.map.items() if key.startswith(prefix))

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

#medium
Задача: 678. Valid Parenthesis String

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution:
    def checkValidString(self, s: str) -> bool:
        memo = [[-1] * len(s) for _ in range(len(s))]
        return self.isValidString(0, 0, s, memo)

    def isValidString(self, index: int, openCount: int, s: str, memo: list) -> bool:
        if index == len(s):
            return openCount == 0

        if memo[index][openCount] != -1:
            return memo[index][openCount] == 1

        isValid = False

        if s[index] == '*':
            isValid = self.isValidString(index + 1, openCount + 1, s, memo)
            if openCount > 0:
                isValid = isValid or self.isValidString(index + 1, openCount - 1, s, memo)
            isValid = isValid or self.isValidString(index + 1, openCount, s, memo)
        elif s[index] == '(':
            isValid = self.isValidString(index + 1, openCount + 1, s, memo)
        elif openCount > 0:
            isValid = self.isValidString(index + 1, openCount - 1, s, memo)

        memo[index][openCount] = 1 if isValid else 0
        return isValid

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

#hard
Задача: 679. 24 Game

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution:
    def generatePossibleResults(self, a, b):
        res = [a + b, a - b, b - a, a * b]
        if a != 0:
            res.append(b / a)
        if b != 0:
            res.append(a / b)
        return res

    def checkIfResultReached(self, list):
        if len(list) == 1:
            return abs(list[0] - 24) <= 0.1

        for i in range(len(list)):
            for j in range(i + 1, len(list)):
                new_list = [list[k] for k in range(len(list)) if k != i and k != j]
                for res in self.generatePossibleResults(list[i], list[j]):
                    new_list.append(res)
                    if self.checkIfResultReached(new_list):
                        return True
                    new_list.pop()
        return False

    def judgePoint24(self, cards):
        return self.checkIfResultReached(list(map(float, cards)))

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

#easy
Задача: 680. Valid Palindrome II

Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.

Пример:

Input: s = "aba"
Output: true

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

1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом.

2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов.

3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true.

😎 Решение:

class Solution:
    def checkPalindrome(self, s: str, i: int, j: int) -> bool:
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True
    
    def validPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        
        while i < j:
            if s[i] != s[j]:
                return self.checkPalindrome(s, i, j - 1) or self.checkPalindrome(s, i + 1, j)
            i += 1
            j -= 1
        
        return True

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