Задача: 917. Reverse Only Letters
Сложность: easy

Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания.

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

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

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

package main

func reverseOnlyLetters(s string) string {
    letters := []rune{}
    for _, c := range s {
        if isLetter(c) {
            letters = append(letters, c)
        }
    }
    reverseRunes(letters)
    result := []rune{}
    idx := 0
    for _, c := range s {
        if isLetter(c) {
            result = append(result, letters[idx])
            idx++
        } else {
            result = append(result, c)
        }
    }
    return string(result)
}

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

func reverseRunes(runes []rune) {
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
}

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

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

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣Инициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

func validSubarrays(nums []int) int {
    ans := 0
    var st []int
    
    for i := 0; i < len(nums); i++ {
        for len(st) > 0 && nums[i] < nums[st[len(st)-1]] {
            ans += i - st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    
    for len(st) > 0 {
        ans += len(nums) - st[len(st)-1]
        st = st[:len(st)-1]
    }
    
    return ans
}

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

Задача: 1030. Matrix Cells in Distance Order
Сложность: easy

Вам даны четыре целых числа row, cols, rCenter и cCenter. Имеется матрица rows x cols, и вы находитесь на ячейке с координатами (rCenter, cCenter). Верните координаты всех ячеек в матрице, отсортированные по их расстоянию от (rCenter, cCenter) от наименьшего расстояния до наибольшего. Вы можете вернуть ответ в любом порядке, удовлетворяющем этому условию. Расстояние между двумя ячейками (r1, c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.

Пример:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]

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

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

2⃣Сортировка списка:
Отсортируйте список по расстоянию в порядке возрастания.

3⃣Извлечение координат:
Извлеките координаты из отсортированного списка и верните их.

😎 Решение:

import (
    "sort"
    "math"
)

func allCellsDistOrder(rows int, cols int, rCenter int, cCenter int) [][]int {
    cells := make([][3]int, 0, rows*cols)
    
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            distance := int(math.Abs(float64(r - rCenter)) + math.Abs(float64(c - cCenter)))
            cells = append(cells, [3]int{distance, r, c})
        }
    }
    
    sort.Slice(cells, func(i, j int) bool {
        return cells[i][0] < cells[j][0]
    })
    
    result := make([][]int, len(cells))
    for i, cell := range cells {
        result[i] = []int{cell[1], cell[2]}
    }
    
    return result
}

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

package main

func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    left := searchColumns(image, 0, y, 0, m, true)
    right := searchColumns(image, y+1, n, 0, m, false)
    top := searchRows(image, 0, x, left, right, true)
    bottom := searchRows(image, x+1, m, left, right, false)
    return (right - left) * (bottom - top)
}

func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        t := top
        for t < bottom && image[t][k] == '0' {
            t++
        }
        if (t < bottom) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        l := left
        for l < right && image[k][l] == '0' {
            l++
        }
        if (l < right) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

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

😎 Решение:

package main

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    var i int
    for i = n - 2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            break
        }
    }
    if i == -1 {
        return arr
    }

    var j int
    for j = n - 1; j > i; j-- {
        if arr[j] < arr[i] && (j == n-1 || arr[j] != arr[j+1]) {
            break
        }
    }

    arr[i], arr[j] = arr[j], arr[i]
    
    return arr
}

func main() {
    arr := []int{3, 2, 1}
    result := prevPermOpt1(arr)
    fmt.Println(result)
}

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

Задача: 738. Monotone Increasing Digits
Сложность: medium

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10
Output: 9

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

1⃣Преобразуйте число в строку для удобства обработки.

2⃣Найдите позицию, где последовательность перестает быть монотонной.

3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎 Решение:

package main

import "strconv"

func monotoneIncreasingDigits(N int) int {
    digits := []byte(strconv.Itoa(N))
    marker := len(digits)
    
    for i := len(digits) - 1; i > 0; i-- {
        if digits[i] < digits[i-1] {
            marker = i
            digits[i-1]--
        }
    }
    
    for i := marker; i < len(digits); i++ {
        digits[i] = '9'
    }
    
    result, _ := strconv.Atoi(string(digits))
    return result
}

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

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy

Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника.

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

Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

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

