Задача: 228. Summary Ranges
Сложность: easy

Вам дан отсортированный массив уникальных целых чисел nums.

Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).

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

Каждый диапазон [a,b] в списке должен быть представлен в формате:

"a->b" если a != b
"a" если a == b

Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

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

1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i].

2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики.

3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
)

func summaryRanges(nums []int) []string {
    ranges := []string{}
    i := 0
    for i < len(nums) {
        start := nums[i]
        for i+1 < len(nums) && nums[i]+1 == nums[i+1] {
            i++
        }
        if start != nums[i] {
            ranges = append(ranges, strconv.Itoa(start)+"->"+strconv.Itoa(nums[i]))
        } else {
            ranges = append(ranges, strconv.Itoa(start))
        }
        i++
    }
    return ranges
}

func main() {
    nums := []int{0, 1, 2, 4, 5, 7}
    fmt.Println(summaryRanges(nums))
}

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

Задача: 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
}

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

Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

package main

func minTransfers(transactions [][]int) int {
    creditMap := make(map[int]int)
    for _, t := range transactions {
        creditMap[t[0]] += t[2]
        creditMap[t[1]] -= t[2]
    }
    
    creditList := []int{}
    for _, amount := range creditMap {
        if amount != 0 {
            creditList = append(creditList, amount)
        }
    }
    
    n := len(creditList)
    var dfs func(int) int
    dfs = func(cur int) int {
        for cur < n && creditList[cur] == 0 {
            cur++
        }
        if cur == n {
            return 0
        }
        cost := int(^uint(0) >> 1)
        for nxt := cur + 1; nxt < n; nxt++ {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1))
                creditList[nxt] -= creditList[cur]
            }
        }
        return cost
    }
    
    return dfs(0)
}

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

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

Задача: 1272. Remove Interval
Сложность: medium

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:
Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

1⃣Итерируйтесь по каждому интервалу в списке intervals.

2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.

3⃣Добавляйте непересекающиеся части текущего интервала в результат.

😎 Решение:

func removeInterval(intervals [][]float64, toBeRemoved []float64) [][]float64 {
    result := [][]float64{}
    for _, interval := range intervals {
        if interval[0] < toBeRemoved[0] {
            result = append(result, []float64{interval[0], math.Min(interval[1], toBeRemoved[0])})
        }
        if interval[1] > toBeRemoved[1] {
            result = append(result, []float64{math.Max(interval[0], toBeRemoved[1]), interval[1]})
        }
    }
    return result
}

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