#medium
Задача: 739. Daily Temperatures

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день.

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

3⃣Возвращайте массив ответов.

😎 Решение:

vpackage main

func dailyTemperatures(T []int) []int {
    n := len(T)
    answer := make([]int, n)
    stack := []int{}
    
    for i := 0; i < n; i++ {
        for len(stack) > 0 && T[i] > T[stack[len(stack)-1]] {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            answer[j] = i - j
        }
        stack = append(stack, i)
    }
    
    return answer
}

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

#medium
Задача: 740. Delete and Earn

Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.

Пример:

Input: nums = [3,4,2]
Output: 6

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

1⃣Подсчитайте количество каждого числа в массиве nums.

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

3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

package main

import "sort"

func deleteAndEarn(nums []int) int {
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    uniqueNums := make([]int, 0, len(count))
    for num := range count {
        uniqueNums = append(uniqueNums, num)
    }
    sort.Ints(uniqueNums)

    avoid, using, prev := 0, 0, -1
    for _, num := range uniqueNums {
        if num-1 != prev {
            newAvoid := max(avoid, using)
            using = num*count[num] + max(avoid, using)
            avoid = newAvoid
        } else {
            newAvoid := max(avoid, using)
            using = num*count[num] + avoid
            avoid = newAvoid
        }
        prev = num
    }

    return max(avoid, using)
}

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

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

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

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

#medium
Задача: 742. Closest Leaf in a Binary Tree

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

Пример:

Input: root = [1,3,2], k = 1
Output: 2

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

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

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

package main

import "container/list"

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

func findClosestLeaf(root *TreeNode, k int) int {
    path := []*TreeNode{}
    leaves := map[*TreeNode]int{}
    
    findPath(root, k, &path)
    findLeaves(root, leaves)
    
    queue := list.New()
    queue.PushBack([2]interface{}{path[len(path)-1], 0})
    visited := map[*TreeNode]bool{}
    
    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        node, dist := elem.Value.([2]interface{})[0].(*TreeNode), elem.Value.([2]interface{})[1].(int)
        if _, ok := leaves[node]; ok {
            return node.Val
        }
        visited[node] = true
        if node.Left != nil && !visited[node.Left] {
            queue.PushBack([2]interface{}{node.Left, dist + 1})
        }
        if node.Right != nil && !visited[node.Right] {
            queue.PushBack([2]interface{}{node.Right, dist + 1})
        }
        if len(path) > 1 {
            queue.PushBack([2]interface{}{path[len(path)-2], dist + 1})
            path = path[:len(path)-1]
        }
    }
    return -1
}

func findPath(node *TreeNode, k int, path *[]*TreeNode) bool {
    if node == nil {
        return false
    }
    *path = append(*path, node)
    if node.Val == k {
        return true
    }
    if findPath(node.Left, k, path) || findPath(node.Right, k, path) {
        return true
    }
    *path = (*path)[:len(*path)-1]
    return false
}

func findLeaves(node *TreeNode, leaves map[*TreeNode]int) {
    if node == nil {
        return
    }
    if node.Left == nil && node.Right == nil {
        leaves[node] = 0
    }
    findLeaves(node.Left, leaves)
    findLeaves(node.Right, leaves)
}

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

#medium
Задача: 743. Network Delay Time

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

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

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

😎 Решение:

package main

import (
  "container/heap"
  "math"
)

type Edge struct {
  to, weight int
}

type MinHeap [][]int

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

func networkDelayTime(times [][]int, n int, k int) int {
  graph := make(map[int][]Edge)
  for _, time := range times {
    graph[time[0]] = append(graph[time[0]], Edge{time[1], time[2]})
  }

  minHeap := &MinHeap{}
  heap.Init(minHeap)
  heap.Push(minHeap, []int{0, k})
  minTime := make(map[int]int)
  for i := 1; i <= n; i++ {
    minTime[i] = math.MaxInt32
  }
  minTime[k] = 0

  for minHeap.Len() > 0 {
    t := heap.Pop(minHeap).([]int)
    time, node := t[0], t[1]
    for _, edge := range graph[node] {
      newTime := time + edge.weight
      if newTime < minTime[edge.to] {
        minTime[edge.to] = newTime
        heap.Push(minHeap, []int{newTime, edge.to})
      }
    }
  }

  maxTime := 0
  for _, t := range minTime {
    if t == math.MaxInt32 {
      return -1
    }
    if t > maxTime {
      maxTime = t
    }
  }
  return maxTime
}

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

