Оценка скобок Решение LeetCode

Постановка задачи Оценка скобок Решение LeetCode гласит: Дана сбалансированная строка скобок s и возвращено максимальное количество баллов. Оценка сбалансированной строки скобок основана на следующих правилах: «()» имеет оценку 1. AB имеет оценку A + B, где A и B — сбалансированные строки скобок. (A) имеет оценку 2 * A, где A — это …

Подробнее

Решение LeetCode для обхода двоичного дерева по порядку

Постановка задачи: Неупорядоченный обход двоичного дерева Решение LeetCode Учитывая корень двоичного дерева, вернуть неупорядоченный обход значений его узлов. Пример 1: Ввод: root = [1,null,2,3] Вывод: [1,3,2] Пример 2: Ввод: root = [] Вывод: [] Пример 3: Ввод: root = [1] Вывод: [1] Ограничения: количество узлов в …

Подробнее

Расшифровать строку Leetcode Solution

Постановка проблемы Декодирование строки Решение LeetCode — «Декодирование строки» предлагает вам преобразовать закодированную строку в декодированную строку. Правило кодирования — k[encoded_string], где encoded_string внутри квадратных скобок повторяется ровно k раз, где k — положительное целое число. Пример: Ввод: s = «3[a]2[bc]» Вывод: «aaabcbc» …

Подробнее

Преобразование двоичного дерева в связанный список Решение LeetCode

Преобразование двоичного дерева в связанный список Решение LeetCode говорит, что - Учитывая root бинарного дерева, сгладьте дерево в «связный список»:

  • «Связанный список» должен использовать тот же TreeNode класс, где right дочерний указатель указывает на следующий узел в списке и left дочерний указатель всегда null.
  • «Связанный список» должен быть в том же порядке, что и Предварительный заказ пересечение бинарного дерева.

 

Пример 1:

Преобразование двоичного дерева в связанный список Решение LeetCodeВходной сигнал:

 root = [1,2,5,3,4,null,6]

Вывод:

 [1,null,2,null,3,null,4,null,5,null,6]

Пример 2:

Входной сигнал:

 root = []

Вывод:

 []

Пример 3:

Входной сигнал:

 root = [0]

Вывод:

 [0]

 

АЛГОРИТМ –

ИДЕЯ –

  • Чтобы сгладить двоичное дерево, мы сначала найдем самый правый элемент левого поддерева, и после того, как мы получим самый правый элемент, мы свяжем правый указатель этого узла с правым поддеревом данного дерева.
  • На шаге 2 мы свяжем правый указатель корневого узла с левым поддеревом и установим левое поддерево как нулевое.
  • На шаге 3 теперь наш корневой узел является узлом правого поддерева, тот же процесс произойдет с этим узлом, и процесс будет продолжаться до тех пор, пока все левые части не станут нулевыми.

Подход к сведению двоичного дерева к решению Leetcode для связанного списка —

– Сначала я запущу цикл, т.е. while(root != null), затем возьму две переменные и сохраним левое поддерево.

- затем проверит проверку самого правого узла левого поддерева, используя while(k.left != null), и свяжет этот узел с правым поддеревом, используя (k.right = root.right).

- затем свяжите правый указатель корневого узла с левым поддеревом (root.right = left) и установите левый указатель корневого узла как null (root.left = null) и обновите ( root = root.right ), так что теперь root прав узел поддерева.

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

 

Преобразование двоичного дерева в связанный список Решение LeetCode

Преобразование двоичного дерева в связанный список Решение LeetCode

Решение Python:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

Java-решение:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

Временная сложность: O (N)

Космическая сложность: O (1)

Поскольку мы прошли только один раз, временная сложность будет o(n).

и поскольку мы не занимали никакого дополнительного места, объемная сложность будет равна o(1) постоянному дополнительному пространству.

Аналогичный вопрос - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Добавить решение для двух чисел II Leetcode

Постановка задачи Решение LeetCode «Добавить два числа II» — «Добавить два числа II» утверждает, что два непустых связанных списка представляют два неотрицательных целых числа, в которых старшая значащая цифра идет первой, а каждый узел содержит ровно одну цифру. Нам нужно сложить два числа и вернуть сумму как …

Подробнее

Ежедневная температура Решение Leetcode

Постановка задачи Ежедневные температуры Решение Leetcode: утверждает, что задан массив целых чисел температуры, представляющих дневные температуры, верните ответ в виде массива, такой что answer[i] - это количество дней, которые вам нужно ждать после i-го дня, чтобы получить более теплую температуру. Если нет будущего дня, для которого это возможно, вместо этого оставьте answer[i] == 0. …

Подробнее

Минимальное удаление, чтобы сделать скобки действительными Решение LeetCode

Постановка задачи Минимальное удаление скобок, чтобы сделать их действительными. LeetCode Решение. Вам дана строка s, состоящая из '(', ')' и строчных английских символов. Ваша задача состоит в том, чтобы удалить минимальное количество скобок ( '(' или ')', в любых позициях) так, чтобы результирующая строка скобок была …

Подробнее

Решение для улавливания дождевой воды

Постановка задачи Решение LeetCode для захвата дождевой воды – «Захват дождевой воды» утверждает, что задан массив высот, который представляет собой карту высот, где ширина каждого столбца равна 1. Нам нужно найти количество воды, попавшей в ловушку после дождя. Пример: Ввод: высота = [0,1,0,2,1,0,1,3,2,1,2,1] Вывод: 6 Объяснение: Проверить...

Подробнее

Действительные скобки Решение Leetcode

Постановка задачи Допустимые скобки Решение LeetCode. «Действительные скобки» означают, что вам дана строка, содержащая только символы '(', ')', '{', '}', '[' и ']'. Нам нужно определить, является ли входная строка допустимой строкой или нет. Строка считается корректной, если открытые скобки должны быть закрыты...

Подробнее

Решение с максимальным частотным стеком

Постановка задачи Стек максимальной частоты Решение LeetCode — «Максимальный стек частоты» просит вас спроектировать стек частот, в котором всякий раз, когда мы извлекаем элемент из стека, он должен возвращать наиболее часто встречающийся элемент, присутствующий в стеке. Реализуйте класс FreqStack: FreqStack() создает пустой стек частот. void push(int val) толкает …

Подробнее

Translate »