（算法）加油站————＜贪心算法＞

1. 题⽬链接：134.加油站

2. 题⽬描述：

3. 解法（暴⼒解法->贪⼼）：

暴⼒解法：

a. 依次枚举所有的起点；

b. 从起点开始，模拟⼀遍加油的流程

贪⼼优化：

我们发现，当从i 位置出发，⾛了step 步之后，如果失败了。那么[i, i + step] 这个 区间内任意⼀个位置作为起点，都不可能环绕⼀圈。

因此我们枚举的下⼀个起点，应该是i + step + 1 。

C++算法代码： 

class Solution 
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
    {
        //找出符合条件的点
        int n=gas.size();
        for(int i=0;i<n;i++)    //选起始位置
        {
            int sum=0;   //净值
            int step=0; //移动的步数
            for(;step<n;step++)
            {
                int index = (i + step) % n; // 求出⾛ step 步之后的下标 
                sum+=gas[index]-cost[index];
                if(sum<0)
                {
                    break;
                }
            }
            if(sum>=0)
            {
                return i;
            }
            //改变初始值
            i+=step;
        }
        //所有加油站都做不到
        return -1;
    }
};

Java算法代码：

class Solution
{
	public int canCompleteCircuit(int[] gas, int[] cost)
	{
		int n = gas.length;
		for (int i = 0; i < n; i++) // 依次枚举所有的起点 
		{
			int rest = 0; // 统计净收益 
			int step = 0;
			for (; step < n; step++) // 枚举向后⾛的步数 
			{
				int index = (i + step) % n; // ⾛ step 步之后的下标 
				rest = rest + gas[index] - cost[index];
				if (rest < 0)
				{
					break;
				}
			}
			if (rest >= 0)
			{
				return i;
			}
			i = i + step; // 优化 
		}
		return -1;
	}
}