#easy
Задача: 744. Find Smallest Letter Greater Than Target

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

Пример:

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

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

1⃣Использовать бинарный поиск для нахождения позиции первого символа в letters, который лексикографически больше target.

2⃣Если найденный символ существует, вернуть его.

3⃣Если такого символа не существует, вернуть первый символ в letters.

😎 Решение:

package main

func nextGreatestLetter(letters []byte, target byte) byte {
    left, right := 0, len(letters)-1
    for left <= right {
        mid := (left + right) / 2
        if letters[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return letters[left % len(letters)]
}

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

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

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

#easy
Задача: 746. Min Cost Climbing Stairs

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

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

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

package main

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    copy(dp, cost)
    for i := 2; i < n; i++ {
        dp[i] += min(dp[i-1], dp[i-2])
    }
    return min(dp[n-1], dp[n-2])
}

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

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

#easy
Задача: 747. Largest Number At Least Twice of Others

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

Пример:

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

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

1⃣Найдите максимальный элемент в массиве и его индекс.

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

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

😎 Решение:

package main

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    copy(dp, cost)
    for i := 2; i < n; i++ {
        dp[i] += min(dp[i-1], dp[i-2])
    }
    return min(dp[n-1], dp[n-2])
}

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

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

#easy
Задача: 748. Shortest Completing Word

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

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

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

package main

func shortestCompletingWord(licensePlate string, words []string) string {
    licenseCount := getCharCount(licensePlate)
    
    var result string
    for _, word := range words {
        if isCompletingWord(word, licenseCount) {
            if result == "" || len(word) < len(result) {
                result = word
            }
        }
    }
    return result
}

func getCharCount(s string) map[rune]int {
    count := make(map[rune]int)
    for _, c := range s {
        if isLetter(c) {
            count[toLower(c)]++
        }
    }
    return count
}

func isCompletingWord(word string, licenseCount map[rune]int) bool {
    wordCount := make(map[rune]int)
    for _, c := range word {
        wordCount[c]++
    }
    for char, cnt := range licenseCount {
        if wordCount[char] < cnt {
            return false
        }
    }
    return true
}

func isLetter(c rune) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}

func toLower(c rune) rune {
    if c >= 'A' && c <= 'Z' {
        return c + 'a' - 'A'
    }
    return c
}

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

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

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

На easyoffer 2.0 появится:
🎯 Тренажер "Проработка вопросов"

✅ Метод интервальных повторений и флеш-карточки
✅ Персональный подход изучения на основе ваших ответов
✅ Упор на самые частые вопросы

📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос).

🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом.

Уже в течение недели я объявлю о старте краудфандинговой кампании на сбор финансирования, чтобы ускорить разработку сайта. Все кто поддержит проект до официального релиза получат самые выгодные условия пользования сервисом. А именно 1 год доступа к сайту по цене месячной подписки.

‼️ Очень важно, чтобы как можно больше людей поддержали проект в первые дни, по-этому те кто окажет поддержку первыми получат еще более выгодную стоимость на годовую подписку и существенный 💎 бонус о котором я позже расскажу в этом телеграм канале. Подписывайтесь, чтобы узнать о старте проекта раньше других и воспользоваться лимитированными вознаграждениями.

#medium
Задача: 930. Binary Subarrays With Sum

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

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

package main

import "fmt"

func numSubarraysWithSum(nums []int, goal int) int {
    prefixSumCount := make(map[int]int)
    prefixSumCount[0] = 1

    currentSum, count := 0, 0

    for _, num := range nums {
        currentSum += num

        if val, exists := prefixSumCount[currentSum-goal]; exists {
            count += val
        }

        prefixSumCount[currentSum]++
    }

    return count
}

func main() {
    nums := []int{1, 0, 1, 0, 1}
    goal := 2
    fmt.Println(numSubarraysWithSum(nums, goal))
}

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

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

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

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

😎 Решение:

package main