1⃣Инициализация переменных:
Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0.

2⃣Итерация по зарплатам:
Для каждой зарплаты добавить её к переменной sum.
Обновить переменную minSalary, если текущая зарплата меньше её значения.
Обновить переменную maxSalary, если текущая зарплата больше её значения.

3⃣Вычисление среднего значения:
Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности.

😎 Решение:

func average(salary []int) float64 {
    minSalary := int(^uint(0) >> 1)
    maxSalary := -minSalary - 1
    sum := 0

    for _, sal := range salary {
        sum += sal
        if sal < minSalary {
            minSalary = sal
        }
        if sal > maxSalary {
            maxSalary = sal
        }
    }

    return float64(sum - minSalary - maxSalary) / float64(len(salary) - 2)
}

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

Задача: 136. Single Number
Сложность: easy

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

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Переберите все элементы в массиве nums.

2⃣Если какое-то число в nums новое для массива, добавьте его.

3⃣Если какое-то число уже есть в массиве, удалите его.

😎 Решение:

func singleNumber(nums []int) int {
    no_duplicate_list := []int{}
    for _, i := range nums {
        found := false
        for j, x := range no_duplicate_list {
            if i == x {
                found = true
                no_duplicate_list = append(
                    no_duplicate_list[:j],
                    no_duplicate_list[j+1:]...)
                break
            }
        }
        if !found {
            no_duplicate_list = append(no_duplicate_list, i)
        }
    }
    return no_duplicate_list[0]
}

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

Задача: 711. Number of Distinct Islands II
Сложность: hard

Вам дана бинарная матрица grid. Нужно вернуть количество уникальных островов (групп 1), учитывая вращения и отражения как одинаковую форму.

Пример:

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

Пояснение: острова в левом верхнем и правом нижнем углу — одинаковые по форме (с учётом поворота).

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

1⃣DFS для поиска формы острова
Для каждой клетки 1 вызываем DFS, сохраняем относительные координаты точек острова в массив shape. Помечаем посещённые ячейки как 0.

2⃣Нормализация формы
Для каждой формы создаём 8 возможных трансформаций:
- 4 поворота: (x,y), (-x,y), (x,-y), (-x,-y)
- 4 отражения по диагоналям: (y,x), (-y,x), (y,-x), (-y,-x)
Сортируем координаты каждой трансформации, затем приводим к строке и выбираем лексикографически минимальную — она будет "канонической" формой острова.

3⃣Подсчёт уникальных форм
Храним все канонические формы в map[string]struct{}. Размер map — это количество уникальных островов.

😎 Решение:

package main

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

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

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

  return len(uniqueIslands)
}

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

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

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

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

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

  return minShape
}

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

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

Задача: 81. Search in Rotated Sorted Array II
Сложность: medium

В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].

Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.

Необходимо сократить количество операций поиска настолько, насколько это возможно.

Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

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

1⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска.

2⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске:
Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end].
Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid).
Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска.
Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска.

3⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно.

😎 Решение:

func search(nums []int, target int) bool {
    n := len(nums)
    if n == 0 {
        return false
    }
    end := n - 1
    start := 0
    for start <= end {
        mid := start + (end-start)/2
        if nums[mid] == target {
            return true
        }
        if !isBinarySearchHelpful(nums, start, nums[mid]) {
            start++
            continue
        }
        pivotArray := existsInFirst(nums, start, nums[mid])
        targetArray := existsInFirst(nums, start, target)
        if pivotArray != targetArray {
            if pivotArray {
                start = mid + 1
            } else {
                end = mid - 1
            }
        } else {
            if nums[mid] < target {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }
    return false
}

func isBinarySearchHelpful(nums []int, start int, element int) bool {
    return nums[start] != element
}

func existsInFirst(nums []int, start int, element int) bool {
    return nums[start] <= element
}

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

Задача: №38. Count and Say
Сложность: medium

Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы:

countAndSay(1) = "1"
countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).
Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511".

Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи".

Пример:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

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

1⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222".
Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает.

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

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

😎 Решение:

func countAndSay(n int) string {
    s := "1"
    for i := 2; i <= n; i++ {
        t := ""
        count := 1
        for j := 1; j < len(s); j++ {
            if s[j] == s[j-1] {
                count++
            } else {
                t += strconv.Itoa(count) + string(s[j-1])
                count = 1
            }
        }
        t += strconv.Itoa(count) + string(s[len(s)-1])
        s = t
    }
    return s
}

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

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

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

😎 Решение

func findRoot(tree []*Node) *Node {
    seen := make(map[int]struct{})

    for _, node := range tree {
        for _, child := range node.Children {
            seen[child.Val] = struct{}{}
        }
    }

    for _, node := range tree {
        if _, found := seen[node.Val]; !found {
            return node
        }
    }

    return nil
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

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

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

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

😎 Решение:

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

func longestZigZag(root *TreeNode) int {
    maxLength := 0

    var dfs func(node *TreeNode, isLeft bool, length int)
    dfs = func(node *TreeNode, isLeft bool, length int) {
        if node == nil {
            return
        }
        if length > maxLength {
            maxLength = length
        }
        if isLeft {
            dfs(node.Left, false, length+1)
            dfs(node.Right, true, 1)
        } else {
            dfs(node.Right, true, length+1)
            dfs(node.Left, false, 1)
        }
    }

    dfs(root, true, 0)
    dfs(root, false, 0)

    return maxLength
}

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

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

Дан корень бинарного дерева, верните предварительный обход значений его узлов.

Пример:

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

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

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

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

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

😎 Решение:

func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    stack := []*TreeNode{root}

    output := []int{}

    for len(stack) > 0 {
        length := len(stack)
        root = stack[length-1]
        stack = stack[:length-1]

        if root != nil {
            output = append(output, root.Val)
        }

        if root.Right != nil {
            stack = append(stack, root.Right)
        }

        if root.Left != nil {
            stack = append(stack, root.Left)
        }
    }

    return output
}

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

Задача: 688. Knight Probability in Chessboard
Сложность: medium

На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).

Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.

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

Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.

Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы.

Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

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

1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.

2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j].

3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.

😎 Решение:

package main

func knightProbability(n int, k int, row int, column int) float64 {
    directions := [8][2]int{{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}
    dp := make([][][]float64, k+1)
    for i := range dp {
        dp[i] = make([][]float64, n)
        for j := range dp[i] {
            dp[i][j] = make([]float64, n)
        }
    }
    dp[0][row][column] = 1

    for moves := 1; moves <= k; moves++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                for _, direction := range directions {
                    prevI, prevJ := i-direction[0], j-direction[1]
                    if prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n {
                        dp[moves][i][j] += dp[moves-1][prevI][prevJ] / 8
                    }
                }
            }
        }
    }

    totalProbability := 0.0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            totalProbability += dp[k][i][j]
        }
    }

    return totalProbability
}

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

Задача: №93. Restore IP Addresses
Сложность: medium

Дана строка s, представляющая только цифры. Необходимо вернуть все возможные допустимые комбинации разделения строки на IP-адреса.

Пример:

Input: s = "25525511135"  
Output: ["255.255.11.135", "255.255.111.35"]  

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

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

2⃣Проверяем, что каждая часть является допустимой (1-3 цифры, не начинается с 0, не превышает 255).

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

😎 Решение:

