#hard
Задача: 446. Arithmetic Slices II - Subsequence


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

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

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

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

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

type Solution struct {
    n   int
    ans int
}

func (sol *Solution) dfs(dep int, A []int, cur []int64) {
    if dep == sol.n {
        if len(cur) < 3 {
            return
        }
        for i := 1; i < len(cur); i++ {
            if cur[i]-cur[i-1] != cur[1]-cur[0] {
                return
            }
        }
        sol.ans++
        return
    }
    sol.dfs(dep+1, A, cur)
    cur = append(cur, int64(A[dep]))
    sol.dfs(dep+1, A, cur)
    cur = cur[:len(cur)-1]
}

func numberOfArithmeticSlices(A []int) int {
    sol := Solution{n: len(A), ans: 0}
    sol.dfs(0, A, []int64{})
    return sol.ans
}

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

#hard
Задача: 591. Tag Validator

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

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

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

package main

import (
    "regexp"
    "strings"
)

type Solution struct {
    stack       []string
    containsTag bool
}

func (s *Solution) isValidTagName(tag string, ending bool) bool {
    if ending {
        if len(s.stack) > 0 && s.stack[len(s.stack)-1] == tag {
            s.stack = s.stack[:len(s.stack)-1]
        } else {
            return false
        }
    } else {
        s.containsTag = true
        s.stack = append(s.stack, tag)
    }
    return true
}

func (s *Solution) IsValid(code string) bool {
    regex := "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
    matched, _ := regexp.MatchString(regex, code)
    if !matched {
        return false
    }

    for i := 0; i < len(code); i++ {
        ending := false
        if len(s.stack) == 0 && s.containsTag {
            return false
        }
        if code[i] == '<' {
            if code[i+1] == '!' {
                i = strings.Index(code[i+1:], "]]>") + i + 2
                if i == -1 {
                    return false
                }
                continue
            }
            if code[i+1] == '/' {
                i++
                ending = true
            }
            closeIndex := strings.Index(code[i+1:], ">") + i + 1
            if closeIndex == -1 || !s.isValidTagName(code[i+1:closeIndex], ending) {
                return false
            }
            i = closeIndex
        }
    }
    return len(s.stack) == 0
}

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

#hard
Задача: 710. Random Pick with Blacklist

Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.

Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

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

1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

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

3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type Solution struct {
  mapping map[int]int
  bound   int
}

func Constructor(n int, blacklist []int) Solution {
  mapping := make(map[int]int)
  bound := n - len(blacklist)
  blackset := make(map[int]struct{})
  for _, b := range blacklist {
    blackset[b] = struct{}{}
  }
  whitelist := bound
  for _, b := range blacklist {
    if b < bound {
      for {
        if _, exists := blackset[whitelist]; !exists {
          break
        }
        whitelist++
      }
      mapping[b] = whitelist
      whitelist++
    }
  }
  return Solution{mapping: mapping, bound: bound}
}

func (this *Solution) Pick() int {
  r := rand.Intn(this.bound)
  if mapped, exists := this.mapping[r]; exists {
    return mapped
  }
  return r
}

func main() {
  rand.Seed(time.Now().UnixNano())
}

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

#hard
Задача: 765. Couples Holding Hands

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

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

😎 Решение:

type Solution struct {
    N     int
    pairs [][]int
}

func (s *Solution) minSwapsCouples(row []int) int {
    s.N = len(row) / 2
    s.pairs = make([][]int, s.N)
    for i := 0; i < s.N; i++ {
        s.pairs[i] = []int{row[2*i] / 2, row[2*i+1] / 2}
    }
    return s.solve(0)
}

func (s *Solution) swap(a, b, c, d int) {
    t := s.pairs[a][b]
    s.pairs[a][b] = s.pairs[c][d]
    s.pairs[c][d] = t
}

