程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [leetcode] 134 Gas Station(經典dp || 貪心)

[leetcode] 134 Gas Station(經典dp || 貪心)

編輯:關於C++

(一)最容易想到的是O(n2)的解法

預處理出gas[i] - cost[i] 的數組,從每個非負的位置開始嘗試,只要能夠完成一個循環,就可以輸出結果;

對於返回-1的情況,我們經過思考和推論可以得出:對於一個循環數組,如果這個數組整體和 SUM >= 0,那麼必然可以在數組中找到這麼一個元素:從這個數組元素出發,繞數組一圈,能保證累加和一直是出於非負狀態。

所以只需要比較sum和0的大小就可以判斷是否有解。

(二)繼續對問題進行抽象,我們肯定希望一開始的路程都是加油>消耗的,這樣就可以累積油量應付後面的消耗量大的,根據這個思路,就轉變成求數組的最大連續子序列的和(並且記錄起始下標),這是我們前面接觸過的題目,例如hdu 1003;

但是因為是循環數組,我們還得考慮一種情況:就是首尾都是正數,怎麼辦呢?我們只需要再記錄並求得 最小連續子序列的和就可以了,最後取Maxsum和sum-Minsum的最大值。另外Minsum的小標要加一取余返回。

 

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
    	int sum=0;
        for(int i=0;iMaxsum)
	          {
        		 Maxsum=tot1;
        		 Maxpos=CurMaxp;
        	  }  
        	
        	
        	if(tot2+gas[i]>gas[i])//最小連續子序列和 
	        	tot2=gas[i];
	        else
        		tot2+=gas[i];
       	    	if(tot2=(sum-Minsum))
        return Maxpos;
        else
        return (Minpos+1)%gas.size();
        
    }
};
(三)還有另外一種簡單的思路。我們首先從i站點出發,若走到當前站點cur我們的油量<0,那麼只需要從cur+1繼續出發試探即可。在此不進行證明,但是我們可以宏觀的想一下,前面的任意的前綴站點段的油量和肯定是>0的,那麼去掉任意一個前綴,只會使油量變得更少,所以我們只能嘗試從cur+1重新開始。

 

 

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
    	int sum=0;
        for(int i=0;i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved