Задача: 554. Brick Wall
Сложность: medium

Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.

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

Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.

Пример:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

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

1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду.

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

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

😎 Решение:

package main

import (
    "math"
)

func leastBricks(wall [][]int) int {
    pos := make([]int, len(wall))
    sum := 0
    res := math.MaxInt32

    for _, el := range wall[0] {
        sum += el
    }

    for sum != 0 {
        count := 0
        for i := 0; i < len(wall); i++ {
            if wall[i][pos[i]] != 0 {
                count++
            } else {
                pos[i]++
            }
            wall[i][pos[i]]--
        }
        sum--
        res = min(res, count)
    }

    return res
}

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

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

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

3⃣Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.

😎 Решение:

func palindromePairs(words []string) [][]int {
    var pairs [][]int
    
    for i := 0; i < len(words); i++ {
        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }
            combined := words[i] + words[j]
            if combined == reverseString(combined) {
                pairs = append(pairs, []int{i, j})
            }
        }
    }
    
    return pairs
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.


2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).


3⃣Верните максимальное значение из dp.

😎 Решение:

package main

import (
  "fmt"
  "math"
)

func lengthOfLIS(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  dp := make([]int, len(nums))
  for i := range dp {
    dp[i] = 1
  }

  for i := 1; i < len(nums); i++ {
    for j := 0; j < i; j++ {
      if nums[i] > nums[j] {
        dp[i] = int(math.Max(float64(dp[i]), float64(dp[j]+1)))
      }
    }
  }

  maxLength := 0
  for _, length := range dp {
    if length > maxLength {
      maxLength = length
    }
  }

  return maxLength
}

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

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

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

package main

func validateStackSequences(pushed []int, popped []int) bool {
    stack := []int{}
    j := 0
    for _, x := range pushed {
        stack = append(stack, x)
        for len(stack) > 0 && j < len(popped) && stack[len(stack)-1] == popped[j] {
            stack = stack[:len(stack)-1]
            j++
        }
    }
    return j == len(popped)
}

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

Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

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

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

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

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

import (
    "math"
    "sort"
)

func numSquarefulPerms(nums []int) int {
    sort.Ints(nums)
    used := make([]bool, len(nums))
    result := make(map[string]bool)
    path := []int{}
    backtrack(nums, used, path, result)
    return len(result)
}

func backtrack(nums []int, used []bool, path []int, result map[string]bool) {
    if len(path) == len(nums) {
        if isSquareful(path) {
            key := makeKey(path)
            result[key] = true
        }
        return
    }
    
    for i := 0; i < len(nums); i++ {
        if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
            continue
        }
        path = append(path, nums[i])
        used[i] = true
        backtrack(nums, used, path, result)
        path = path[:len(path)-1]
        used[i] = false
    }
}

func isSquareful(perm []int) bool {
    for i := 0; i < len(perm)-1; i++ {
        sum := perm[i] + perm[i+1]
        root := int(math.Sqrt(float64(sum)))
        if root*root != sum {
            return false
        }
    }
    return true
}

func makeKey(path []int) string {
    key := ""
    for _, num := range path {
        key += string(num) + ","
    }
    return key
}

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

Задача: 616. Add Bold Tag in String
Сложность: medium

Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов.

Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

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

1⃣Найдите все позиции вхождений подстрок из words в строку s и пометьте эти позиции для выделения тегами <b> и </b>.

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

3⃣Постройте новую строку s, добавляя теги <b> и </b> в определенные позиции.

😎 Решение:

package main

import (
    "strings"
)

func addBoldTag(s string, words []string) string {
    n := len(s)
    bold := make([]bool, n)
    
    for _, word := range words {
        start := strings.Index(s, word)
        for start != -1 {
            for i := start; i < start+len(word); i++ {
                bold[i] = true
            }
            start = strings.Index(s, word, start+1)
        }
    }
    
    var result strings.Builder
    i := 0
    for i < n {
        if bold[i] {
            result.WriteString("<b>")
            for i < n && bold[i] {
                result.WriteByte(s[i])
                i++
            }
            result.WriteString("</b>")
        } else {
            result.WriteByte(s[i])
            i++
        }
    }
    
    return result.String()
}

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

