Python | LeetCode

Задача: 437. Path Sum III Сложность: medium Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum. Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним). Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

👨‍💻 Алгоритм: 1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0). 2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target]. 3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его. 😎 Решение:

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        def preorder(node: TreeNode, curr_sum) -> None:
            nonlocal count
            if not node:
                return 
            curr_sum += node.val
            if curr_sum == k:
                count += 1
            count += h[curr_sum - k]
            h[curr_sum] += 1
            preorder(node.left, curr_sum)
            preorder(node.right, curr_sum)
            h[curr_sum] -= 1
            
        count, k = 0, sum
        h = defaultdict(int)
        preorder(root, 0)
        return count

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

Задача: 523. Continuous Subarray Sum Сложность: medium Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае. Хороший подмассив — это подмассив, который: имеет длину не менее двух, и сумма элементов подмассива является кратной k. Учтите: Подмассив — это непрерывная часть массива. Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k. Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

👨‍💻 Алгоритм: 1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod. 2⃣Итеративно пройдите по всем элементам массива nums. 3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false. 😎 Решение:

class Solution:
    def checkSubarraySum(self, nums, k):
        prefix_mod = 0
        mod_seen = {0: -1}

        for i in range(len(nums)):
            prefix_mod = (prefix_mod + nums[i]) % k

            if prefix_mod in mod_seen:
                if i - mod_seen[prefix_mod] > 1:
                    return True
            else:
                mod_seen[prefix_mod] = i

        return False

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

🎉 easyoffer 2.0 — релиз уже в этом месяце! Вас ждут новые фичи, о которых мы ранее даже не упоминали. Они сделают путь к офферам ещё быстрее и эффективнее. Расскажу о них чуть позже 👀 В честь запуска мы готовим ограниченную акцию: Первые 500 покупателей получат: 🚀 PRO тариф на 1 год с 50% скидкой Что нужно сделать: 🔔 Подпишитесь на этот Telegram-канал, чтобы первыми узнать о старте релиза. Сообщение появится в нем раньше, чем где-либо еще — вы успеете попасть в число первых 500 и получить максимальную выгоду. 🎁 А еще только для подписчиков канала ценный бонус в подарок к PRO тарифу. 📅 Официальный запуск — уже совсем скоро. Следите за новостями и не пропустите старт!

Спокойный сон руководителя: закупки под контролем! Для руководителей в строительстве, которым важно доверие к команде, прозрачность процессов и уверенность в каждой сделке. ⚡Подозреваете, что снабжение не дорабатывает или просто не умеет эффективно искать поставщиков? С нейросетью для контроля закупок""Тринити"" вы получаете: Объективную оценку каждой сделки по 18 параметрам без человеческого фактора Альтернативные предложения от проверенных поставщиков на 7-10% дешевле Полную прозрачность закупочного процесса Уверенность в каждом решении отдела закупок Наши клиенты снижают процент неэффективных закупок с 30% до 5%! Экономия до 3,5 млрд ₽. 👍Перейдите в телеграм-бота сейчас и проверьте свои закупки бесплатно в течение 15 дней! Первые результаты через 10 минут. Попробовать #реклама 16+ trinitysafe.ru О рекламодателе

Задача: 1481. Least Number of Unique Integers after K Removals Сложность: medium Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов. Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

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

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        from collections import Counter
        freq_map = Counter(arr)
        frequencies = sorted(freq_map.values())
        
        elements_removed = 0
        for i, freq in enumerate(frequencies):
            elements_removed += freq
            if elements_removed > k:
                return len(frequencies) - i
        
        return 0

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

Задача: 670. Maximum Swap Сложность: medium Дано целое число num. Вы можете поменять местами две цифры не более одного раза, чтобы получить число с наибольшим значением. Верните число с наибольшим значением, которое можно получить. Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

👨‍💻 Алгоритм: 1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно. 2⃣Проверяем, что не добавили ведущий ноль. Фактически, проверять это не нужно, так как изначальное число его не содержит. 3⃣Возвращаем максимальное значение из всех кандидатов. 😎 Решение:

class Solution:
    def maximumSwap(self, num: int) -> int:
        A = list(str(num))
        ans = A[:]
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                A[i], A[j] = A[j], A[i]
                for k in range(len(A)):
                    if A[k] != ans[k]:
                        if A[k] > ans[k]:
                            ans = A[:]
                        break
                A[i], A[j] = A[j], A[i]
        return int(''.join(ans))

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