func restoreIpAddresses(s string) []string {
    var ans []string
    var valid func(s string, start int, length int) bool
    valid = func(s string, start int, length int) bool {
        return length == 1 ||
            (s[start] != '0' && (length < 3 || s[start:start+length] <= "255"))
    }
    var helper func(s string, startIndex int, dots []int)
    helper = func(s string, startIndex int, dots []int) {
        remainingLength := len(s) - startIndex
        remainingNumberOfIntegers := 4 - len(dots)
        if remainingLength > remainingNumberOfIntegers*3 ||
            remainingLength < remainingNumberOfIntegers {
            return
        }
        if len(dots) == 3 {
            if valid(s, startIndex, remainingLength) {
                temp := ""
                last := 0
                for i := 0; i < len(dots); i++ {
                    temp += s[last : last+dots[i]]
                    if last != startIndex {
                        temp += "."
                    }
                    last += dots[i]
                }
                temp += s[startIndex:]
                ans = append(ans, temp)
            }
            return
        }
        for curPos := 1; curPos <= 3 && curPos <= remainingLength; curPos++ {
            dots = append(dots, curPos)
            if valid(s, startIndex, curPos) {
                helper(s, startIndex+curPos, dots)
            }
            dots = dots[:len(dots)-1]
        }
    }
    helper(s, 0, []int{})
    return ans
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

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

😎 Решение:

package main

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

func exclusiveTime(n int, logs []string) []int {
  stack := []int{}
  times := make([]int, n)
  prevTime := 0

  for _, log := range logs {
    parts := strings.Split(log, ":")
    fid, _ := strconv.Atoi(parts[0])
    typ := parts[1]
    time, _ := strconv.Atoi(parts[2])

    if typ == "start" {
      if len(stack) > 0 {
        times[stack[len(stack)-1]] += time - prevTime
      }
      stack = append(stack, fid)
      prevTime = time
    } else {
      times[stack[len(stack)-1]] += time - prevTime + 1
      stack = stack[:len(stack)-1]
      prevTime = time + 1
    }
  }

  return times
}

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

import (
    "container/heap"
)

func isPossible(target []int) bool {
    pq := &MaxHeap{}
    heap.Init(pq)
    total := 0
    for _, num := range target {
        heap.Push(pq, num)
        total += num
    }
    
    for (*pq)[0] > 1 {
        maxVal := heap.Pop(pq).(int)
        total -= maxVal
        if maxVal < total || total == 0 || maxVal % total == 0 {
            return false
        }
        heap.Push(pq, maxVal % total)
        total += (*pq)[0]
    }
    return true
}

type MaxHeap []int

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

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

func checkInclusion(s1 string, s2 string) bool {
    s1Len, s2Len := len(s1), len(s2)
    if s1Len > s2Len {
        return false
    }

    s1Count, s2Count := make([]int, 26), make([]int, 26)
    for i := 0; i < s1Len; i++ {
        s1Count[s1[i]-'a']++
        s2Count[s2[i]-'a']++
    }

    for i := 0; i < s2Len-s1Len; i++ {
        if equal(s1Count, s2Count) {
            return true
        }
        s2Count[s2[i]-'a']--
        s2Count[s2[i+s1Len]-'a']++
    }

    return equal(s1Count, s2Count)
}

func equal(a, b []int) bool {
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

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

Задача: 906. Super Palindromes
Сложность: hard

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

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

😎 Решение:

public class Solution {
    private bool IsPalindrome(long x) {
        string s = x.ToString();
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        return s == new string(arr);
    }

    public int SuperpalindromesInRange(string left, string right) {
        long leftNum = long.Parse(left);
        long rightNum = long.Parse(right);
        int count = 0;

        for (int i = 1; i < 100000; i++) {
            string s = i.ToString();
            long palin1 = long.Parse(s + new string(s.Reverse().ToArray()));
            long palin2 = long.Parse(s + new string(s.Reverse().Skip(1).ToArray()));

            if (palin1 * palin1 > rightNum) {
                break;
            }
            if (palin1 * palin1 >= leftNum && IsPalindrome(palin1 * palin1)) {
                count++;
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && IsPalindrome(palin2 * palin2)) {
                count++;
            }
        }

        return count;
    }
}

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