Golang | LeetCode

Задача: 1396. Design Underground System
Сложность: medium

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

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.

Пример:
Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.

3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.

😎 Решение:
type UndergroundSystem struct {
journeyData map[string][2]float64
checkInData map[int][2]interface{}
}

func Constructor() UndergroundSystem {
return UndergroundSystem{
journeyData: make(map[string][2]float64),
checkInData: make(map[int][2]interface{}),
}
}

func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
this.checkInData[id] = [2]interface{}{stationName, t}
}

func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
checkIn := this.checkInData[id]
startStation := checkIn[0].(string)
startTime := checkIn[1].(int)
delete(this.checkInData, id)
routeKey := startStation + "->" + stationName
tripTime := float64(t - startTime)
if _, exists := this.journeyData[routeKey]; !exists {
this.journeyData[routeKey] = [2]float64{0, 0}
}
this.journeyData[routeKey][0] += tripTime
this.journeyData[routeKey][1] += 1
}

func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
stats := this.journeyData[startStation+"->"+endStation]
return stats[0] / stats[1]
}

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

Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:
Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

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

1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину.

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:
import "math"

func getSumOfKthPowerOfDigits(n, k int) int {
result := 0
for n != 0 {
digit := n % 10
result += int(math.Pow(float64(digit), float64(k)))
n /= 10
}
return result
}

func isArmstrong(n int) bool {
length := len(strconv.Itoa(n))
return getSumOfKthPowerOfDigits(n, length) == n
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.

3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:
package main

func findRedundantConnection(edges [][]int) []int {
const MAX_EDGE_VAL = 1000
graph := make([][]int, MAX_EDGE_VAL+1)
for i := range graph {
graph[i] = make([]int, 0)
}
seen := make(map[int]bool)

var dfs func(source, target int) bool
dfs = func(source, target int) bool {
if !seen[source] {
seen[source] = true
if source == target {
return true
}
for _, nei := range graph[source] {
if dfs(nei, target) {
return true
}
}
}
return false
}

for _, edge := range edges {
seen = make(map[int]bool)
if len(graph[edge[0]]) > 0 && len(graph[edge[1]]) > 0 && dfs(edge[0], edge[1]) {
return edge
}
graph[edge[0]] = append(graph[edge[0]], edge[1])
graph[edge[1]] = append(graph[edge[1]], edge[0])
}
return nil
}

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:
Input: nums = [4,6,15,35]
Output: 4

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

1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1.

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

3⃣Найти размер наибольшей связной компоненты.

😎 Решение:
package main

import (
"math"
)

func largestComponentSize(nums []int) int {
parent := make(map[int]int)
rank := make(map[int]int)

for _, num := range nums {
parent[num] = num
rank[num] = 0
}

var find func(int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}

union := func(x, y int) {
rootX := find(x)
rootY := find(y)
if rootX != rootY {
if rank[rootX] > rank[rootY] {
parent[rootY] = rootX
} else if rank[rootX] < rank[rootY] {
parent[rootX] = rootY
} else {
parent[rootY] = rootX
rank[rootX]++
}
}
}

primeFactors := func(n int) map[int]struct{} {
factors := make(map[int]struct{})
d := 2
for d*d 1 {
factors[n] = struct{}{}
}
return factors
}

primeToIndex := make(map[int][]int)
for _, num := range nums {
primes := primeFactors(num)
for prime := range primes {
primeToIndex[prime] = append(primeToIndex[prime], num)
}
}

for _, primes := range primeToIndex {
for i := 1; i < len(primes); i++ {
union(primes[0], primes[i])
}
}

size := make(map[int]int)
for _, num := range nums {
root := find(num)
size[root]++
}

maxSize := 0
for _, value := range size {
if value > maxSize {
maxSize = value
}
}

return maxSize
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:
Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список.

3⃣Верните выходной список.

😎 Решение:
package main

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

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
stack1, stack2 := []*TreeNode{}, []*TreeNode{}
output := []int{}

for root1 != nil || root2 != nil || len(stack1) > 0 || len(stack2) > 0 {
for root1 != nil {
stack1 = append(stack1, root1)
root1 = root1.Left
}
for root2 != nil {
stack2 = append(stack2, root2)
root2 = root2.Left
}
if len(stack2) == 0 || (len(stack1) > 0 && stack1[len(stack1)-1].Val

Задача: 941. Valid Mountain Array
Сложность: easy

Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Пример:
Input: arr = [2,1]
Output: false

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

1⃣Убедиться, что длина массива не меньше 3.

2⃣Найти вершину горы, которая удовлетворяет условиям горного массива.
Проверить, что все элементы слева от вершины строго возрастают.
Проверить, что все элементы справа от вершины строго убывают.

3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.

😎 Решение:
package main

func validMountainArray(arr []int) bool {
if len(arr) < 3 {
return false
}

i := 1
for i < len(arr) && arr[i] > arr[i-1] {
i++
}

if i == 1 || i == len(arr) {
return false
}

for i < len(arr) && arr[i] < arr[i-1] {
i++
}

return i == len(arr)
}

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

Задача: 442. Find All Duplicates in an Array
Сложность: medium

Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.

Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.

Пример:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

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

1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива.

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

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

😎 Решение:
func findDuplicates(nums []int) []int {
ans := []int{}

for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[j] == nums[i] {
ans = append(ans, nums[i])
break
}
}
}

return ans
}

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

Задача: 256. Paint House
Сложность: medium

Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.

Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.

Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.

Пример:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

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

1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2].

2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp:
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).

