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

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