Задача: 965. Univalued Binary Tree
Сложность: easy
Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.
Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.
Пример:
👨💻 Алгоритм:
1⃣ Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список.
2⃣ Проверьте, что все значения в списке одинаковы.
3⃣ Если все значения одинаковы, верните true, иначе верните false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.
Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.
Пример:
Input: root = [1,1,1,1,1,null,1]
Output: true
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
}Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1
Задача: 604. Design Compressed String Iterator
Сложность: easy
Разработайте и реализуйте итератор для сжатой строки, представленной как чередование букв и чисел, где каждая буква повторяется указанное количество раз.
Методы класса
-
-
Пример:
👨💻 Алгоритм:
1⃣ Предварительная распаковка
Проходим по входной строке. Для каждой буквы считываем следующее число (многозначное возможно) и добавляем нужное количество символов в
2⃣ Метод Next()
Если есть ещё символы, возвращаем текущий и двигаем указатель
3⃣ Метод HasNext()
Проверяем, остались ли ещё символы в
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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]
Проходим по входной строке. Для каждой буквы считываем следующее число (многозначное возможно) и добавляем нужное количество символов в
res.Если есть ещё символы, возвращаем текущий и двигаем указатель
ptr вперёд. Если нет — возвращаем пробел ' '.Проверяем, остались ли ещё символы в
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)
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 346. Moving Average from Data Stream
Сложность: easy
Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне.
Реализуйте класс MovingAverage:
MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.
Пример:
👨💻 Алгоритм:
1⃣ Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.
2⃣ Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.
3⃣ Вычисление скользящего среднего:
Возвращайте текущее скользящее среднее как сумму значений в окне, деленную на количество значений в окне.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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]
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.
Возвращайте текущее скользящее среднее как сумму значений в окне, деленную на количество значений в окне.
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))
}Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 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] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.
Пример:
👨💻 Алгоритм:
1⃣ Рекурсивное вычисление стоимости
Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений.
2⃣ Использование специальных предложений
Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение.
3⃣ Выбор минимальной стоимости
Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений.
Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение.
Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость.
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
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 465. Optimal Account Balancing
Сложность: medium
Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.
Пример:
👨💻 Алгоритм:
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).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.
Пример:
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Игнорировать 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
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 1272. Remove Interval
Сложность: medium
Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.
Пример:
👨💻 Алгоритм:
1⃣ Итерируйтесь по каждому интервалу в списке intervals.
2⃣ Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.
3⃣ Добавляйте непересекающиеся части текущего интервала в результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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]]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
}Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 1041. Robot Bounded In Circle
Сложность: medium
На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.
Пример:
👨💻 Алгоритм:
1⃣ Понимание поведения робота:
Мы анализируем, как робот движется в пределах одной серии команд. Если он вернется в начальную точку или изменит направление после выполнения всех команд, значит, он будет двигаться по замкнутой траектории, что соответствует условию задачи.
2⃣ Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).
3⃣ Обработка команд:
Пройдите по всем командам и обновите позицию робота и направление, в котором он движется.
Проверка состояния робота:
После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.
Пример:
Input: instructions = "GGLLGG"
Output: true
Мы анализируем, как робот движется в пределах одной серии команд. Если он вернется в начальную точку или изменит направление после выполнения всех команд, значит, он будет двигаться по замкнутой траектории, что соответствует условию задачи.
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).
Пройдите по всем командам и обновите позицию робота и направление, в котором он движется.
Проверка состояния робота:
После выполнения всех команд проверьте, вернулся ли робот в начальную точку (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
}Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 1286. Iterator for Combination
Сложность: medium
Создайте класс CombinationIterator:
CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.
Пример:
👨💻 Алгоритм:
1⃣ Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.
2⃣ Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.
3⃣ Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 Falsepackage 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
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 299. Bulls and Cows
Сложность: medium
Вы играете в игру "Быки и коровы" со своим другом.
Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:
Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.
Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.
Пример:
👨💻 Алгоритм:
1⃣ Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.
2⃣ Обход строки guess:
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.
3⃣ Возврат результата:
Верните количество быков и коров в формате "xAyB".
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вы играете в игру "Быки и коровы" со своим другом.
Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:
Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.
Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.
Пример:
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.
Верните количество быков и коров в формате "xAyB".
package main
import (
"fmt"
"strconv"
)
func getHint(secret string, guess string) string {
h := make(map[rune]int)
for _, ch := range secret {
h[ch]++
}
bulls, cows := 0, 0
n := len(guess)
secretArray := []rune(secret)
guessArray := []rune(guess)
for idx := 0; idx < n; idx++ {
ch := guessArray[idx]
if count, ok := h[ch]; ok {
if ch == secretArray[idx] {
bulls++
if count <= 0 {
cows--
}
} else {
if count > 0 {
cows++
}
}
h[ch]--
}
}
return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B"
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: №45. Jump Game II
Сложность: medium
Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0].
Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i.
Другими словами, если вы находитесь в nums[i], вы можете перейти к любому nums[i + j], где:
• 1 <= j <= nums[i]
• i + j < n
Возвращает минимальное количество переходов для достижения nums[n - 1].
Пример:
👨💻 Алгоритм:
1⃣ Использовать переменные
2⃣ Итерироваться по массиву, обновляя
3⃣ Повторять процесс, пока не достигнем последнего индекса.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0].
Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i.
Другими словами, если вы находитесь в nums[i], вы можете перейти к любому nums[i + j], где:
• 1 <= j <= nums[i]
• i + j < n
Возвращает минимальное количество переходов для достижения nums[n - 1].
Пример:
Input: nums = [2,3,1,1,4]
Output: 2
maxReach, end, jumps для отслеживания дальности прыжка, границы текущего шага и количества прыжков. maxReach, и если достигаем границы текущего прыжка, увеличивать счетчик jumps. func jump(nums []int) int {
jumps, end, maxReach := 0, 0, 0
for i := 0; i < len(nums)-1; i++ {
maxReach = max(maxReach, i+nums[i])
if i == end {
jumps++
end = maxReach
}
}
return jumps
}
func max(a, b int) int {
if a > b {
return a
}
return b
}Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Вот отсортированная база с тонной материала (постепенно пополняется):
(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
Please open Telegram to view this post
VIEW IN TELEGRAM
💊1
Задача: 942. DI String Match
Сложность: easy
Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.
Пример:
👨💻 Алгоритм:
1⃣ Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке.
2⃣ Создать массив perm длиной n + 1.
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.
3⃣ Вернуть массив perm.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.
Пример:
Input: s = "IDID"
Output: [0,4,1,3,2]
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.
package main
func diStringMatch(s string) []int {
n := len(s)
low, high := 0, n
perm := make([]int, n+1)
for i := 0; i < n; i++ {
if s[i] == 'I' {
perm[i] = low
low++
} else {
perm[i] = high
high--
}
}
perm[n] = low
return perm
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium
Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.
Пример:
👨💻 Алгоритм:
1⃣ Найдите сумму всех элементов массива.
2⃣ Если сумма делится на 3, то она и есть ответ.
3⃣ Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.
Пример:
Input: nums = [3,6,5,1,8]
Output: 18Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).
import (
"sort"
)
func maxSumDivThree(nums []int) int {
totalSum := 0
for _, num := range nums {
totalSum += num
}
if totalSum % 3 == 0 {
return totalSum
}
mod1 := []int{}
mod2 := []int{}
for _, num := range nums {
if num % 3 == 1 {
mod1 = append(mod1, num)
} else if num % 3 == 2 {
mod2 = append(mod2, num)
}
}
sort.Ints(mod1)
sort.Ints(mod2)
if totalSum % 3 == 1 {
remove1 := int(^uint(0) >> 1) // maximum int
if len(mod1) > 0 {
remove1 = mod1[0]
}
remove2 := int(^uint(0) >> 1)
if len(mod2) >= 2 {
remove2 = mod2[0] + mod2[1]
}
if remove1 < remove2 {
return totalSum - remove1
} else {
return totalSum - remove2
}
} else {
remove2 := int(^uint(0) >> 1)
if len(mod2) > 0 {
remove2 = mod2[0]
}
remove1 := int(^uint(0) >> 1)
if len(mod1) >= 2 {
remove1 = mod1[0] + mod1[1]
}
if remove2 < remove1 {
return totalSum - remove2
} else {
return totalSum - remove1
}
}
}
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM