#hard
Задача: 591. Tag Validator

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

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

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

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

import java.util.regex.Pattern

class Solution {
    private val stack = mutableListOf<String>()
    private var containsTag = false

    private fun isValidTagName(s: String, ending: Boolean): Boolean {
        return if (ending) {
            if (stack.isNotEmpty() && stack.last() == s) stack.removeAt(stack.size - 1) else false
        } else {
            containsTag = true
            stack.add(s)
            true
        }
    }

    fun isValid(code: String): Boolean {
        val regex = "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
        if (!Pattern.matches(regex, code)) return false

        var i = 0
        while (i < code.length) {
            var ending = false
            if (stack.isEmpty() && containsTag) return false
            if (code[i] == '<') {
                if (code[i + 1] == '!') {
                    i = code.indexOf("]]>", i + 1)
                    if (i == -1) return false
                    continue
                }
                if (code[i + 1] == '/') {
                    i++
                    ending = true
                }
                val closeIndex = code.indexOf('>', i + 1)
                if (closeIndex == -1 || !isValidTagName(code.substring(i + 1, closeIndex), ending)) return false
                i = closeIndex
            }
            i++
        }
        return stack.isEmpty()
    }
}

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

#hard
Задача: 710. Random Pick with Blacklist

Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.

Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

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

1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка.

3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.

😎 Решение:

import kotlin.random.Random

class Solution(n: Int, blacklist: IntArray) {
    private val map = mutableMapOf<Int, Int>()
    private val bound = n - blacklist.size

    init {
        val blackset = blacklist.toSet()
        var whitelist = bound
        for (b in blacklist) {
            if (b < bound) {
                while (blackset.contains(whitelist)) {
                    whitelist++
                }
                map[b] = whitelist
                whitelist++
            }
        }
    }

    fun pick(): Int {
        val r = Random.nextInt(bound)
        return map.getOrDefault(r, r)
    }
}

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

#hard
Задача: 765. Couples Holding Hands

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

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

😎 Решение:

class Solution {
    private var N = 0
    private lateinit var pairs: Array<IntArray>
    
    fun minSwapsCouples(row: IntArray): Int {
        N = row.size / 2
        pairs = Array(N) { IntArray(2) }
        for (i in 0 until N) {
            pairs[i][0] = row[2 * i] / 2
            pairs[i][1] = row[2 * i + 1] / 2
        }
        return solve(0)
    }
    
    private fun swap(a: Int, b: Int, c: Int, d: Int) {
        val t = pairs[a][b]
        pairs[a][b] = pairs[c][d]
        pairs[c][d] = t
    }
    
    private fun solve(i: Int): Int {
        if (i == N) return 0
        val x = pairs[i][0]
        val y = pairs[i][1]
        if (x == y) return solve(i + 1)
        
        var jx = 0
        var kx = 0
        var jy = 0
        var ky = 0
        for (j in i + 1 until N) {
            for (k in 0..1) {
                if (pairs[j][k] == x) { jx = j; kx = k }
                if (pairs[j][k] == y) { jy = j; ky = k }
            }
        }
        
        swap(i, 1, jx, kx)
        val ans1 = 1 + solve(i + 1)
        swap(i, 1, jx, kx)
        
        swap(i, 0, jy, ky)
        val ans2 = 1 + solve(i + 1)
        swap(i, 0, jy, ky)
        
        return minOf(ans1, ans2)
    }
}

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

#hard
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

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⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

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

😎 Решение:

