Задача: 669. Trim a Binary Search Tree
Сложность: medium

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

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

func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val > high {
        return trimBST(root.Left, low, high)
    }
    if root.Val < low {
        return trimBST(root.Right, low, high)
    }
    root.Left = trimBST(root.Left, low, high)
    root.Right = trimBST(root.Right, low, high)
    return root
}

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

Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве.
Если в дереве более одной моды, верните их в любом порядке.

Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.

Пример:

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

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

3⃣Возврат результата
Верните список ans.

😎 Решение:

func findMode(root *TreeNode) []int {
    var values []int
    dfs(root, &values)
    
    maxStreak, currStreak, currNum := 0, 0, 0
    var ans []int
    
    for _, num := range values {
        if num == currNum {
            currStreak++
        } else {
            currStreak = 1
            currNum = num
        }
        
        if currStreak > maxStreak {
            ans = []int{num}
            maxStreak = currStreak
        } else if currStreak == maxStreak {
            ans = append(ans, num)
        }
    }
    
    return ans
}

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

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

Задача: 275. H-Index II
Сложность: medium

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n - 1
    
    for left <= right {
        mid := left + (right - left) / 2
        if citations[mid] == n - mid {
            return n - mid
        } else if citations[mid] < n - mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return n - left
}

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

Задача: 953. Verifying an Alien Dictionary
Сложность: hard

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

Пример:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

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

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

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

3⃣Если все слова отсортированы правильно, вернуть true.

😎 Решение:

package main

func isAlienSorted(words []string, order string) bool {
    orderMap := make(map[rune]int)
    for i, char := range order {
        orderMap[char] = i
    }
    
    compare := func(word1, word2 string) bool {
        minLength := min(len(word1), len(word2))
        for i := 0; i < minLength; i++ {
            if orderMap[rune(word1[i])] < orderMap[rune(word2[i])] {
                return true
            } else if orderMap[rune(word1[i])] > orderMap[rune(word2[i])] {
                return false
            }
        }
        return len(word1) <= len(word2)
    }
    
    for i := 0; i < len(words) - 1; i++ {
        if !compare(words[i], words[i + 1]) {
            return false
        }
    }
    return true
}

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

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

Задача: 640. Solve the Equation
Сложность: medium

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения
Разделите уравнение на левую и правую части относительно знака равенства '='.

2⃣Парсинг и упрощение
Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений.

3⃣Решение уравнения
Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

package main

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

func solveEquation(equation string) string {
  parse := func(s string) (int, int) {
    coeff, constPart, sign, num := 0, 0, 1, 0
    i := 0
    for i < len(s) {
      if s[i] == '+' {
        sign = 1
        i++
      } else if s[i] == '-' {
        sign = -1
        i++
      } else if s[i] >= '0' && s[i] <= '9' {
        num = 0
        for i < len(s) && s[i] >= '0' && s[i] <= '9' {
          num = num*10 + int(s[i]-'0')
          i++
        }
        if i < len(s) && s[i] == 'x' {
          coeff += sign * num
          i++
        } else {
          constPart += sign * num
        }
      } else if s[i] == 'x' {
        coeff += sign
        i++
      }
    }
    return coeff, constPart
  }

  left, right := equation[:strings.Index(equation, "=")], equation[strings.Index(equation, "=")+1:]
  leftCoeff, leftConst := parse(left)
  rightCoeff, rightConst := parse(right)

  coeff := leftCoeff - rightCoeff
  constPart := rightConst - leftConst

  if coeff == 0 {
    if constPart == 0 {
      return "Infinite solutions"
    }
    return "No solution"
  }
  return "x=" + strconv.Itoa(constPart/coeff)
}

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

Задача: 223. Rectangle Area
Сложность: medium

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

Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2).

Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2).

Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

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

1⃣Вычислить площади двух прямоугольников:
Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту.

2⃣Вычислить перекрытие:
Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия.

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

😎 Решение:

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
    areaOfA := (ay2 - ay1) * (ax2 - ax1)
    areaOfB := (by2 - by1) * (bx2 - bx1)

    left := max(ax1, bx1)
    right := min(ax2, bx2)
    xOverlap := right - left

    top := min(ay2, by2)
    bottom := max(ay1, by1)
    yOverlap := top - bottom

    areaOfOverlap := 0
    if xOverlap > 0 && yOverlap > 0 {
        areaOfOverlap = xOverlap * yOverlap
    }

    totalArea := areaOfA + areaOfB - areaOfOverlap
    return totalArea
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

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

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

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

😎 Решение

func diagonalSort(mat [][]int) [][]int {
    m := len(mat)
    n := len(mat[0])
    diagonals := make(map[int]*PriorityQueue)

    for row := 0; row < m; row++ {
        for col := 0; col < n; col++ {
            key := row - col
            if diagonals[key] == nil {
                diagonals[key] = NewPriorityQueue()
            }
            diagonals[key].Push(mat[row][col])
        }
    }

    for row := 0; row < m; row++ {
        for col := 0; col < n; col++ {
            key := row - col
            mat[row][col] = diagonals[key].Pop().(int)
        }
    }

    return mat
}

type PriorityQueue struct {
    items []int
}

func NewPriorityQueue() *PriorityQueue {
    return &PriorityQueue{items: []int{}}
}

func (pq *PriorityQueue) Push(x int) {
    pq.items = append(pq.items, x)
    pq.up(len(pq.items) - 1)
}

func (pq *PriorityQueue) Pop() interface{} {
    n := len(pq.items) - 1
    pq.swap(0, n)
    pq.down(0, n)

    item := pq.items[n]
    pq.items = pq.items[:n]
    return item
}

func (pq *PriorityQueue) up(j int) {
    for {
        i := (j - 1) / 2
        if i == j || pq.items[i] <= pq.items[j] {
            break
        }
        pq.swap(i, j)
        j = i
    }
}

func (pq *PriorityQueue) down(i, n int) {
    for {
        j := 2*i + 1
        if j >= n || j < 0 {
            break
        }
        if k := j + 1; k < n && pq.items[k] < pq.items[j] {
            j = k
        }
        if pq.items[i] <= pq.items[j] {
            break
        }
        pq.swap(i, j)
        i = j
    }
}

func (pq *PriorityQueue) swap(i, j int) {
    pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
}

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

Задача: 1021. Remove Outermost Parentheses
Сложность: easy

Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.

Пример:

Input: s = "(()())(())"
Output: "()()()"

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

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

2⃣Обработка строки:
Итерируйте по каждому символу строки.
Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат.
Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат.

3⃣Возврат результата:
Верните результат, содержащий строку без крайних скобок из каждой примитивной строки.

😎 Решение:

func removeOuterParentheses(s string) string {
    var result []rune
    level := 0
    
    for _, char := range s {
        if char == '(' {
            if level > 0 {
                result = append(result, char)
            }
            level++
        } else {
            level--
            if level > 0 {
                result = append(result, char)
            }
        }
    }
    
    return string(result)
}

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

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

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