81. Gas Station

8309 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ

  • 円形経路で接続されたガソリンスタンドのリストがあります.
    各ガソリンスタンドにはgas[i]のガソリンがあり、次のガソリンスタンドまではcost[i]が必要です.
    十分な油がなければ移動できないと言ったら、すべてのガソリンスタンドにアクセスできる起点インデックスを印刷します.
  • 始点が存在しない場合は、-1を返し、始点が一意である.


    • 1.すべてのアクセス（4680ミリ秒）

    

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for start in range(len(gas)):
            fuel = 0
            for i in range(start, len(gas) + start):
                index = i % len(gas)
                
                can_travel = True
                if gas[index] + fuel < cost[index]:
                    can_travel = False
                    break
                else:
                    fuel += gas[index] - cost[index]
                    
            if can_travel:
                return start
            
        return -1
    <各ガソリンスタンドのガソリンと移動料金>

  • 例では、正しい3号インデックスは、4を充填することができる点である.

  • 充填可能油量とインデックス番号、移動に必要な油量はすべてマークされています.

  • 最初から1つの格を出発点として指定し,残りのすべてのガソリンスタンドにアクセスする方法で解く.

  • ガソリンスタンドの経路は円形に接続されているので、モジュールで演算でき、インデックスを0から再指定できます.

  • すべてのガソリンスタンドにアクセスできるかどうかをチェックし、できればこの問題の出発点に一意性の制限があるので、その出発点を結果として直接戻ります.
  • の間で中断された場合、再び次の開始点でこの操作を繰り返します.

  • リングが重なり、O(n 2)となる.さらなる最適化が必要です.

    • 2.1回のアクセス（56ミリ秒）

    
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #모든 주유소 방문 가능 여부 판별
        if sum(gas) < sum(cost):
            return -1
        
        start, fuel = 0, 0
        for i in range(len(gas)):
            #출발점이 안되는 지점 판별
            if gas[i] + fuel < cost[i]:
                start = i + 1
                fuel = 0
            else:
                fuel += gas[i] - cost[i]
                
        return start

  • よく考えてみると、総油量が総費用より大きいと、必ず全体を訪問できる起点があるに違いない.
  • はもともと複数の場所であってもよいが、この問題には起点の唯一の制限があり、ここには必然的に1つの場所しか存在しない.

  • 費用がもっと高い時に回収すれば、今は存在しなければならない状況しか残っていない.
    したがって,訪問の全過程で成立しなければ,起点を1段後ろに押す.

  • 成立しない場所があれば、その先をすべて出発点にすることはできません.

  • 成立しない点を排除し、出発点を探すのは、数学で再帰法で証明するのと似ている.

  • 矛盾を引き出し、虚偽を排除すれば、可能な場所は排除できない場所であり、自然に残っている場所が正解である.

  • 2回のサイクルを1回に減らす.

  • すべてのsum()の文を比較することに合格すれば、1つの起点が必要で、1つの場所しか存在しないので、1回の検査だけで十分です.

  • O(n)に最適化され,運転速度が速い.
    運転速度は
  • 1回より80倍近く速い.
    • [規格]9251号:LCS(Python Python Python Python Python Python)
    C#の50掃雷