🐍💩👩‍💻👩‍💻🧑‍💻🧑‍💻🐧👩‍💻🧑‍💻👩‍💻👩‍💻 В сети начали массово сливать курсы и книги известных онлайн школ по айти Вот отсортированная база с тонной материала (постепенно пополняется): (363 видео, 87 книги) — Python (415 видео, 68 книги) — Frontend (143 видео, 33 книги) — ИБ/Хакинг (352 видео, 89 книги) — С/С++/C# (343 видео, 87 книги) — Java/QA (176 видео, 32 книги) — Git/Linux (174 видео, 91 книги) — DevOps (167 видео, 53 книги) — PHP/1С (227 видео, 83 книги) — SQL/БД (114 видео, 77 книги) — Сисадмин (107 видео, 43 книги) — BA/SA (181 видео, 32 книги) — Go/Rust (167 видео, 43 книги) — Kotlin/Swift (112 видео, 24 книги) — Flutter (137 видео, 93 книги) — DS/ML (113 видео, 82 книги) — GameDev (183 видео, 37 книги) — Дизайн (136 видео, 33 книги) — PM/HR Скачивать ничего не нужно — все выложили в Telegram

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 830. Positions of Large Groups Сложность: easy В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа. Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy". Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6]. Группа считается большой, если в ней 3 или более символов. Верните интервалы каждой большой группы, отсортированные в порядке возрастания начального индекса. Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

👨‍💻 Алгоритм: 1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы. 2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат. 3⃣Обновите i = j + 1 и начните новую группу. 😎 Решение:

class Solution:
    def largeGroupPositions(self, S: str):
        ans = []
        i, N = 0, len(S)

        for j in range(N):
            if j == N - 1 or S[j] != S[j + 1]:
                if j - i + 1 >= 3:
                    ans.append([i, j])
                i = j + 1

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

Задача: 538. Convert BST to Greater 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⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево. 2⃣Посещаем текущий узел, обновляем его значение и общую сумму. 3⃣Рекурсивно обрабатываем левое поддерево. 😎 Решение:

class Solution:
    def __init__(self):
        self.sum = 0

    def convertBST(self, root: TreeNode) -> TreeNode:
        if root:
            self.convertBST(root.right)
            self.sum += root.val
            root.val = self.sum
            self.convertBST(root.left)
        return root

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

Пройди практику в Wildberries&Russ и получи диплом ТГУ Хочешь развивать карьеру в аналитике и не тратить на это 10 лет? Магистратура «Дата-аналитика для бизнеса» ускорит! В ней ты: ⚡Прокачаешь навыки работы с Big Data и искусственным интеллектом в бизнесе с экспертами Wildberries & Russ, других топ-компаний и преподавателями ТГУ. ⚡3 специализации на выбор: продуктовая аналитика, маркетинговая аналитика и BI/бизнес-аналитика — выбирай то, что ближе к твоим целям. ⚡Получишь возможность пройти стажировку в Wildberries & Russ. Учёба онлайн — с гибким графиком из любой точки мира. Оставляй заявку, а мы проконсультируем, как :) Узнать больше #реклама 16+ ai.tsu.ru О рекламодателе

Задача: 348. Design Tic-Tac-Toe Сложность: medium Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками: Ход гарантированно является допустимым и делается на пустом поле. Как только достигается выигрышное условие, дальнейшие ходы запрещены. Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру. Реализуйте класс TicTacToe: TicTacToe(int n) Инициализирует объект с размером доски n. int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает: 0, если после хода победителя нет. 1, если после хода игрок 1 является победителем. 2, если после хода игрок 2 является победителем. Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal = 0
        self.anti_diagonal = 0

    def move(self, row: int, col: int, player: int) -> int:
        add = 1 if player == 1 else -1

        self.rows[row] += add
        self.cols[col] += add
        if row == col:
            self.diagonal += add
        if row + col == self.n - 1:
            self.anti_diagonal += add

        if (abs(self.rows[row]) == self.n or
            abs(self.cols[col]) == self.n or
            abs(self.diagonal) == self.n or
            abs(self.anti_diagonal) == self.n):
            return player

        return 0

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

Задача: 1189. Maximum Number of Balloons Сложность: easy Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon". Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать. Пример:

Input: text = "nlaebolko"
Output: 1

👨‍💻 Алгоритм: 1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text. 2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений. 3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение. 😎 Решение:

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        bCount = 0
        aCount = 0
        lCount = 0
        oCount = 0
        nCount = 0

        for char in text:
            if char == 'b':
                bCount += 1
            elif char == 'a':
                aCount += 1
            elif char == 'l':
                lCount += 1
            elif char == 'o':
                oCount += 1
            elif char == 'n':
                nCount += 1

        lCount = lCount // 2
        oCount = oCount // 2

        return min(bCount, aCount, lCount, oCount, nCount)

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

