_134_CanCompleteCircuit.java

/**
 * @author jzy
 * @GitHub <a href="https://github.com/567jin">567jin</a>
 * @since 2024-03-22 10:02:35
 */
public class _134_CanCompleteCircuit {
    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        int i = new _134_CanCompleteCircuit().canCompleteCircuit(gas, cost);
        System.out.println(i);
    }

    /**
     * 模拟 即直接找到每个站点 循环遍历 看起是否能够到达
     * 但是有一个可以优化的地方 当不可达站点时 则该站点的之前的站点也不可达(因为会经过此不可达的站点) 因此每次遍历的起点是不可达站点的下一个站点
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int total = 0;
            int sumCost = 0;
            int cnt = 0;  // 计数 看当前站点能往后走多少个站点
            while (cnt < n) {
                int j = (i + cnt) % n;  // 因为是环形的 当超过末尾时 应回到起始点
                total += gas[j];
                sumCost += cost[j];
                if (total < sumCost) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) { // 即能环绕一周 到达了5个站点
                return i;
            } else { // 不能环绕一周则从当前不能到达的站点的下一个站点开始
                i = i + cnt + 1;
            }
        }

        return -1;
    }
}