class Solution {
    fun numDistinctIslands2(grid: Array<IntArray>): Int {
        val uniqueIslands = mutableSetOf<String>()
        
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if (grid[i][j] == 1) {
                    val shape = mutableListOf<Pair<Int, Int>>()
                    dfs(grid, i, j, i, j, shape)
                    uniqueIslands.add(normalize(shape))
                }
            }
        }
        
        return uniqueIslands.size
    }
    
    private fun dfs(grid: Array<IntArray>, i: Int, j: Int, baseI: Int, baseJ: Int, shape: MutableList<Pair<Int, Int>>) {
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == 0) {
            return
        }
        grid[i][j] = 0
        shape.add(Pair(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)
    }
    
    private fun normalize(shape: List<Pair<Int, Int>>): String {
        val shapes = List(8) { mutableListOf<Pair<Int, Int>>() }
        for ((x, y) in shape) {
            shapes[0].add(Pair(x, y))
            shapes[1].add(Pair(x, -y))
            shapes[2].add(Pair(-x, y))
            shapes[3].add(Pair(-x, -y))
            shapes[4].add(Pair(y, x))
            shapes[5].add(Pair(y, -x))
            shapes[6].add(Pair(-y, x))
            shapes[7].add(Pair(-y, -x))
        }
        for (s in shapes) {
            s.sortWith(compareBy({ it.first }, { it.second }))
        }
        val minShape = shapes.minByOrNull { it.toString() }!!
        return minShape.joinToString(";") { "${it.first},${it.second}" }
    }
}

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

#hard
Задача: 774. Minimize Max Distance to Gas Station

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.

Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.

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

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    fun minmaxGasDist(stations: IntArray, K: Int): Double {
        val N = stations.size
        val deltas = DoubleArray(N-1)
        for (i in 0 until N-1) {
            deltas[i] = (stations[i+1] - stations[i]).toDouble()
        }

        val dp = Array(N-1) { DoubleArray(K+1) }
        for (i in 0..K) {
            dp[0][i] = deltas[0] / (i+1)
        }

        for (p in 1 until N-1) {
            for (k in 0..K) {
                var bns = Double.MAX_VALUE
                for (x in 0..k) {
                    bns = minOf(bns, maxOf(deltas[p] / (x+1), dp[p-1][k-x]))
                }
                dp[p][k] = bns
            }
        }

        return dp[N-2][K]
    }
}

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

#hard
Задача: 715. Range Module

Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).

Пример:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

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

1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.

2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.

3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.

😎 Решение:

class RangeModule {

    private val ranges = mutableListOf<Pair<Int, Int>>()

    fun addRange(left: Int, right: Int) {
        val newRanges = mutableListOf<Pair<Int, Int>>()
        var i = 0
        while (i < ranges.size && ranges[i].second < left) {
            newRanges.add(ranges[i])
            i++
        }
        var l = left
        var r = right
        while (i < ranges.size && ranges[i].first <= right) {
            l = minOf(l, ranges[i].first)
            r = maxOf(r, ranges[i].second)
            i++
        }
        newRanges.add(l to r)
        while (i < ranges.size) {
            newRanges.add(ranges[i])
            i++
        }
        ranges.clear()
        ranges.addAll(newRanges)
    }

    fun queryRange(left: Int, right: Int): Boolean {
        for (range in ranges) {
            if (range.first <= left && right <= range.second) {
                return true
            }
        }
        return false
    }

    fun removeRange(left: Int, right: Int) {
        val newRanges = mutableListOf<Pair<Int, Int>>()
        for (range in ranges) {
            if (range.first < left) {
                newRanges.add(range.first to minOf(range.second, left))
            }
            if (right < range.second) {
                newRanges.add(maxOf(range.first, right) to range.second)
            }
        }
        ranges.clear()
        ranges.addAll(newRanges)
    }
}

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

#hard
Задача: 716. Max Stack

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

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

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

class MaxStack {

    private val stack = mutableListOf<Int>()
    private val maxStack = mutableListOf<Int>()

    fun push(x: Int) {
        stack.add(x)
        if (maxStack.isEmpty() || x >= maxStack.last()) {
            maxStack.add(x)
        }
    }

    fun pop(): Int {
        val x = stack.removeAt(stack.size - 1)
        if (x == maxStack.last()) {
            maxStack.removeAt(maxStack.size - 1)
        }
        return x
    }

