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

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

Задача: 157. Read N Characters Given Read4
Сложность: easy

Предположим, что у вас есть файл, и вы можете читать файл только с помощью данного метода read4. Реализуйте метод для чтения n символов.
Метод read4 читает до 4 символов за раз во временный буфер, и вы должны использовать его, чтобы скопировать максимум n символов в целевой буфер buf.

Пример:

Input: file = "abc", n = 4  
Output: 3

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

1⃣Инициализируем счётчики copiedChars = 0 и readChars = 4, а также создаём временный буфер buf4 размером 4 символа.

2⃣Пока считанные символы меньше n и readChars == 4, читаем с помощью read4(buf4) и посимвольно копируем в buf.

3⃣Если достигли n символов или read4 вернул меньше 4 — завершаем и возвращаем количество считанных символов.

😎 Решение:

type Reader4 interface {
    Read4(buf []byte) int
}

type Solution struct {
    Reader4
}

func (sol *Solution) Read(buf []byte, n int) int {
    copiedChars := 0
    readChars := 4
    buf4 := make([]byte, 4)

    for copiedChars < n && readChars == 4 {
        readChars = sol.Read4(buf4)
        for i := 0; i < readChars; i++ {
            if copiedChars == n {
                return copiedChars
            }
            buf[copiedChars] = buf4[i]
            copiedChars++
        }
    }
    return copiedChars
}

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

package main

type MaxStack struct {
    stack    []int
    maxStack []int
}

func Constructor() MaxStack {
    return MaxStack{}
}

func (this *MaxStack) Push(x int) {
    this.stack = append(this.stack, x)
    if len(this.maxStack) == 0 || x >= this.maxStack[len(this.maxStack)-1] {
        this.maxStack = append(this.maxStack, x)
    }
}

func (this *MaxStack) Pop() int {
    x := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if x == this.maxStack[len(this.maxStack)-1] {
        this.maxStack = this.maxStack[:len(this.maxStack)-1]
    }
    return x
}

func (this *MaxStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MaxStack) PeekMax() int {
    return this.maxStack[len(this.maxStack)-1]
}

func (this *MaxStack) PopMax() int {
    maxVal := this.maxStack[len(this.maxStack)-1]
    this.maxStack = this.maxStack[:len(this.maxStack)-1]
    buffer := []int{}
    for this.stack[len(this.stack)-1] != maxVal {
        buffer = append(buffer, this.stack[len(this.stack)-1])
        this.stack = this.stack[:len(this.stack)-1]
    }
    this.stack = this.stack[:len(this.stack)-1]
    for len(buffer) > 0 {
        this.Push(buffer[len(buffer)-1])
        buffer = buffer[:len(buffer)-1]
    }
    return maxVal
}

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

Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

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

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎 Решение:

import (
    "sort"
)

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    adj := make([][]int, n)
    for _, pair := range pairs {
        adj[pair[0]] = append(adj[pair[0]], pair[1])
        adj[pair[1]] = append(adj[pair[1]], pair[0])
    }

    visited := make([]bool, n)
    sArray := []rune(s)

    var dfs func(node int, indices *[]int, chars *[]rune)
    dfs = func(node int, indices *[]int, chars *[]rune) {
        visited[node] = true
        *indices = append(*indices, node)
        *chars = append(*chars, sArray[node])
        for _, neighbor := range adj[node] {
            if !visited[neighbor] {
                dfs(neighbor, indices, chars)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            indices := []int{}
            chars := []rune{}
            dfs(i, &indices, &chars)
            sort.Ints(indices)
            sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
            for j, index := range indices {
                sArray[index] = chars[j]
            }
        }
    }

    return string(sArray)
}

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

package main

import (
    "sort"
)

type TopVotedCandidate struct {
    times   []int
    leaders []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
    counts := make(map[int]int)
    leader := -1
    leaders := make([]int, len(persons))

    for i, person := range persons {
        counts[person]++
        if counts[person] >= counts[leader] {
            leader = person
        }
        leaders[i] = leader
    }

    return TopVotedCandidate{times, leaders}
}

