Заправки

Источник: https://www.interviewbit.com/problems/gas-station/

Задача. Дано два массива A и B одинакового размера N. N - это число заправок расположенных на пути, который закольцовывается.

Массив A показывает, сколько топлива хранится на каждой заправке i.

У вас есть машина с беконечным баком. А в массиве B элемент i показывает, сколько топлива расходует ваша машина при переезде из точки i в i+1.

Нужно вернуть индекс i заправки, начиная с которой вы можете объехать все заправки. Либо вернуть -1, если такого индекса не существует (с какой заправки не стратуй, всё равно останешься где-то без топлива).

Пример.

Input 1:
    A =  [1, 2]
    B =  [2, 1]
Output 1:
    1
Объяснение:
        Если вы стартуете с индекса 0, вы можете залить в бак A[0] = 1 
единиц топлива. Но вам нужно B[0] = 2 единицы топлива, чтобы доехать 
до заправки с индексом 1. 
        Если вы стартуете с заправки под индексом 1, вы можете залить в бак 
A[1] = 2 единицы топлива. И вам нужно B[1] = 1 топлива, чтобы доехать до 
заправки с индексом 0. И вы до неё доезжаете, и у вас ещё остаётся 1 единица 
топлива. Вы доливаете A[0] = 1 ещё одну единицу топлива, и у вас в баке 
становится 2 единицы топлива. В данной точке вам нужно B[0] = 2 единиц топлива,
чтобы доехать до заправки с номером 1 и завершить круг. 

Идея решения: прежде всего, можно просуммировать все значения требуемого топлива (из массива B) и вычесть из суммы все значения наличного топлива (массив А), чтобы понять, решаема ли задача в принципе. Но так мы не найдём нужный индекс, если задача решаема.

Поэтому идём по всем индексам от 0 до N и попарно вычитаем требуемое топливо из наличного (бензобак + заправка).

Компилируемое решение

public class Solution {
    public int canCompleteCircuit(final List<Integer> gas, final List<Integer> cost) {
        // проверка на нольь
        if(gas == null || cost == null || gas.size() == 0 || cost.size() == 0 ||
           gas.size() != cost.size())
            return -1;
        int n = gas.size();
       
        int sumRemaining= 0;
        int total = 0;
        int start = 0;
       
        for(int i = 0; i < n; i++){
            // попарно вычитаем
            int remaining = gas.get(i) - cost.get(i);
            // если бак не ушёл в минус на предыдущем шаге
            if(sumRemaining >= 0)
            // то добавляем топливо запрвки и вычитаем стоимость переезда в следующую точку
                sumRemaining += remaining;
            else{
// если бензобак ушёл в минус на предыдущем шаге, то мы начали не с той точки
// поэтому начинаем с текущей точки i, и заливаем remaining
                sumRemaining = remaining;
                start = i;
            }
// а вот тут подсчитываем, решаема ли задача в принципе.
// То, что было написано в идее решения сразу же
            total += remaining;
        }
// если задача в принципе решаема, то сумма элеиментов A минус сумма элементов B
// должна быть больше нуля, а необходимый индекс start - тот,
// который ни разу не "дискредитировал" себя
        if(total >= 0)
            return start;
        else return -1;  
    }
}