Задача: 951. Flip Equivalent Binary Trees
Сложность: medium

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

Пример:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

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

1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false.

2⃣Если значения корней деревьев не совпадают, вернуть false.
Проверить два условия:
Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева.
Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева.

3⃣Вернуть true, если выполняется хотя бы одно из этих условий.

😎 Решение:

package main

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

func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    }
    if root1 == nil || root2 == nil {
        return false
    }
    if root1.Val != root2.Val {
        return false
    }
    
    return (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) ||
           (flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left))
}

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

package main

import (
    "fmt"
    "sort"
    "strconv"
    "unicode"
)

func countOfAtoms(formula string) string {
    stack := []map[string]int{{}}
    n := len(formula)
    i := 0

    for i < n {
        if formula[i] == '(' {
            stack = append(stack, map[string]int{})
            i++
        } else if formula[i] == ')' {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            i++
            iStart := i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            for name, count := range top {
                stack[len(stack)-1][name] += count * multiplicity
            }
        } else {
            iStart := i
            i++
            for i < n && unicode.IsLower(rune(formula[i])) {
                i++
            }
            name := formula[iStart:i]
            iStart = i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            stack[len(stack)-1][name] += multiplicity
        }
    }

    countMap := stack[0]
    keys := make([]string, 0, len(countMap))
    for key := range countMap {
        keys = append(keys, key)
    }
    sort.Strings(keys)
    result := ""
    for _, name := range keys {
        result += name
        if countMap[name] > 1 {
            result += strconv.Itoa(countMap[name])
        }
    }
    return result
}

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

Задача: 187. Repeated DNA Sequences
Сложность: medium

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.

Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.

Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке.

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

2⃣Проверяем хеш в хешсете:
Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод.
В противном случае добавляем хеш в хешсет.

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

😎 Решение:

type MyCircularQueue struct {
    queue     []int
    tailIndex int
    capacity  int
}

func CreateMyCircularQueue(capacity int) MyCircularQueue {
    return MyCircularQueue{make([]int, capacity), 0, capacity}
}

func (q *MyCircularQueue) enQueue(value int) {
    q.queue[q.tailIndex] = value
    q.tailIndex = (q.tailIndex + 1) % q.capacity
}

func (q *MyCircularQueue) get(index int) int

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

Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

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

1⃣Обход всей сетки:
- Если найден '1', запускаем поиск в глубину (DFS).

2⃣DFS для пометки острова:
- Заменяем '1' на '0', чтобы избежать повторного посещения.
- Рекурсивно вызываем DFS для всех четырёх направлений.

3⃣Подсчет островов:
- Каждый запуск DFS означает новый остров.
- Увеличиваем счетчик островов.

😎 Решение:

package main

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    numIslands := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                numIslands++
            }
        }
    }
    return numIslands
}

func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
        return
    }

    grid[r][c] = '0'
    dfs(grid, r-1, c)
    dfs(grid, r+1, c)
    dfs(grid, r, c-1)
    dfs(grid, r, c+1)
}

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

Задача: 387. First Unique Character in a String
Сложность: easy

Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.

Пример:

Input: s = "leetcode"
Output: 0

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

1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице.

2⃣Пройдите по строке снова и проверьте для каждого символа, является ли его количество появлений в хеш-таблице равным 1.

3⃣Если найдется символ с количеством появлений, равным 1, верните его индекс. Если такой символ не найден, верните -1.

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type Solution struct {
  original []int
  array    []int
}

func Constructor(nums []int) Solution {
  original := make([]int, len(nums))
  copy(original, nums)
  return Solution{
    original: original,
    array:    append([]int(nil), nums...),
  }
}

func (this *Solution) Reset() []int {
  this.array = append([]int(nil), this.original...)
  return this.original
}