func (s *Solution) solve(i int) int {
    if i == s.N {
        return 0
    }
    x, y := s.pairs[i][0], s.pairs[i][1]
    if x == y {
        return s.solve(i + 1)
    }

    var jx, kx, jy, ky int
    for j := i + 1; j < s.N; j++ {
        for k := 0; k <= 1; k++ {
            if s.pairs[j][k] == x {
                jx, kx = j, k
            }
            if s.pairs[j][k] == y {
                jy, ky = j, k
            }
        }
    }

    s.swap(i, 1, jx, kx)
    ans1 := 1 + s.solve(i+1)
    s.swap(i, 1, jx, kx)

    s.swap(i, 0, jy, ky)
    ans2 := 1 + s.solve(i+1)
    s.swap(i, 0, jy, ky)

    if ans1 < ans2 {
        return ans1
    }
    return ans2
}

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

#hard
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

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

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

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

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

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

😎 Решение:

package main

import (
  "sort"
  "strconv"
  "strings"
)

func numDistinctIslands2(grid [][]int) int {
  uniqueIslands := make(map[string]struct{})

  for i := 0; i < len(grid); i++ {
    for j := 0; j < len(grid[0]); j++ {
      if grid[i][j] == 1 {
        shape := [][]int{}
        dfs(grid, i, j, i, j, &shape)
        uniqueIslands[normalize(shape)] = struct{}{}
      }
    }
  }

  return len(uniqueIslands)
}

func dfs(grid [][]int, i, j, baseI, baseJ int, shape *[][]int) {
  if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
    return
  }
  grid[i][j] = 0
  *shape = append(*shape, []int{i - baseI, j - baseJ})
  dfs(grid, i+1, j, baseI, baseJ, shape)
  dfs(grid, i-1, j, baseI, baseJ, shape)
  dfs(grid, i, j+1, baseI, baseJ, shape)
  dfs(grid, i, j-1, baseI, baseJ, shape)
}

func normalize(shape [][]int) string {
  shapes := make([][][]int, 8)
  for i := range shapes {
    shapes[i] = [][]int{}
  }

  for _, p := range shape {
    x, y := p[0], p[1]
    shapes[0] = append(shapes[0], []int{x, y})
    shapes[1] = append(shapes[1], []int{x, -y})
    shapes[2] = append(shapes[2], []int{-x, y})
    shapes[3] = append(shapes[3], []int{-x, -y})
    shapes[4] = append(shapes[4], []int{y, x})
    shapes[5] = append(shapes[5], []int{y, -x})
    shapes[6] = append(shapes[6], []int{-y, x})
    shapes[7] = append(shapes[7], []int{-y, -x})
  }

  for i := range shapes {
    sort.Slice(shapes[i], func(a, b int) bool {
      if shapes[i][a][0] == shapes[i][b][0] {
        return shapes[i][a][1] < shapes[i][b][1]
      }
      return shapes[i][a][0] < shapes[i][b][0]
    })
  }

  minShape := shapeToString(shapes[0])
  for _, s := range shapes {
    shapeStr := shapeToString(s)
    if shapeStr < minShape {
      minShape = shapeStr
    }
  }

  return minShape
}

func shapeToString(shape [][]int) string {
  var sb strings.Builder
  for _, p := range shape {
    sb.WriteString(strconv.Itoa(p[0]))
    sb.WriteString(",")
    sb.WriteString(strconv.Itoa(p[1]))
    sb.WriteString(";")
  }
  return sb.String()
}

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

#hard
Задача: 774. Minimize Max Distance to Gas Station

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.

Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.

Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

func minmaxGasDist(stations []int, K int) float64 {
    N := len(stations)
    deltas := make([]float64, N-1)
    for i := 0; i < N-1; i++ {
        deltas[i] = float64(stations[i+1] - stations[i])
    }

    dp := make([][]float64, N-1)
    for i := range dp {
        dp[i] = make([]float64, K+1)
    }
    for i := 0; i <= K; i++ {
        dp[0][i] = deltas[0] / float64(i+1)
    }

    for p := 1; p < N-1; p++ {
        for k := 0; k <= K; k++ {
            bns := 1e9
            for x := 0; x <= k; x++ {
                bns = math.Min(bns, math.Max(deltas[p] / float64(x+1), dp[p-1][k-x]))
            }
            dp[p][k] = bns
        }
    }

    return dp[N-2][K]
}

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

#hard
Задача: 716. Max Stack

Разработайте структуру данных 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
}

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

#hard
Задача: 719. Find K-th Smallest Pair Distance

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎 Решение:

package main

import (
    "sort"
)

func countPairs(nums []int, mid int) int {
    count := 0
    j := 0
    for i := 0; i < len(nums); i++ {
        for j < len(nums) && nums[j] - nums[i] <= mid {
            j++
        }
        count += j - i - 1
    }
    return count
}

func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    left, right := 0, nums[len(nums) - 1] - nums[0]
    for left < right {
        mid := (left + right) / 2
        if countPairs(nums, mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

#hard
Задача: 489. Robot Room Cleaner

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

Разработайте алгоритм для очистки всей комнаты, используя следующие API:

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

1⃣Пометьте текущую ячейку как посещенную и очистите её.

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

3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎 Решение:

type Solution struct {
    robot     *Robot
    visited   map[[2]int]bool
    directions [4][2]int
}

func (s *Solution) goBack() {
    s.robot.TurnRight()
    s.robot.TurnRight()
    s.robot.Move()
    s.robot.TurnRight()
    s.robot.TurnRight()
}

func (s *Solution) backtrack(row, col, d int) {
    s.visited[[2]int{row, col}] = true
    s.robot.Clean()
    for i := 0; i < 4; i++ {
        newD := (d + i) % 4
        newRow := row + s.directions[newD][0]
        newCol := col + s.directions[newD][1]
        if !s.visited[[2]int{newRow, newCol}] && s.robot.Move() {
            s.backtrack(newRow, newCol, newD)
            s.goBack()
        }
        s.robot.TurnRight()
    }
}

func (s *Solution) CleanRoom(robot *Robot) {
    s.robot = robot
    s.visited = make(map[[2]int]bool)
    s.directions = [4][2]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
    s.backtrack(0, 0, 0)
}

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

#hard
Задача: 499. The Maze III

В лабиринте есть мячик с пустыми пространствами (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"
}

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

#hard
Задача: 502. IPO

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

Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала.

Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу.

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

Ответ гарантированно поместится в 32-битное целое число со знаком.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

1⃣Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.

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

3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
    projects := make([][2]int, len(profits))
    for i := range profits {
        projects[i] = [2]int{capital[i], profits[i]}
    }
    sort.Slice(projects, func(i, j int) bool {
        return projects[i][0] < projects[j][0]
    })

    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    ptr := 0

    for i := 0; i < k; i++ {
        for ptr < len(projects) && projects[ptr][0] <= w {
            heap.Push(maxHeap, projects[ptr][1])
            ptr++
        }
        if maxHeap.Len() == 0 {
            break
        }
        w += heap.Pop(maxHeap).(int)
    }

    return w
}

type MaxHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

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

#hard
Задача: 726. Number of Atoms

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 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
}

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

#hard
Задача: 727. Minimum Window Subsequence

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

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

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

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

😎 Решение:

package main

func minWindow(s1 string, s2 string) string {
    if len(s1) == 0 || len(s2) == 0 {
        return ""
    }

    dictT := make(map[rune]int)
    for _, c := range s2 {
        dictT[c]++
    }

    required := len(dictT)
    l, r := 0, 0
    formed := 0
    windowCounts := make(map[rune]int)
    ans := []int{int(^uint(0) >> 1), 0, 0}

    for r < len(s1) {
        c := rune(s1[r])
        windowCounts[c]++

        if count, ok := dictT[c]; ok && windowCounts[c] == count {
            formed++
        }

        for l <= r && formed == required {
            c = rune(s1[l])

            if r-l+1 < ans[0] {
                ans[0] = r - l + 1
                ans[1] = l
                ans[2] = r
            }

            windowCounts[c]--
            if count, ok := dictT[c]; ok && windowCounts[c] < count {
                formed--
            }

            l++
        }

        r++
    }

    if ans[0] == int(^uint(0)>>1) {
        return ""
    }

    return s1[ans[1] : ans[2]+1]
}

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