func countCornerRectangles(grid [][]int) int {
    count := 0
    for i := 0; i < len(grid); i++ {
        for j := i + 1; j < len(grid); j++ {
            numPairs := 0
            for k := 0; k < len(grid[0]); k++ {
                if grid[i][k] == 1 && grid[j][k] == 1 {
                    numPairs++
                }
            }
            if numPairs > 1 {
                count += numPairs * (numPairs - 1) / 2
            }
        }
    }
    return count
}

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

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func ipToInt(ip string) int {
    parts := strings.Split(ip, ".")
    p1, _ := strconv.Atoi(parts[0])
    p2, _ := strconv.Atoi(parts[1])
    p3, _ := strconv.Atoi(parts[2])
    p4, _ := strconv.Atoi(parts[3])
    return (p1 << 24) + (p2 << 16) + (p3 << 8) + p4
}

func intToIp(num int) string {
    return fmt.Sprintf("%d.%d.%d.%d", (num>>24)&255, (num>>16)&255, (num>>8)&255, num&255)
}

func cidr(ip string, prefixLength int) string {
    return fmt.Sprintf("%s/%d", ip, prefixLength)
}

func findCidrBlocks(startIp string, n int) []string {
    start := ipToInt(startIp)
    var result []string
    
    for n > 0 {
        maxSize := 1
        for maxSize <= start && maxSize <= n {
            maxSize <<= 1
        }
        maxSize >>= 1
        
        for start%maxSize != 0 {
            maxSize >>= 1
        }
        
        result = append(result, cidr(intToIp(start), 32-log2(maxSize)+1))
        start += maxSize
        n -= maxSize
    }
    
    return result
}

func log2(n int) int {
    count := 0
    for n > 1 {
        n >>= 1
        count++
    }
    return count
}

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

#medium
Задача: 752. Open the Lock

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

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

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

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

package main

import (
    "fmt"
)

func openLock(deadends []string, target string) int {
    neighbors := func(node string) []string {
        res := []string{}
        for i := 0; i < 4; i++ {
            x := node[i] - '0'
            for _, d := range []int{-1, 1} {
                y := (x + byte(d) + 10) % 10
                res = append(res, node[:i]+string(y+'0')+node[i+1:])
            }
        }
        return res
    }

    dead := make(map[string]bool)
    for _, d := range deadends {
        dead[d] = true
    }

    queue := []string{"0000"}
    steps := 0
    visited := make(map[string]bool)
    visited["0000"] = true

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node == target {
                return steps
            }
            if dead[node] {
                continue
            }
            for _, neighbor := range neighbors(node) {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }
        steps++
    }

    return -1
}

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

#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

func crackSafe(n int, k int) string {
    seen := make(map[string]bool)
    var result []byte

    startNode := strings.Repeat("0", n-1)
    dfs(startNode, k, seen, &result)

    result = append(result, startNode...)
    return string(result)
}

func dfs(node string, k int, seen map[string]bool, result *[]byte) {
    for x := 0; x < k; x++ {
        neighbor := node + fmt.Sprint(x)
        if !seen[neighbor] {
            seen[neighbor] = true
            dfs(neighbor[1:], k, seen, result)
            *result = append(*result, byte(x+'0'))
        }
    }
}

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

package main

import (
    "fmt"
    "math"
)

func reachTarget(target int) int {
    target = int(math.Abs(float64(target)))
    position := 0
    steps := 0
    for position < target || (position - target) % 2 != 0 {
        steps++
        position += steps
    }
    return steps
}

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

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

func runningSum(nums []int) []int {
    result := make([]int, len(nums))
    result[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        result[i] = result[i-1] + nums[i]
    }
    return result
}

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

Задача: 961. N-Repeated Element in Size 2N Array
Сложность: easy

Вам дан целочисленный массив nums со следующими свойствами:

nums.length == 2 * n.
nums содержит n + 1 уникальных элементов.
Ровно один элемент массива nums повторяется n раз.
Верните элемент, который повторяется n раз.

Пример:

Input: nums = [1,2,3,3]
Output: 3

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

1⃣Проверить все подмассивы длиной 4. В таком подмассиве обязательно будет главный элемент, повторяющийся n раз.

2⃣Сравнить элементы массива с их соседями на расстоянии 1, 2 и 3. Если найдется повторяющийся элемент, он и будет искомым.

3⃣Вернуть найденный элемент.

😎 Решение:

func repeatedNTimes(A []int) int {
    for k := 1; k <= 3; k++ {
        for i := 0; i < len(A) - k; i++ {
            if A[i] == A[i + k] {
                return A[i]
            }
        }
    }
    return -1
}

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