    fun top(): Int {
        return stack.last()
    }

    fun peekMax(): Int {
        return maxStack.last()
    }

    fun popMax(): Int {
        val maxVal = maxStack.removeAt(maxStack.size - 1)
        val buffer = mutableListOf<Int>()
        while (stack.last() != maxVal) {
            buffer.add(stack.removeAt(stack.size - 1))
        }
        stack.removeAt(stack.size - 1)
        while (buffer.isNotEmpty()) {
            push(buffer.removeAt(buffer.size - 1))
        }
        return maxVal
    }
}       }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

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

#hard
Задача: 719. Find K-th Smallest Pair Distance

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

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

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

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

2⃣Определите минимальное и максимальное возможные расстояния.

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

😎 Решение:

fun countPairs(nums: IntArray, mid: Int): Int {
    var count = 0
    var j = 0
    for (i in nums.indices) {
        while (j < nums.size && nums[j] - nums[i] <= mid) {
            j++
        }
        count += j - i - 1
    }
    return count
}

fun smallestDistancePair(nums: IntArray, k: Int): Int {
    nums.sort()
    var left = 0
    var right = nums.last() - nums.first()
    while (left < right) {
        val mid = (left + right) / 2
        if (countPairs(nums, mid) < k) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

#hard
Задача: 489. Robot Room Cleaner

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

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

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

1⃣Пометьте текущую ячейку как посещенную и очистите её.

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

3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎 Решение:

class Solution {
    private lateinit var robot: Robot
    private val visited = mutableSetOf<Pair<Int, Int>>()
    private val directions = listOf(Pair(-1, 0), Pair(0, 1), Pair(1, 0), Pair(0, -1))

    private fun goBack() {
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnRight()
        robot.turnRight()
    }

    private fun backtrack(row: Int, col: Int, d: Int) {
        visited.add(Pair(row, col))
        robot.clean()
        for (i in 0..3) {
            val newD = (d + i) % 4
            val newRow = row + directions[newD].first
            val newCol = col + directions[newD].second
            if (!visited.contains(Pair(newRow, newCol)) && robot.move()) {
                backtrack(newRow, newCol, newD)
                goBack()
            }
            robot.turnRight()
        }
    }

    fun cleanRoom(robot: Robot) {
        this.robot = robot
        backtrack(0, 0, 0)
    }
}

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

#hard
Задача: 499. The Maze III

В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него.

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

import java.util.PriorityQueue

data class State(val row: Int, val col: Int, val dist: Int, val path: String) : Comparable<State> {
    override fun compareTo(other: State): Int {
        return if (dist == other.dist) path.compareTo(other.path) else dist - other.dist
    }
}

class Solution {
    private val directions = arrayOf(intArrayOf(0, -1), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(1, 0))
    private val textDirections = arrayOf("l", "u", "r", "d")

    fun findShortestWay(maze: Array<IntArray>, ball: IntArray, hole: IntArray): String {
        val m = maze.size
        val n = maze[0].size
        val heap = PriorityQueue<State>()
        val seen = Array(m) { BooleanArray(n) }
        heap.add(State(ball[0], ball[1], 0, ""))
        
        while (heap.isNotEmpty()) {
            val curr = heap.poll()
            if (seen[curr.row][curr.col]) continue
            if (curr.row == hole[0] && curr.col == hole[1]) return curr.path
            seen[curr.row][curr.col] = true

            directions.forEachIndexed { i, (dy, dx) ->
                var (r, c, dist) = arrayOf(curr.row, curr.col, 0)
                while (r + dy in 0 until m && c + dx in 0 until n && maze[r + dy][c + dx] == 0) {
                    r += dy; c += dx; dist++
                    if (r == hole[0] && c == hole[1]) break
                }
                if (!seen[r][c]) heap.add(State(r, c, curr.dist + dist, curr.path + textDirections[i]))
            }
        }
        return "impossible"
    }
}

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