#hard
Задача: 728. Self Dividing Numbers

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

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

3⃣Добавьте саморазделяющиеся числа в результативный список и верните его.

😎 Решение:

package main

func selfDividingNumbers(left int, right int) []int {
    var result []int
    for num := left; num <= right; num++ {
        if isSelfDividing(num) {
            result = append(result, num)
        }
    }
    return result
}

func isSelfDividing(num int) bool {
    n := num
    for n > 0 {
        digit := n % 10
        if digit == 0 || num % digit != 0 {
            return false
        }
        n /= 10
    }
    return true
}

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

#hard
Задача: 730. Count Different Palindromic Subsequences

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

package main

func countPalindromicSubsequences(s string) int {
    const MOD = 1000000007
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for i := 0; i < n; i++ {
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                l, r := i+1, j-1
                for l <= r && s[l] != s[i] {
                    l++
                }
                for l <= r && s[r] != s[j] {
                    r--
                }
                if l > r {
                    dp[i][j] = dp[i+1][j-1]*2 + 2
                } else if l == r {
                    dp[i][j] = dp[i+1][j-1]*2 + 1
                } else {
                    dp[i][j] = dp[i+1][j-1]*2 - dp[l+1][r-1]
                }
            } else {
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD
        }
    }

    return dp[0][n-1]
}

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

#hard
Задача: 732. My Calendar III

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

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

2⃣Для каждого нового события обновите словари начала и конца событий.

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

😎 Решение:

package main

import "sort"

type MyCalendarThree struct {
    events map[int]int
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{events: make(map[int]int)}
}

func (this *MyCalendarThree) Book(startTime int, endTime int) int {
    this.events[startTime]++
    this.events[endTime]--
    
    times := make([]int, 0, len(this.events))
    for time := range this.events {
        times = append(times, time)
    }
    sort.Ints(times)
    
    active := 0
    maxActive := 0
    for _, time := range times {
        active += this.events[time]
        if active > maxActive {
            maxActive = active
        }
    }
    
    return maxActive
}

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

#hard
Задача: 736. Parse Lisp Expression

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

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

😎 Решение:

package main

import (
    "strconv"
    "strings"
)

func evaluate(expression string) int {
    return evaluateExpression(expression, map[string]int{})
}

func evaluateExpression(expression string, env map[string]int) int {
    if expression[0] != '(' {
        if val, err := strconv.Atoi(expression); err == nil {
            return val
        }
        return env[expression]
    }

    tokens := tokenize(expression)
    if tokens[0] == "let" {
        for i := 1; i < len(tokens)-2; i += 2 {
            env[tokens[i]] = evaluateExpression(tokens[i+1], env)
        }
        return evaluateExpression(tokens[len(tokens)-1], env)
    } else if tokens[0] == "add" {
        return evaluateExpression(tokens[1], env) + evaluateExpression(tokens[2], env)
    } else if tokens[0] == "mult" {
        return evaluateExpression(tokens[1], env) * evaluateExpression(tokens[2], env)
    }
    return 0
}

func tokenize(expression string) []string {
    tokens := []string{}
    token := ""
    parens := 0
    for _, char := range expression {
        switch char {
        case '(':
            parens++
            if parens == 1 {
                continue
            }
        case ')':
            parens--
            if parens == 0 {
                tokens = append(tokens, tokenize(token)...)
                token = ""
                continue
            }
        case ' ':
            if parens == 1 {
                if token != "" {
                    tokens = append(tokens, token)
                    token = ""
                }
                continue
            }
        }
        token += string(char)
    }
    if token != "" {
        tokens = append(tokens, token)
    }
    return tokens
}

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

