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

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

3⃣Обработка команд:
Пройдите по всем командам и обновите позицию робота и направление, в котором он движется.
Проверка состояния робота:
После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории.

😎 Решение:

func isRobotBounded(instructions string) bool {
    directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    x, y, direction := 0, 0, 0
    
    for _, instruction := range instructions {
        switch instruction {
        case 'G':
            x += directions[direction][0]
            y += directions[direction][1]
        case 'L':
            direction = (direction + 3) % 4
        case 'R':
            direction = (direction + 1) % 4
        }
    }
    
    return (x == 0 && y == 0) || direction != 0
}

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

type CombinationIterator struct {
    combinations []string
}

func Constructor(characters string, combinationLength int) CombinationIterator {
    var combinations []string
    n, k := len(characters), combinationLength
    for bitmask := 0; bitmask < (1 << n); bitmask++ {
        if bits.OnesCount(uint(bitmask)) == k {
            var curr strings.Builder
            for j := 0; j < n; j++ {
                if bitmask&(1<<(n-j-1)) != 0 {
                    curr.WriteByte(characters[j])
                }
            }
            combinations = append(combinations, curr.String())
        }
    }
    return CombinationIterator{combinations}
}

func (this *CombinationIterator) Next() string {
    n := len(this.combinations)
    res := this.combinations[n-1]
    this.combinations = this.combinations[:n-1]
    return res
}

func (this *CombinationIterator) HasNext() bool {
    return len(this.combinations) > 0
}

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