Задача: 422. Valid Word Square
Сложность: easy

Дан массив строк words, верните true, если он образует правильный квадрат слов.

Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).

Пример:
Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

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

1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом.

2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false.

3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false.

😎 Решение:

package main

func validWordSquare(words []string) bool {
    cols := 0
    rows := len(words)
    newWords := []string{}
    
    for _, word := range words {
        if len(word) > cols {
            cols = len(word)
        }
    }

    if cols != len(words[0]) || rows != cols {
        return false
    }

    for col := 0; col < cols; col++ {
        newWord := ""
        for row := 0; row < rows; row++ {
            if col < len(words[row]) {
                newWord += string(words[row][col])
            }
        }
        newWords = append(newWords, newWord)
    }

    for i := range words {
        if words[i] != newWords[i] {
            return false
        }
    }
    return true
}

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

Задача: 117. Populating Next Right Pointers in Each Node II
Сложность: medium

Вам дано бинарное дерево:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.
Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,null,7] 
Output: [1,#,2,3,#,4,5,7,#]

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

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

2⃣Внутри основного цикла while, фиксируем размер очереди — это количество узлов на текущем уровне.

3⃣Вложенным циклом проходим только по этим узлам: соединяем node.Next = Q.Front() для всех кроме последнего и добавляем детей в очередь для следующего уровня.

😎 Решение:

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    Q := list.New()
    Q.PushBack(root)
    for Q.Len() > 0 {
        size := Q.Len()
        for i := 0; i < size; i++ {
            front := Q.Front()
            node := front.Value.(*Node)
            Q.Remove(front)
            if i < size-1 {
                node.Next = Q.Front().Value.(*Node)
            }
            if node.Left != nil {
                Q.PushBack(node.Left)
            }
            if node.Right != nil {
                Q.PushBack(node.Right)
            }
        }
    }
    return root
}

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

Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: hard

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:

[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Для данного отсортированного и повернутого массива nums, который может содержать дубликаты, верните минимальный элемент этого массива.

Необходимо максимально уменьшить количество операций.

Пример:

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

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

1⃣Сравнение с правой границей:
В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2⃣Обновление указателей:
Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.
Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.
Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.

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

😎 Решение:

func findMin(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        pivot := low + (high-low)/2
        if nums[pivot] < nums[high] {
            high = pivot
        } else if nums[pivot] > nums[high] {
            low = pivot + 1
        } else {
            high -= 1
        }
    }
    return nums[low]
}

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:
Input: steps = 3, arrLen = 2
Output: 4

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

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

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

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

😎 Решение:

func numWays(steps int, arrLen int) int {
    mod := 1000000007
    maxPos := min(arrLen - 1, steps)
    dp := make([]int, maxPos + 1)
    dp[0] = 1
    for step := 0; step < steps; step++ {
        newDp := make([]int, maxPos + 1)
        for i := 0; i <= maxPos; i++ {
            newDp[i] = dp[i] % mod
            if i > 0 {
                newDp[i] = (newDp[i] + dp[i - 1]) % mod
            }
            if i < maxPos {
                newDp[i] = (newDp[i] + dp[i + 1]) % mod
            }
        }
        dp = newDp
    }
    return dp[0]
}

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

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

Задача: 784. Letter Case Permutation
Сложность: medium

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

package main

import (
    "strings"
    "unicode"
)

func letterCasePermutation(S string) []string {
    ans := [][]rune{{}}

    for _, c := range S {
        n := len(ans)
        if unicode.IsLetter(c) {
            for i := 0; i < n; i++ {
                ans = append(ans, append([]rune{}, ans[i]...))
                ans[i] = append(ans[i], unicode.ToLower(c))
                ans[n+i] = append(ans[n+i], unicode.ToUpper(c))
            }
        } else {
            for i := 0; i < n; i++ {
                ans[i] = append(ans[i], c)
            }
        }
    }

    result := make([]string, len(ans))
    for i, r := range ans {
        result[i] = string(r)
    }
    return result
}

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