В турагентство на удаленку требуются стажеры Клиентов предоставим. Можно без опыта и совмещая с основной работой или декретом. С нас обучение с гарантированной стажировкой. Доход после обучения: от 50 000₽ до 220 000₽. Оплата в процессе обучения зависит от вашей вовлеченности. Задачи: Помогать людям организовывать путешествия: подбор самых выгодных предложений на отдых со скидкой до 50% в новых сервисах бронирования. Условия: ✅ Без опыта — обучение с нуля за 2 месяца, первые выплаты в среднем в течение 2 недель; ✅Удаленная работа или совмещение с офисом (по желанию, зависит от вашего города). Хотите проверить, подойдет ли это вам? Регистрируйтесь на бесплатный вводный урок, на котором узнаете: — как подбирать туры для себя и близких с выгодой до 40% — как получать комиссию 7-10% с каждого тура. Узнать больше #реклама 16+ via-tourism-school.space О рекламодателе

Задача: 377. Combination Sum IV Сложность: medium Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target. Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число. Пример:

Input: nums = [9], target = 3
Output: 0

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

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

    def combinationSum4(self, nums: List[int], target: int) -> int:
        return self.combs(nums, target)

    def combs(self, nums: List[int], remain: int) -> int:
        if remain == 0:
            return 1
        if remain in self.memo:
            return self.memo[remain]

        result = 0
        for num in nums:
            if remain - num >= 0:
                result += self.combs(nums, remain - num)
        
        self.memo[remain] = result
        return result

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

Задача: 863. All Nodes Distance K in Binary Tree Сложность: medium Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла. Ответ можно вернуть в любом порядке. Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя). 2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь. 3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS. 😎 Решение:

class Solution:
    def distanceK(self, root, target, k):
        def add_parent(cur, parent):
            if cur:
                cur.parent = parent
                add_parent(cur.left, cur)
                add_parent(cur.right, cur)
        add_parent(root, None)
        
        answer = []
        visited = set()
        def dfs(cur, distance):
            if not cur or cur in visited:
                return
            visited.add(cur)
            if distance == 0:
                answer.append(cur.val)
                return
            dfs(cur.parent, distance - 1)
            dfs(cur.left, distance - 1)
            dfs(cur.right, distance - 1)
            
        dfs(target, k)
        return answer

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

Задача: 780. Reaching Points Сложность: hard Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false. Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y). Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

👨‍💻 Алгоритм: 1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}. 2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно. 3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy. 😎 Решение:

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while tx >= sx and ty >= sy:
            if sx == tx and sy == ty:
                return True
            if tx > ty:
                tx -= ty
            else:
                ty -= tx
        return False

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

Задача: 250. Count Univalue Subtrees Сложность: medium Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями. Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение. Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

👨‍💻 Алгоритм: 1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0. 2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе: Если узел равен null, верните true. Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left). Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right). Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true. В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false. 3️⃣Верните count. 😎 Решение:

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

class Solution:
    def __init__(self):
        self.count = 0

    def dfs(self, node):
        if not node:
            return True
        
        isLeftUniValue = self.dfs(node.left)
        isRightUniValue = self.dfs(node.right)
        
        if isLeftUniValue and isRightUniValue:
            if node.left and node.left.val != node.val:
                return False
            if node.right and node.right.val != node.val:
                return False
            self.count += 1
            return True
        return False

    def countUnivalSubtrees(self, root):
        self.dfs(root)
        return self.count

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

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 774. Minimize Max Distance to Gas Station Сложность: hard Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k. Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию. Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций. Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

👨‍💻 Алгоритм: 1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x. 2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов. 3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций. 😎 Решение:

class Solution:
    def minmaxGasDist(self, stations: List[int], K: int) -> float:
        N = len(stations)
        deltas = [0] * (N-1)
        for i in range(N-1):
            deltas[i] = stations[i+1] - stations[i]

        dp = [[0] * (K+1) for _ in range(N-1)]
        for i in range(K+1):
            dp[0][i] = deltas[0] / (i+1)

        for p in range(1, N-1):
            for k in range(K+1):
                bns = float('inf')
                for x in range(k+1):
                    bns = min(bns, max(deltas[p] / (x+1), dp[p-1][k-x]))
                dp[p][k] = bns

        return dp[N-2][K]

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