Chinaunix首页 | 论坛 | 博客
  • 博客访问: 143121
  • 博文数量: 9
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 729
  • 用 户 组: 普通用户
  • 注册时间: 2013-05-08 14:00
文章分类

全部博文(9)

文章存档

2015年(1)

2014年(2)

2013年(6)

分类: C/C++

2014-01-24 14:31:59

            转眼间到了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;
}

            备注:求书友一起阅读开源项目,相互探讨~~~






阅读(2867) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~