Задача: 379. Design Phone Directory
Сложность: medium

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

Реализуйте класс PhoneDirectory:

PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers.
int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны.
bool check(int number) Возвращает true, если слот доступен, и false в противном случае.
void release(int number) Перераспределяет или освобождает номер слота.

Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

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

1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах.

2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1.
Метод check(number): Вернуть значение isSlotAvailable[number].

3⃣Метод release(number): Установить isSlotAvailable[number] = true.

😎 Решение:

package main

type PhoneDirectory struct {
    isSlotAvailable []bool
}

func Constructor(maxNumbers int) PhoneDirectory {
    isSlotAvailable := make([]bool, maxNumbers)
    for i := range isSlotAvailable {
        isSlotAvailable[i] = true
    }
    return PhoneDirectory{isSlotAvailable}
}

func (this *PhoneDirectory) Get() int {
    for i, available := range this.isSlotAvailable {
        if available {
            this.isSlotAvailable[i] = false
            return i
        }
    }
    return -1
}

func (this *PhoneDirectory) Check(number int) bool {
    return this.isSlotAvailable[number]
}

func (this *PhoneDirectory) Release(number int) {
    this.isSlotAvailable[number] = true
}

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

Задача: 243. Shortest Word Distance
Сложность: easy

Дан массив строк wordsDict и две разные строки, которые уже существуют в массиве: word1 и word2. Верните кратчайшее расстояние между этими двумя словами в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

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

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

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

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

😎 Решение:

type Solution struct{}

func (s *Solution) ShortestDistance(words []string, word1 string, word2 string) int {
    minDistance := len(words)
    for i, w1 := range words {
        if w1 == word1 {
            for j, w2 := range words {
                if w2 == word2 {
                    if diff := abs(i - j); diff < minDistance {
                        minDistance = diff
                    }
                }
            }
        }
    }
    return minDistance
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

Задача: 972. Equal Rational Numbers
Сложность: hard

Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

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

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

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

😎 Решение:

package main

import (
  "math"
  "strconv"
  "strings"
)

type Fraction struct {
  n, d int64
}

func (f *Fraction) iadd(other Fraction) {
  numerator := f.n*other.d + f.d*other.n
  denominator := f.d * other.d
  g := gcd(numerator, denominator)
  f.n = numerator / g
  f.d = denominator / g
}

func gcd(x, y int64) int64 {
  if x != 0 {
    return gcd(y%x, x)
  }
  return y
}

func isRationalEqual(S string, T string) bool {
  f1 := convert(S)
  f2 := convert(T)
  return f1.n == f2.n && f1.d == f2.d
}

func convert(S string) Fraction {
  state := 0
  ans := Fraction{0, 1}
  decimalSize := 0

  parts := strings.FieldsFunc(S, func(r rune) bool {
    return r == '.' || r == '(' || r == ')'
  })

  for _, part := range parts {
    state++
    if part == "" {
      continue
    }
    x, _ := strconv.ParseInt(part, 10, 64)
    sz := len(part)

    if state == 1 {
      ans.iadd(Fraction{x, 1})
    } else if state == 2 {
      ans.iadd(Fraction{x, int64(math.Pow(10, float64(sz)))})
      decimalSize = sz
    } else {
      denom := int64(math.Pow(10, float64(decimalSize)))
      denom *= int64(math.Pow(10, float64(sz)) - 1)
      ans.iadd(Fraction{x, denom})
    }
  }
  return ans
}

func main() {
  // Test the function here
}

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

Задача: 934. Shortest Bridge
Сложность: medium

Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.

Пример:

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

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

1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.

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

3⃣Вернуть длину кратчайшего пути.

😎 Решение:

package main

type Pair struct {
    x, y int
}

func shortestBridge(grid [][]int) int {
    n := len(grid)
    
    directions := [][]int{
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1},
    }
    
    queue := []Pair{}
    found := false
    
    var dfs func(x, y int)
    dfs = func(x, y int) {
        if x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1 {
            return
        }
        grid[x][y] = -1
        queue = append(queue, Pair{x, y})
        for _, dir := range directions {
            nx, ny := x+dir[0], y+dir[1]
            dfs(nx, ny)
        }
    }
    
    for i := 0; i < n && !found; i++ {
        for j := 0; j < n && !found; j++ {
            if grid[i][j] == 1 {
                dfs(i, j)
                found = true
            }
        }
    }
    
    steps := 0
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            p := queue[0]
            queue = queue[1:]
            for _, dir := range directions {
                nx, ny := p.x+dir[0], p.y+dir[1]
                if nx >= 0 && nx < n && ny >= 0 && ny < n {
                    if grid[nx][ny] == 1 {
                        return steps
                    }
                    if grid[nx][ny] == 0 {
                        grid[nx][ny] = -1
                        queue = append(queue, Pair{nx, ny})
                    }
                }
            }
        }
        steps++
    }
    
    return -1
}

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