😎 Решение:
func minCost(costs [][]int) int {
n := len(costs)
dp := make([][3]int, n)
dp[0] = [3]int{costs[0][0], costs[0][1], costs[0][2]}

for i := 1; i < n; i++ {
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
}

return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])
}

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

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

Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:
Input: stamp = "abc", target = "ababc"
Output: [0,2]

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

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:
package main

func movesToStamp(stamp string, target string) []int {
s, t := []rune(stamp), []rune(target)
m, n := len(s), len(t)
res := []int{}
done := make([]bool, n)

canStamp := func(i int) bool {
for j := 0; j < m; j++ {
if t[i + j] != '?' && t[i + j] != s[j] {
return false;
}
}
return true;
}

doStamp := func(i int) {
for j := 0; j < m; j++ {
t[i + j] = '?'
}
res = append(res, i)
done[i] = true
}

changed := true
for changed {
changed = false
for i := 0; i

Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи.

Пример:
Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю.

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:
package main

import (
"fmt"
"strings"
)

func toHex(num int) string {
if num == 0 {
return "0"
}
hexChars := "0123456789abcdef"
if num < 0 {
num += 1 0 {
result = append(result, hexChars[num%16])
num /= 16
}
for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
result[i], result[j] = result[j], result[i]
}
return string(result)
}

func main() {
fmt.Println(toHex(26))
fmt.Println(toHex(-1))
}

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

Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium

Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.

Пример:
Input: nums = [3,6,5,1,8]
Output: 18

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

1⃣Найдите сумму всех элементов массива.

2⃣Если сумма делится на 3, то она и есть ответ.

3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 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
        }
    }
}

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза.

Пример:
Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:
package main

import (
"math"
)

