Сложность: medium
Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.
Пример:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
👨💻 Алгоритм:
1⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.
2⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.
3⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.
😎 Решение:
func canCompleteCircuit(gas: [Int], cost: [Int]) -> Int {
var currGain = 0
var totalGain = 0
var answer = 0
for i in 0..<gas.count {
let gain = gas[i] - cost[i]
totalGain += gain
currGain += gain
if currGain < 0 {
answer = i + 1
currGain = 0
}
}
return totalGain >= 0 ? answer : -1
}Ставь 👍 и забирай 📚 Базу знаний