func (this *Solution) Shuffle() []int {
  rand.Seed(time.Now().UnixNano())
  for i := range this.array {
    randIndex := rand.Intn(len(this.array)-i) + i
    this.array[i], this.array[randIndex] = this.array[randIndex], this.array[i]
  }
  return this.array
}

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

Задача: 312. Burst Balloons
Сложность: hard

Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.

Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.

Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.

Пример:

Input: nums = [1,5]
Output: 10

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

1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.

2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.

3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.

😎 Решение:

func maxCoins(nums []int) int {
    n := len(nums)
    newNums := make([]int, n+2)
    newNums[0] = 1
    newNums[n+1] = 1
    for i := 0; i < n; i++ {
        newNums[i+1] = nums[i]
    }
    
    dp := make([][]int, n+2)
    for i := range dp {
        dp[i] = make([]int, n+2)
    }
    
    for length := 2; length < n+2; length++ {
        for left := 0; left < n+2-length; left++ {
            right := left + length
            for i := left + 1; i < right; i++ {
                dp[left][right] = max(dp[left][right],
                                      newNums[left]*newNums[i]*newNums[right] + dp[left][i] + dp[i][right])
            }
        }
    }
    
    return dp[0][n+1]
}

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

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

package main

import (
    "strings"
)

func addBoldTags(keywords []string, s string) string {
    n := len(s)
    bold := make([]bool, n)
    
    for _, word := range keywords {
        start := strings.Index(s, word)
        for start != -1 {
            for i := start; i < start+len(word); i++ {
                bold[i] = true
            }
            start = strings.Index(s, word, start+1)
        }
    }
    
    var result strings.Builder
    i := 0
    for i < n {
        if bold[i] {
            result.WriteString("<b>")
            for i < n && bold[i] {
                result.WriteByte(s[i])
                i++
            }
            result.WriteString("</b>")
        } else {
            result.WriteByte(s[i])
            i++
        }
    }
    
    return result.String()
}

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

Задача: 118. Pascal's Triangle
Сложность: easy

Дано целое число numRows. Верните первые numRows строк треугольника Паскаля.

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

Пример:

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

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

1⃣Инициализация:
- Создаем список triangle, в котором каждая строка — отдельный срез ([]int).
- Первая строка всегда [1].

2⃣Генерация строк:
- Для каждой строки i от 1 до numRows - 1:
- Добавляем 1 в начало строки.
- Каждое внутреннее число — сумма двух чисел из предыдущей строки.
- Добавляем 1 в конец строки.

3⃣Результат:
- Возвращаем triangle после генерации всех строк.

😎 Решение:

func generate(numRows int) [][]int {
    triangle := make([][]int, numRows)
    triangle[0] = []int{1}
    for rowNum := 1; rowNum < numRows; rowNum++ {
        prevRow := triangle[rowNum-1]
        row := make([]int, 0, rowNum+1)
        row = append(row, 1)
        for j := 1; j < rowNum; j++ {
            row = append(row, prevRow[j-1]+prevRow[j])
        }
        row = append(row, 1)
        triangle[rowNum] = row
    }
    return triangle
}

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

Задача: 171. Excel Sheet Column Number
Сложность: easy

Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.

Пример:

Input: columnTitle = "A"
Output: 1

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

1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1).

2⃣Инициализируйте переменную-аккумулятор result.

3⃣Начиная справа налево, вычислите значение символа в
зависимости от его позиции и добавьте его к result.

😎 Решение:

func titleToNumber(s string) int {
    result := 0

    alpha_map := make(map[rune]int)
    for i := 0; i < 26; i++ {
        alpha_map[rune(i + 65)] = i + 1
    }

    n := len(s)
    for i := 0; i < n; i++ {
        cur_char := rune(s[n - 1 - i])
        result += alpha_map[cur_char] * pow(26, i)
    }
    return result
}

func pow(x int, y int) int {
    result := 1
    for i := 0; i < y; i++ {
        result *= x
    }
    return result
}

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

