Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List
Сложность: medium

Преобразуйте двоичное дерево поиска в отсортиров анный кольцевой двусвязный список на месте.

Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом.

Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка.

Пример:
Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

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

1⃣Инициализируйте первые и последние узлы как null.

2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root):
Если узел не равен null:
Вызовите рекурсию для левого поддерева helper(node.left).
Если последний узел не равен null, свяжите последний узел и текущий узел.
Иначе инициализируйте первый узел.
Пометьте текущий узел как последний: last = node.
Вызовите рекурсию для правого поддерева helper(node.right).

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

😎 Решение:

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func helper(node *Node, first **Node, last **Node) {
    if node != nil {
        helper(node.Left, first, last)

        if *last != nil {
            (*last).Right = node
            node.Left = *last
        } else {
            *first = node
        }
        *last = node

        helper(node.Right, first, last)
    }
}

func treeToDoublyList(root *Node) *Node {
    if root == nil {
        return nil
    }

    var first, last *Node
    helper(root, &first, &last)

    last.Right = first
    first.Left = last
    return first
}

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

Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

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

1⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

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

3⃣Верните sentinel.next.

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func deleteNode(head *ListNode, value int) *ListNode {
    sentinel := &ListNode{Next: head}
    prev, curr := sentinel, head

    for curr != nil {
        if curr.Val == value {
            prev.Next = curr.Next
        } else {
            prev = curr
        }
        curr = curr.Next
    }
    return sentinel.Next
}

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

Задача: 965. Univalued Binary Tree
Сложность: easy

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

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

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список.

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

func isUnivalTree(root *TreeNode) bool {
    vals := []int{}
    
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node != nil {
            vals = append(vals, node.Val)
            dfs(node.Left)
            dfs(node.Right)
        }
    }
    
    dfs(root)
    for _, v := range vals {
        if v != vals[0] {
            return false
        }
    }
    return true
}

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

Задача: 604. Design Compressed String Iterator
Сложность: easy

Разработайте и реализуйте итератор для сжатой строки, представленной как чередование букв и чисел, где каждая буква повторяется указанное количество раз.

Методы класса StringIterator:

- Next(): возвращает следующий символ, если остались символы; иначе ' '.
- HasNext(): возвращает true, если остались ещё символы для распаковки.

Пример:

Input: ["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]  
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]  
Output: [null, "L", "e", "e", "t", "C", "o", true, "d", true]

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

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

2⃣Метод Next()
Если есть ещё символы, возвращаем текущий и двигаем указатель ptr вперёд. Если нет — возвращаем пробел ' '.

3⃣Метод HasNext()
Проверяем, остались ли ещё символы в res, сравнивая ptr с длиной.

😎 Решение:

package main

type StringIterator struct {
    res []rune
    ptr int
}

func Constructor(s string) StringIterator {
    res := []rune{}
    i := 0
    for i < len(s) {
        ch := rune(s[i])
        i++
        num := 0
        for i < len(s) && s[i] >= '0' && s[i] <= '9' {
            num = num*10 + int(s[i]-'0')
            i++
        }
        for j := 0; j < num; j++ {
            res = append(res, ch)
        }
    }
    return StringIterator{res: res, ptr: 0}
}

func (this *StringIterator) Next() rune {
    if !this.HasNext() {
        return ' '
    }
    ch := this.res[this.ptr]
    this.ptr++
    return ch
}

func (this *StringIterator) HasNext() bool {
    return this.ptr < len(this.res)
}

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

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

Реализуйте класс MovingAverage:

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

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

3⃣Вычисление скользящего среднего:
Возвращайте текущее скользящее среднее как сумму значений в окне, деленную на количество значений в окне.

😎 Решение:

type MovingAverage struct {
    size int
    queue []int
    sum int
}

func Constructor(size int) MovingAverage {
    return MovingAverage{size: size}
}

func (this *MovingAverage) Next(val int) float64 {
    this.queue = append(this.queue, val)
    this.sum += val
    if len(this.queue) > this.size {
        this.sum -= this.queue[0]
        this.queue = this.queue[1:]
    }
    return float64(this.sum) / float64(len(this.queue))
}

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

Задача: 638. Shopping Offers
Сложность: medium

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

1⃣Рекурсивное вычисление стоимости
Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений.

2⃣Использование специальных предложений
Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение.

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

😎 Решение:

package main

import (
  "fmt"
  "strconv"
  "strings"
)

func shoppingOffers(price []int, special [][]int, needs []int) int {
  memo := make(map[string]int)
  return dfs(price, special, needs, memo)
}

func dfs(price []int, special [][]int, needs []int, memo map[string]int) int {
  key := serialize(needs)
  if val, exists := memo[key]; exists {
    return val
  }

  minPrice := 0
  for i := 0; i < len(needs); i++ {
    minPrice += needs[i] * price[i]
  }

  for _, offer := range special {
    newNeeds := make([]int, len(needs))
    valid := true
    for i := 0; i < len(needs); i++ {
      if needs[i] < offer[i] {
        valid = false
        break
      }
      newNeeds[i] = needs[i] - offer[i]
    }
    if valid {
      minPrice = min(minPrice, offer[len(needs)]+dfs(price, special, newNeeds, memo))
    }
  }

  memo[key] = minPrice
  return minPrice
}

func serialize(needs []int) string {
  var sb strings.Builder
  for _, need := range needs {
    sb.WriteString(strconv.Itoa(need))
    sb.WriteString(",")
  }
  return sb.String()
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

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