Задача: 559. Maximum Depth of N-ary Tree
Сложность: easy

Дано n-арное дерево, найдите его максимальную глубину.

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.

Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).

Пример:

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

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

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

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

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

😎 Решение:

type Node struct {
    Val      int
    Children []*Node
}

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    } else if len(root.Children) == 0 {
        return 1
    } else {
        heights := []int{}
        for _, child := range root.Children {
            heights = append(heights, maxDepth(child))
        }
        max := 0
        for _, h := range heights {
            if h > max {
                max = h
            }
        }
        return max + 1
    }
}

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

Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

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

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

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

3⃣Проверка возможности отправки всех пакетов за заданное количество дней:
Напишите вспомогательную функцию, которая проверяет, можно ли отправить все пакеты при заданной грузоподъемности за определенное количество дней. Эта функция проходит по списку весов и считает количество необходимых дней для отправки всех пакетов при текущей грузоподъемности.

😎 Решение:

func shipWithinDays(weights []int, D int) int {
    canShipInDays := func(capacity int) bool {
        days := 1
        total := 0
        for _, weight := range weights {
            if total+weight > capacity {
                days++
                total = 0
            }
            total += weight
        }
        return days <= D
    }
    
    left, right := max(weights), sum(weights)
    
    for left < right {
        mid := (left + right) / 2
        if canShipInDays(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

func max(arr []int) int {
    maxVal := arr[0]
    for _, v := range arr {
        if v > maxVal {
            maxVal = v
        }
    }
    return maxVal
}

func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎 Решение

func solve(root *TreeNode, parent, gParent int) int {
    if root == nil {
        return 0
    }
    return solve(root.Left, root.Val, parent) + solve(root.Right, root.Val, parent) + func() int {
        if gParent%2 == 0 {
            return root.Val
        }
        return 0
    }()
}

func sumEvenGrandparent(root *TreeNode) int {
    return solve(root, -1, -1)
}

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

Задача: 685. Redundant Connection II
Сложность: hard

В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.

Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

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

Пример:

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

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

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

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

😎 Решение:

package main

type Solution struct{}

func (s *Solution) findRedundantDirectedConnection(edges [][]int) []int {
    N := len(edges)
    parent := make(map[int]int)
    var candidates [][]int
    for _, edge := range edges {
        if p, exists := parent[edge[1]]; exists {
            candidates = append(candidates, []int{p, edge[1]})
            candidates = append(candidates, edge)
        } else {
            parent[edge[1]] = edge[0]
        }
    }

    root := s.orbit(1, parent).node
    if len(candidates) == 0 {
        cycle := s.orbit(root, parent).seen
        ans := []int{0, 0}
        for _, edge := range edges {
            if cycle[edge[0]] && cycle[edge[1]] {
                ans = edge
            }
        }
        return ans
    }

    children := make(map[int][]int)
    for v, pv := range parent {
        children[pv] = append(children[pv], v)
    }

    seen := make([]bool, N+1)
    seen[0] = true
    stack := []int{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if !seen[node] {
            seen[node] = true
            for _, c := range children[node] {
                stack = append(stack, c)
            }
        }
    }
    for _, b := range seen {
        if !b {
            return candidates[0]
        }
    }
    return candidates[1]
}

type OrbitResult struct {
    node int
    seen map[int]bool
}

func (s *Solution) orbit(node int, parent map[int]int) *OrbitResult {
    seen := make(map[int]bool)
    for {
        if _, exists := parent[node]; !exists || seen[node] {
            break
        }
        seen[node] = true
        node = parent[node]
    }
    return &OrbitResult{node, seen}
}

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

Задача: 259. 3Sum Smaller
Сложность: medium

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

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

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

2⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

import "sort"

func threeSumSmaller(nums []int, target int) int {
    sort.Ints(nums)
    sum := 0
    for i := 0; i < len(nums)-2; i++ {
        sum += twoSumSmaller(nums, i+1, target-nums[i])
    }
    return sum
}

func twoSumSmaller(nums []int, startIndex int, target int) int {
    sum := 0
    for i := startIndex; i < len(nums)-1; i++ {
        j := binarySearch(nums, i, target-nums[i])
        sum += j - i
    }
    return sum
}

func binarySearch(nums []int, startIndex int, target int) int {
    left, right := startIndex, len(nums)-1
    for left < right {
        mid := (left + right + 1) / 2
        if nums[mid] < target {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

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

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

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

3⃣Верните выходной список.

😎 Решение:

package main

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

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    stack1, stack2 := []*TreeNode{}, []*TreeNode{}
    output := []int{}

    for root1 != nil || root2 != nil || len(stack1) > 0 || len(stack2) > 0 {
        for root1 != nil {
            stack1 = append(stack1, root1)
            root1 = root1.Left
        }
        for root2 != nil {
            stack2 = append(stack2, root2)
            root2 = root2.Left
        }
        if len(stack2) == 0 || (len(stack1) > 0 && stack1[len(stack1)-1].Val <= stack2[len(stack2)-1].Val) {
            root1 = stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
            output = append(output, root1.Val)
            root1 = root1.Right
        } else {
            root2 = stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
            output = append(output, root2.Val)
            root2 = root2.Right
        }
    }
    return output
}

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

Задача: 261. Graph Valid Tree
Сложность: medium

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.

Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

package main

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 {
        return false
    }
    
    adjList := make([][]int, n)
    for _, edge := range edges {
        adjList[edge[0]] = append(adjList[edge[0]], edge[1])
        adjList[edge[1]] = append(adjList[edge[1]], edge[0])
    }
    
    parent := make(map[int]int)
    parent[0] = -1
    queue := []int{0}
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, neighbor := range adjList[node] {
            if neighbor == parent[node] {
                continue
            }
            if _, found := parent[neighbor]; found {
                return false
            }
            parent[neighbor] = node
            queue = append(queue, neighbor)
        }
    }
    
    return len(parent) == n
}

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

Задача: 736. Parse Lisp Expression
Сложность: hard

Нам дан массив 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
}

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

Задача: 94. Binary Tree Inorder Traversal
Сложность: easy

Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке (inorder).

Пример:

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

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

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

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

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

😎 Решение:

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

func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    helper(root, &res)
    return res
}

func helper(root *TreeNode, res *[]int) {
    if root != nil {
        helper(root.Left, res)
        *res = append(*res, root.Val)
        helper(root.Right, res)
    }
}

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

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

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

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

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

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

import "sort"

func findLeastNumOfUniqueInts(arr []int, k int) int {
    freqMap := make(map[int]int)
    for _, num := range arr {
        freqMap[num]++
    }
    
    frequencies := make([]int, 0, len(freqMap))
    for _, freq := range freqMap {
        frequencies = append(frequencies, freq)
    }
    
    sort.Ints(frequencies)
    
    elementsRemoved := 0
    for i, freq := range frequencies {
        elementsRemoved += freq
        if elementsRemoved > k {
            return len(frequencies) - i
        }
    }
    
    return 0
}

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