Задача: 499. The Maze III
Сложность: hard

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

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

package main

import (
  "container/heap"
)

type State struct {
  row, col, dist int
  path           string
}

type PriorityQueue []*State

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist || (pq[i].dist == pq[j].dist && pq[i].path < pq[j].path) }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*State)) }
func (pq *PriorityQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  *pq = old[:n-1]
  return item
}

var directions = [4][2]int{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}
var textDirections = []string{"l", "u", "r", "d"}

func findShortestWay(maze [][]int, ball, hole []int) string {
  m, n := len(maze), len(maze[0])
  pq := &PriorityQueue{}
  heap.Init(pq)
  heap.Push(pq, &State{ball[0], ball[1], 0, ""})
  seen := make([][]bool, m)
  for i := range seen {
    seen[i] = make([]bool, n)
  }

  for pq.Len() > 0 {
    curr := heap.Pop(pq).(*State)
    if seen[curr.row][curr.col] {
      continue
    }
    if curr.row == hole[0] && curr.col == hole[1] {
      return curr.path
    }
    seen[curr.row][curr.col] = true

    for i := 0; i < 4; i++ {
      dy, dx := directions[i][0], directions[i][1]
      currRow, currCol, dist := curr.row, curr.col, 0
      for currRow+dy >= 0 && currRow+dy < m && currCol+dx >= 0 && currCol+dx < n && maze[currRow+dy][currCol+dx] == 0 {
        currRow += dy
        currCol += dx
        dist++
        if currRow == hole[0] && currCol == hole[1] {
          break
        }
      }
      heap.Push(pq, &State{currRow, currCol, curr.dist + dist, curr.path + textDirections[i]})
    }
  }
  return "impossible"
}

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

Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]
Output: [1,2]

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

1⃣Сортировка:
Сначала отсортируем массив камней.

2⃣Максимальное количество ходов:
Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.

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

😎 Решение:

import (
    "sort"
)

func numMovesStonesII(stones []int) []int {
    sort.Ints(stones)
    n := len(stones)
    
    maxMoves := stones[n-1] - stones[0] + 1 - n
    maxMoves -= min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1)

    minMoves := int(^uint(0) >> 1) // max int
    j := 0

    for i := 0; i < n; i++ {
        for j < n && stones[j] - stones[i] + 1 <= n {
            j++
        }
        alreadyInWindow := j - i
        if alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1 {
            minMoves = min(minMoves, 2)
        } else {
            minMoves = min(minMoves, n - alreadyInWindow)
        }
    }

    return []int{minMoves, maxMoves}
}

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

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

Задача: 267. Palindrome Permutation II
Сложность: medium

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

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

2⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

package main

import (
  "fmt"
  "strings"
)

type Solution struct {
  set map[string]struct{}
}

func NewSolution() *Solution {
  return &Solution{set: make(map[string]struct{})}
}

func (sol *Solution) generatePalindromes(s string) []string {
  mapChars := make([]int, 128)
  st := make([]rune, len(s)/2)
  if !sol.canPermutePalindrome(s, mapChars) {
    return []string{}
  }

  var ch rune
  k := 0
  for i := 0; i < len(mapChars); i++ {
    if mapChars[i]%2 == 1 {
      ch = rune(i)
    }
    for j := 0; j < mapChars[i]/2; j++ {
      st[k] = rune(i)
      k++
    }
  }
  sol.permute(st, 0, ch)
  result := []string{}
  for key := range sol.set {
    result = append(result, key)
  }
  return result
}

func (sol *Solution) canPermutePalindrome(s string, mapChars []int) bool {
  count := 0
  for _, char := range s {
    index := int(char)
    mapChars[index]++
    if mapChars[index]%2 == 0 {
      count--
    } else {
      count++
    }
  }
  return count <= 1
}

func (sol *Solution) swap(s []rune, i, j int) {
  s[i], s[j] = s[j], s[i]
}

