【贪心】加油站

2.PNG

解题思路：贪心算法

先创立一个新的数组，然后每个位置上的元素对应gas[i]-cost[i]，然后求出数组所有元素的和。如果和小于0，则说明卡车无法回环。若大于0，则继续往下走

局部最优解：当前位置向后数，在耗油差大于等于0的情况下，尽可能地大

1.创建一个数组，计算每个位置耗油量的差值：

a.若总和小于0，则返回false

b.若总和大于0，继续

2.从数组最后一个位置向后数，在累计和大于0情况下记录为currentMax。创建两个值currentMax和preMax，若currentMax大于preMax，更新其值，并更新index

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int* diffArr = (int*)malloc(gasSize * sizeof(int));
    int i, j;
    int sum = 0;
    for(i = 0; i < gasSize; i++) {
        diffArr[i] = gas[i] - cost[i];
        sum+=diffArr[i];
    }
    if(sum < 0)
        return -1;
    
    int index = -1;
    int preMax = INT_MIN;
    int currentMax;
    for(i = gasSize-1; i >= 0; i--) {
        if(diffArr[i] >= 0) {
            currentMax = 0;
            for(j = 0; j < gasSize-1; j++) {
                int ind = (i+j)%gasSize;
                if(currentMax+diffArr[ind] >= 0) {
                    currentMax+=diffArr[ind];
                } else
                    break;
            }
            if(preMax < currentMax) {
                index = i;
                preMax = currentMax;
            }
        }
    }
    return index;
}

1.PNG

改进：

解题思路：贪心算法

1.求出数组中gas[i]-cost[i]的和，若和小于0，说明不可能形成环

2.求和时同时记录最小值，当min>curSum时，更新min

3.从数组最后一个元素遍历，将min+=gas[i]，若min变为>=0，则说明从该位置出发可行

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int curSum = 0;
    int i;
    int min = INT_MAX;
    for(i = 0; i < gasSize; i++) {
        int diff = gas[i] - cost[i];
        curSum += diff;
        if(min > curSum)
            min = curSum;
    }
    if(curSum < 0)
        return -1;
    if(min >= 0)
        return 0;
    for(i = gasSize - 1; i >= 0; i--) {
        min+=(gas[i]-cost[i]);
        if(min >= 0)
            return i;
    }
    return 0;
}

1.PNG