func (this *TopVotedCandidate) Q(t int) int {
    idx := sort.Search(len(this.times), func(i int) bool {
        return this.times[i] > t
    }) - 1
    return this.leaders[idx]
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

package main

import (
    "container/heap"
    "fmt"
    "math"
    "sort"
)

type Item struct {
    cost, index int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].cost < pq[j].cost
}

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.(*Item))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minCostPath(coins []int, maxJump int) []int {
    n := len(coins)
    if coins[0] == -1 {
        return []int{}
    }

    dp := make([]int, n)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = coins[0]
    path := make([][]int, n)
    for i := range path {
        path[i] = []int{}
    }
    path[0] = []int{1}

    pq := &PriorityQueue{&Item{cost: coins[0], index: 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        current := heap.Pop(pq).(*Item)
        currentCost, i := current.cost, current.index
        if currentCost > dp[i] {
            continue
        }
        for k := 1; k <= maxJump; k++ {
            if i+k < n && coins[i+k] != -1 {
                newCost := currentCost + coins[i+k]
                newPath := append([]int{}, path[i]...)
                newPath = append(newPath, i+k+1)
                if newCost < dp[i+k] || (newCost == dp[i+k] && lexicographicalLess(newPath, path[i+k])) {
                    dp[i+k] = newCost
                    path[i+k] = newPath
                    heap.Push(pq, &Item{cost: newCost, index: i+k})
                }
            }
        }
    }

    if dp[n-1] == math.MaxInt32 {
        return []int{}
    }
    return path[n-1]
}

func lexicographicalLess(a, b []int) bool {
    for i := range a {
        if i >= len(b) {
            return false
        }
        if a[i] != b[i] {
            return a[i] < b[i]
        }
    }
    return len(a) < len(b)
}

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

Задача: 1214. Two Sum BSTs
Сложность: medium

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

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

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

func dfs(node *TreeNode, nodeSet map[int]struct{}) {
    if node == nil {
        return
    }
    dfs(node.Left, nodeSet)
    nodeSet[node.Val] = struct{}{}
    dfs(node.Right, nodeSet)
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
    nodeSet1 := make(map[int]struct{})
    nodeSet2 := make(map[int]struct{})
    dfs(root1, nodeSet1)
    dfs(root2, nodeSet2)
    
    for value1 := range nodeSet1 {
        if _, found := nodeSet2[target - value1]; found {
            return true
        }
    }
    
    return false
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

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

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

package main

import (
    "sort"
)

type Interval struct {
    Start int
    End   int
}

func employeeFreeTime(schedule [][]Interval) []Interval {
    intervals := []Interval{}
    for _, employee := range schedule {
        intervals = append(intervals, employee...)
    }
    
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].Start < intervals[j].Start
    })
    
    merged := []Interval{}
    for _, interval := range intervals {
        if len(merged) == 0 || merged[len(merged)-1].End < interval.Start {
            merged = append(merged, interval)
        } else {
            merged[len(merged)-1].End = max(merged[len(merged)-1].End, interval.End)
        }
    }
    
    freeTime := []Interval{}
    for i := 1; i < len(merged); i++ {
        if merged[i].Start > merged[i-1].End {
            freeTime = append(freeTime, Interval{Start: merged[i-1].End, End: merged[i].Start})
        }
    }
    
    return freeTime
}

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

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

Задача: 957. Prison Cells After N Days
Сложность: medium

Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста.
Каждый день статус камеры, занята она или пуста, меняется по следующим правилам:
Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой.
В противном случае, она становится пустой.
Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей.

Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n.
Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше).

Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

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

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

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

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

😎 Решение:

func cellsToBitmap(cells []int) int {
    stateBitmap := 0
    for _, cell := range cells {
        stateBitmap = (stateBitmap << 1) | cell
    }
    return stateBitmap
}

func nextDay(cells []int) []int {
    newCells := make([]int, len(cells))
    for i := 1; i < len(cells)-1; i++ {
        newCells[i] = 0
        if cells[i-1] == cells[i+1] {
            newCells[i] = 1
        }
    }
    return newCells
}

func prisonAfterNDays(cells []int, N int) []int {
    seen := make(map[int]int)
    isFastForwarded := false

    for N > 0 {
        if !isFastForwarded {
            stateBitmap := cellsToBitmap(cells)
            if _, ok := seen[stateBitmap]; ok {
                N %= seen[stateBitmap] - N
                isFastForwarded = true
            } else {
                seen[stateBitmap] = N
            }
        }

        if N > 0 {
            N--
            cells = nextDay(cells)
        }
    }
    return cells
}

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

Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

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

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:
Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

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

1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список.

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

import "container/heap"

type Order struct {
    price  int
    amount int
}

type MinHeap []Order
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].price < h[j].price }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h

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