#hard
Задача: 741. Cherry Pickup

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

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

😎 Решение:

package main

import "math"

func cherryPickup(grid [][]int) int {
    n := len(grid)
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 2*n-1)
            for k := range dp[i][j] {
                dp[i][j][k] = math.MinInt32
            }
        }
    }
    dp[0][0][0] = grid[0][0]

    for k := 1; k < 2*n-1; k++ {
        for i1 := max(0, k-n+1); i1 <= min(n-1, k); i1++ {
            for i2 := max(0, k-n+1); i2 <= min(n-1, k); i2++ {
                j1, j2 := k-i1, k-i2
                if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
                    maxCherries := math.MinInt32
                    if i1 > 0 && i2 > 0 {
                        maxCherries = max(maxCherries, dp[i1-1][i2-1][k-1])
                    }
                    if i1 > 0 {
                        maxCherries = max(maxCherries, dp[i1-1][i2][k-1])
                    }
                    if i2 > 0 {
                        maxCherries = max(maxCherries, dp[i1][i2-1][k-1])
                    }
                    maxCherries = max(maxCherries, dp[i1][i2][k-1])
                    if maxCherries != math.MinInt32 {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1]
                        if i1 != i2 {
                            dp[i1][i2][k] += grid[i2][j2]
                        }
                    }
                }
            }
        }
    }

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

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

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

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

#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

package main

type WordFilter struct {
    prefixSuffixMap map[string]int
}

func Constructor(words []string) WordFilter {
    prefixSuffixMap := make(map[string]int)
    for index, word := range words {
        length := len(word)
        for prefixLength := 1; prefixLength <= length; prefixLength++ {
            for suffixLength := 1; suffixLength <= length; suffixLength++ {
                prefix := word[:prefixLength]
                suffix := word[length-suffixLength:]
                key := prefix + "#" + suffix
                prefixSuffixMap[key] = index
            }
        }
    }
    return WordFilter{prefixSuffixMap}
}

func (wf *WordFilter) F(pref string, suff string) int {
    key := pref + "#" + suff
    if index, exists := wf.prefixSuffixMap[key]; exists {
        return index
    }
    return -1
}

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

#hard
Задача: 928. Minimize Malware Spread II

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

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

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

package main

import (
  "fmt"
  "math"
  "sort"
)

func minMalwareSpread(graph [][]int, initial []int) int {
  n := len(graph)

  dfs := func(node int, visited map[int]bool, component *[]int) {
    stack := []int{node}
    for len(stack) > 0 {
      u := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      *component = append(*component, u)
      for v := 0; v < n; v++ {
        if graph[u][v] == 1 && !visited[v] {
          visited[v] = true
          stack = append(stack, v)
        }
      }
    }
  }

  var components [][]int
  visited := make(map[int]bool)

  for i := 0; i < n; i++ {
    if !visited[i] {
      component := []int{}
      visited[i] = true
      dfs(i, visited, &component)
      components = append(components, component)
    }
  }

  infectedInComponent := make([]int, len(components))
  nodeToComponent := make(map[int]int)

  for idx, component := range components {
    for _, node := range component {
      nodeToComponent[node] = idx
    }
  }

  for _, node := range initial {
    componentIdx := nodeToComponent[node]
    infectedInComponent[componentIdx]++
  }

  minInfected := math.MaxInt32
  resultNode := initial[0]

  sort.Ints(initial)

  for _, node := range initial {
    componentIdx := nodeToComponent[node]
    if infectedInComponent[componentIdx] == 1 {
      componentSize := len(components[componentIdx])
      if componentSize < minInfected || (componentSize == minInfected && node < resultNode) {
        minInfected = componentSize
        resultNode = node
      }
    }
  }

  return resultNode
}

func main() {
  graph := [][]int{
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 1},
  }
  initial := []int{0, 1}
  fmt.Println(minMalwareSpread(graph, initial))
}

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