Leetcode水题一道

            转眼间到了2014年，最近在实验室做一些ANDROID框架层代码的定制，（其实没什么技术含量的吧），几个月也没写博客了，这几个月看的最多的是C++和ANDROID FRAMWORK源码，零星的看了一些虚拟机的知识，垃圾回收机制，LINUX多线程，STL源码等很杂的东东吧。今天去刷了一道水题（真心好久木有编程了，一般都是修修补补的），第一次编写报 时间复杂度过高，痛定思痛，修改为常数级别的检索。写博客在于分享，希望大家新年快乐，万事如意。
            题目如下：
            

            There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

            You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas             stations.

           Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

            Note:
            The solution is guaranteed to be unique.
            1.第一看到这个题目，马上写了一个回溯遍历，测第一个NODE不行，就挨个换下一个测嘛，结果时间复杂度O（N^2),Not Accepted
            2.第二次仔细研读题目，发现访问是一个环形的，那么当从一个结点出发到某个节点终止时，我们可以判断终止节点不可能继续，是因为GAS 不足，从当前已访问的节点段范围内，我们无法选择一个新的起点了（第一次想遍历是脑子都没转，遍历还会从不可能的结果开始），那么从终止节点的下一个开始，再重复上诉过程，直到走一个步数为N的完成过程。
            代码如下：
            1.回溯法求解（时间复杂度过高）
            class Solution {
            public:
            int canCompleteCircuit(vector &gas, vector &cost) {
        
                        return travelGas(gas,cost,gas.size());
             }//try use recurse
    
            int checkGas(vector &gas, vector &cost,int depth,int index,int reserve)
            {
                if(gas[index]+reserve>=cost[index])
                        return (index+depth)%(gas.size());//enough Gas
                  return -1;
            }//condition check
    
            int travelGas(vector &gas, vector &cost,int depth,int current_index=0,int reserve=0)
            {
                       if(depth==gas.size()&&depth>1)//start
                        {
                        reserve=0;
                        int value=-1;
                        for(int i=0;i                         {
                         if(checkGas(gas,cost,depth,i,reserve)!=-1)
                                  value=travelGas(gas,cost,depth-1,(i+1)%(gas.size()),gas[i]-cost[i]);//start
                         if(value!=-1)
                                     return value;//collect value
                        }//for
                    return -1;
                   }//if
                   else if(depth>1)
                  {
                   for(int i=0;i                        {
                      if(checkGas(gas,cost,depth,current_index,reserve)!=-1)
                           return travelGas(gas,cost,depth-1,(current_index+1)%(gas.size()),reserve+gas[current_index]-cost[current_index]); 
                       
                       }
           
               }//else
                 else if(depth==1)
               {
                           return checkGas(gas,cost,depth,current_index,reserve);
                    
               }//else
               return -1;
      
            }//travelGas
    };
            2.环形
        int canCompleteCircuit(vector &gas, vector &cost) {
        int current_step=0;//step record
        int current_reserve=0;//spare gas
        int N=2*gas.size();//limit visit
        
        for(int i=0;i         {
            if(gas[i%(N/2)]+current_reserve>=cost[i%(N/2)])
            {
                current_step++;//count steps,not index
                if(current_step==N/2)
                {
                    int start=(i-N/2+1+N)%N;//ok to combine 
                    if(start>N/2)
                        return start-N/2;//second 
                    else
                        return  start;
                }//if
                current_reserve=current_reserve+gas[i%(N/2)]-cost[i%(N/2)];//update to next node
            }//if
            else
            {
                current_step=0;
                current_reserve=0;
            }//else
      }//for
      return -1;
}

            备注：求书友一起阅读开源项目，相互探讨～～～