决定循环加油站道路的开始

Question

假设有一个圆。那个圆圈上有许多汽油泵。给你两组数据。

1. 汽油泵将提供的汽油量。
2. 从那个汽油泵到下一个加油站的距离。

计算第一个点，卡车将能够完成圆圈(卡车将停在每一个汽油泵，它有无限的容量)。期望时间复杂度为O(n)。假设1升汽油，卡车可以走1单位的距离。例如，假设有4个汽油泵，其汽油量和与下一个汽油泵值对的距离为{4，6}，{6，5}，{7，3}和{4，5}。第一个地方，卡车可以进行循环旅游是第二个汽油泵。产量应为“起动=1”(第二汽油泵的指数)。

寻找代码评审，最佳实践和优化。

public final class PetrolPumpCircularTour {
    
    private PetrolPumpCircularTour() {};

    public static int startingStations(List<PetrolPumpData> gasStations) {
        
        if (gasStations.size() == 0) {
            throw new IllegalArgumentException("There should be atleast a single gas stats");
        }
        
        int front = 0;
        int rear = 0; // is actually 0, after a circle. but 1 is just a game we play for circular queue.
        
        int statationsCovered = 0;
        int gasSavedSoFar = 0;
        
        while (statationsCovered < gasStations.size()) {
            int currentPetrol = gasStations.get(rear).getLitres() + gasSavedSoFar;
            int currentDistance = gasStations.get(rear).getDistance();
            gasSavedSoFar = currentPetrol - currentDistance;
            statationsCovered = statationsCovered + 1;
            
            if (gasSavedSoFar < 0) {
                rear = (rear + 1) % gasStations.size();
                front =  (front + 1) % gasStations.size();
                gasSavedSoFar = 0;
                statationsCovered = 0;
                if (rear == 0) {
                    return -1;
                }
            } else {
                rear = (rear + 1) % gasStations.size();
            }
        }
            
        return front;
    }
}


public class PetrolPumpCircularTourTest {
    
    @Test
    public void test1( ) {
        List<PetrolPumpData> list1 = new ArrayList<PetrolPumpData>();
        list1.add(new PetrolPumpData(4, 6));
        list1.add(new PetrolPumpData(6, 5));
        list1.add(new PetrolPumpData(7, 3));
        list1.add(new PetrolPumpData(4, 5));
        
        assertEquals(1, PetrolPumpCircularTour.startingStations(list1));
    }
    
    @Test
    public void test2() {
        List<PetrolPumpData> list2 = new ArrayList<PetrolPumpData>();
        list2.add(new PetrolPumpData(40, 6));
        list2.add(new PetrolPumpData(6, 5));
        list2.add(new PetrolPumpData(7, 3));
        list2.add(new PetrolPumpData(4, 5));
        
        assertEquals(0, PetrolPumpCircularTour.startingStations(list2));
    }
    
    @Test
    public void test3() {
        List<PetrolPumpData> list3 = new ArrayList<PetrolPumpData>();
        list3.add(new PetrolPumpData(4, 6));
        list3.add(new PetrolPumpData(3, 5));
        list3.add(new PetrolPumpData(70, 3));
        list3.add(new PetrolPumpData(4, 5));
        
        assertEquals(2, PetrolPumpCircularTour.startingStations(list3));
    }
    
    @Test
    public void test4( ) {
        List<PetrolPumpData> list4 = new ArrayList<PetrolPumpData>();
        list4.add(new PetrolPumpData(4, 6));
        list4.add(new PetrolPumpData(3, 5));
        list4.add(new PetrolPumpData(2, 3));
        list4.add(new PetrolPumpData(40, 5));
        
        assertEquals(3, PetrolPumpCircularTour.startingStations(list4));
    }
}

Answer 1

你能证明算法有效吗？看起来真的很可疑。另外，把它和一个

{4,6}, {6,5}, {1,3}, {7,3}, {4,5}

测试用例返回2。(提示:正确算法要简单得多)。

Answer 2

乍一看，这似乎是一个使用剩余/模算子的练习。

我们有一个循环列表的细节，我们需要评估的列表，从不同的点，沿着它。

我们可以使用剩余的%运算符计算一个循环列表，如下所示

for(int index = 0; index < allStations.length; index++){
    int currentStation = allStations[(index + startingPoint) % allStations.length];
// do something with the current station
}

注意:为了方便起见，我使用的是数组，而不是List。

解决方案应该是循环列表中的一个移动窗口。对于每个起点(0 => allStations.length)，检查这是否是有效的路由。如果是的话，返回起点。如果累积燃料平衡不是负的，路线是有效的。