首页 > 其他 > 详细

Gas Station

时间:2014-12-21 11:27:30      阅读:237      评论:0      收藏:0      [点我收藏+]

题目提示采用贪心算法,不知道别人怎么实现的,可以参考下别人的思路。

答案如下:

class Solution {
public:
	vector<int> leftgas;
	int len;
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        len = gas.size();
		int i=0;
		leftgas.resize(gas.size());
		for (i=0; i<len; i++)
	    {
         	leftgas[i] = gas[i] - cost[i];
		}
		pair<bool,int> temp;
        temp = IndexComplete();
        if(temp.first == true)
		 return temp.second;


		return -1;
    }
	pair<bool,int> IndexComplete()
	{
	  int allgas = 0;
	  int backwardindex = 0;
	  int forwardindex = 0;
	  bool ret;
      while(1)
      {
        allgas +=leftgas[forwardindex++];
		
		if(allgas >= 0)
		{
		 
		   if(forwardindex  == backwardindex || forwardindex  == len)
		   	return pair<bool,int>(true,backwardindex);
		}
		else
		{
            ret = SupplyGas(allgas,backwardindex,forwardindex);
			if(ret == false)
			return pair<bool,int>(false,backwardindex);

		}
		
	  }

	}
	bool  SupplyGas(int &allgas,int& backwardindex,int forwardindex )
	 {
	  	
        while(1)
        {
          if(backwardindex == 0)
          {
             backwardindex = len-1;
		  }
		  else
		  {
             backwardindex--;
		  }
		  
          allgas += leftgas[backwardindex];
		  if(allgas >= 0)
		  {
             return true;
		  }
		  else
		  {
            if(backwardindex <= forwardindex)
			  return false;

		  }
		 
		 
		}

	 }
};

 

Gas Station

原文:http://www.cnblogs.com/xgcode/p/4176286.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!