func (sol *Solution) permute(s []rune, l int, ch rune) {
  if l == len(s) {
    var sb strings.Builder
    sb.WriteString(string(s))
    if ch != 0 {
      sb.WriteRune(ch)
    }
    for i := len(s) - 1; i >= 0; i-- {
      sb.WriteRune(s[i])
    }
    sol.set[sb.String()] = struct{}{}
  } else {
    for i := l; i < len(s); i++ {
      if s[l] != s[i] || l == i {
        sol.swap(s, l, i)
        sol.permute(s, l+1, ch)
        sol.swap(s, l, i)
      }
    }
  }
}

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

Задача: 724. Find Pivot Index
Сложность: easy

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

1⃣Вычислите сумму всех элементов массива.

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

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

package main

func pivotIndex(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    leftSum := 0
    for i, num := range nums {
        if leftSum == totalSum - leftSum - num {
            return i
        }
        leftSum += num
    }
    return -1
}

func main() {
    nums := []int{1, 7, 3, 6, 5, 6}
    result := pivotIndex(nums)
    println(result)
}

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

2⃣Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.

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

😎 Решение:

package main

import "fmt"

type Solution struct{}

func (s *Solution) maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    maxCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '0' {
                hits := s.killEnemies(row, col, grid)
                if hits > maxCount {
                    maxCount = hits
                }
            }
        }
    }

    return maxCount
}

func (s *Solution) killEnemies(row, col int, grid [][]byte) int {
    enemyCount := 0
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range directions {
        r, c := row+dir[0], col+dir[1]

        for r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) {
            if grid[r][c] == 'W' {
                break
            }
            if grid[r][c] == 'E' {
                enemyCount++
            }
            r += dir[0]
            c += dir[1]
        }
    }

    return enemyCount
}

func main() {
    grid := [][]byte{
        {'0', 'E', '0', '0'},
        {'E', '0', 'W', 'E'},
        {'0', 'E', '0', '0'},
    }

    sol := Solution{}
    fmt.Println(sol.maxKilledEnemies(grid)) 
}

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

Задача: 764. Largest Plus Sign
Сложность: medium

В сетке n x n с нулями в mines, найдите максимальный порядок +-образного креста из 1, где центр и лучи длины k-1 идут строго вверх, вниз, влево и вправо.

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2

Пояснение: максимальный крест — центр в (2,2), лучи по длине 1 во все стороны.

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

1⃣Инициализация сетки
Создаём матрицу grid n x n, заполняем единицами, и для каждого [x, y] из mines выставляем grid[x][y] = 0.

2⃣Динамика в 4 направлениях
Создаём 4 матрицы:
- left[i][j] — длина непрерывных 1 слева от (i,j)
- right[i][j] — справа
- up[i][j] — сверху
- down[i][j] — снизу
Каждую заполняем проходом по строкам/столбцам.

3⃣Определение порядка
Для каждой ячейки (i, j) считаем order = min(left[i][j], right[i][j], up[i][j], down[i][j]).
Ответ — максимальный order.

Решение (оптимизированное O(n²) с динамикой):

func orderOfLargestPlusSign(n int, mines [][]int) int {
    grid := make([][]int, n)
    for i := range grid {
        grid[i] = make([]int, n)
        for j := range grid[i] {
            grid[i][j] = n // максимальная возможная длина
        }
    }

    for _, mine := range mines {
        grid[mine[0]][mine[1]] = 0
    }

    for i := 0; i < n; i++ {
        count := 0
        for j := 0; j < n; j++ { // слева направо
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }

        count = 0
        for j := n - 1; j >= 0; j-- { // справа налево
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }
    }

    for j := 0; j < n; j++ {
        count := 0
        for i := 0; i < n; i++ { // сверху вниз
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }

        count = 0
        for i := n - 1; i >= 0; i-- { // снизу вверх
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }
    }

    res := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            res = max(res, grid[i][j])
        }
    }

    return res
}

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
}

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