#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))
}

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