func powerfulIntegers(x int, y int, bound int) []int {
a := bound
if x != 1 {
a = int(math.Log(float64(bound)) / math.Log(float64(x)))
}
b := bound
if y != 1 {
b = int(math.Log(float64(bound)) / math.Log(float64(y)))
}
powerfulIntegers := make(map[int]struct{})

for i := 0; i

Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

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

Пример:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:
type Pair struct {
node, mask int
}

func shortestPathLength(graph [][]int) int {
n := len(graph)
if n == 1 {
return 0
}

endingMask := (1

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:
Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.

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

😎 Решение:
package main

func numSubarrayProductLessThanK(nums []int, k int) int {
if k = k {
product /= nums[left]
left++
}
count += right - left + 1
}
return count
}

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

Задача: 1533. Find the Index of the Large Integer
Сложность: medium

У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int compareSub(int l, int r, int x, int y): где 0

Задача: 1250. Check If It Is a Good Array
Сложность: hard

Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False.

Пример:
Input: nums = [12,5,7,23]
Output: true

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

1⃣Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим.

2⃣Если НОД всех чисел больше 1, то массив не считается хорошим

3⃣Получить сумму, равную 1, умножая и складывая элементы.

😎 Решение:
func isGoodArray(nums []int) bool {
    gcd := nums[0]
    for _, num := range nums {
        gcd = gcdFunc(gcd, num)
        if gcd == 1 {
            return true
        }
    }
    return gcd == 1
}

func gcdFunc(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

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

Задача: 532. K-diff Pairs in an Array
Сложность: medium

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

Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣ Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:
func findPairs(nums []int, k int) int {
counter := make(map[int]int)
for _, num := range nums {
counter[num]++
}

result := 0
for x, val := range counter {
if k > 0 {
if _, exists := counter[x + k]; exists {
result++
}
} else if k == 0 && val > 1 {
result++
}
}

return result
}

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

Задача: 229. Majority Element II
Сложность: medium

Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.

Пример:
Input: nums = [3,2,3]
Output: [3]

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

1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.

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

3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.

😎 Решение:
package main

func majorityElement(nums []int) []int {
count1, count2 := 0, 0
var candidate1, candidate2 *int

for _, n := range nums {
if candidate1 != nil && *candidate1 == n {
count1++
} else if candidate2 != nil && *candidate2 == n {
count2++
} else if count1 == 0 {
candidate1 = &n
count1 = 1
} else if count2 == 0 {
candidate2 = &n

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

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:
Input: s = "00110"
Output: 1

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

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).
Пройти по строке и заполнить массивы left и right.

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

😎 Решение:
package main

func minFlipsMonoIncr(s string) int {
n := len(s)
left := make([]int, n+1)
right := make([]int, n+1)

for i := 0; i < n; i++ {
left[i+1] = left[i]
if s[i] == '1' {
left[i+1]++
}
}

for i := n - 1; i >= 0; i-- {
right[i] = right[i+1]
if s[i] == '0' {
right[i]++
}
}

result := n
for i := 0; i

Задача: 672. Bulb Switcher II
Сложность: medium


Дано количество лампочек n (все включены) и количество нажатий presses. Есть 4 кнопки с разной логикой.
Нужно определить, сколько различных состояний лампочек может быть получено после ровно presses нажатий.

Пример:
Input: n = 1, presses = 1` →
Output: 2

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

1⃣Ограничиваем количество лампочек до 6
Поскольку шаблоны переключений кнопок начинают повторяться при n > 6, достаточно проверять только первые min(n, 6) лампочек. Остальные комбинации будут симметричны и не дадут новых состояний.

2⃣Перебираем все возможные комбинации нажатий кнопок
Каждая из 4 кнопок может быть либо нажата, либо нет — всего 2⁴ = 16 комбинаций.
Проверяем каждую комбинацию cand, у которой:
- Кол-во нажатых кнопок bcount ≤ presses
- Чётность bcount % 2 == presses % 2 (так как порядок не важен)

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

😎 Решение:
import (
"math/bits"
)

func flipLights(n int, m int) int {
seen := make(map[int]struct{})
n = min(n, 6)
shift := max(0, 6-n)

for cand := 0; cand < 16; cand++ {
bcount := bits.OnesCount(uint(cand))
if bcount % 2 == m % 2 && bcount >0)&1 > 0 { lights ^= 0b111111 >> shift }
if (cand>>1)&1 > 0 { lights ^= 0b010101 >> shift }
if (cand>>2)&1 > 0 { lights ^= 0b101010 >> shift }
if (cand>>3)&1 > 0 { lights ^= 0b100100 >> shift }
seen[lights] = struct{}{}
}
}

return len(seen)
}

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

func max(a, b int) int {
if a > b {
return a
}
return b
}

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