java greedy solution


  • 0
    P

    //首先计算gas和cost数组的差,得到一个有正有负的数列,然后求连续的和最大的子数列(同时也要保存最大子数列的起始位置 = start),可以转化为53. Maximum Subarray的问题。
    //然后以最大子数列的起点(start)为车开始的起点,看看这样车能不能走一圈。
    //原因:贪婪算法,因为油箱里的燃料会不断损耗和积累,我觉得从油箱燃料将会积累最多的起点(start)出发最好。如果有最优解
    //并不是从燃料将会最多的起点(start)出发,那么,为什么不从燃料将会最多的起点出发呢?至少情况没有变坏。这样就发现
    //最优解和我的方案没区别,所以这个方案就是最优解。
    //First, save the difference between gas and cost in an array named fuel, then find its maximum subarray. Then we start at its first element's position, to see if we can travel around the circuit once.
    //greedy algorithm: we should start at the gas station that we can accumulate most fuel

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int[] fuel = new int[gas.length];
            int start = 0;
            int sum = 0;
            for(int i = 0;i<gas.length;i++)
            {
                fuel[i] = gas[i] - cost[i];
                sum+=fuel[i];
                if(sum<0)
                {
                    sum = 0;
                    start = i+1;
                    if(start == gas.length)
                    {
                        return -1;
                    }
                }
            }
            int result = start;
            sum = 0;
            for(int i = 0;i<gas.length;i++)
            {
                if(start+i == gas.length)
                {
                    start = -i;
                }
                sum+=fuel[start+i];
                if(sum<0)
                {
                    return -1;
                }
            }
            return result;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.