Kotlin | LeetCode

Задача: 1066. Campus Bikes II
Сложность: medium

На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.

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

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

Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

👨‍💻

Алгоритм:

1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего.

2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно.

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

😎

Решение:

class Solution {
    private var smallestDistanceSum = Int.MAX_VALUE
    private val visited = BooleanArray(10)
    
    private fun findDistance(worker: List<Int>, bike: List<Int>): Int {
        return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1])
    }
    
    private fun minimumDistanceSum(workers: List<List<Int>>, workerIndex: Int, 
                                   bikes: List<List<Int>>, currDistanceSum: Int) {
        if (workerIndex >= workers.size) {
            smallestDistanceSum = minOf(smallestDistanceSum, currDistanceSum)
            return
        }
        
        if (currDistanceSum >= smallestDistanceSum) {
            return
        }
        
        for (bikeIndex in bikes.indices) {
            if (!visited[bikeIndex]) {
                visited[bikeIndex] = true
                minimumDistanceSum(workers, workerIndex + 1, bikes, 
                    currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex]))
                visited[bikeIndex] = false
            }
        }
    }
    
    fun assignBikes(workers: List<List<Int>>, bikes: List<List<Int>>): Int {
        minimumDistanceSum(workers, 0, bikes, 0)
        return smallestDistanceSum
    }
}

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

Please open Telegram to view this post