網(wǎng)站建設(shè)和網(wǎng)頁設(shè)計是不是一樣搭建一個app平臺需要多少錢
題目:
鏈接:LeetCode 134. 加油站
難度:中等
在一條環(huán)路上有 n 個加油站,其中第 i 個加油站有汽油 gas[i] 升。
你有一輛油箱容量無限的的汽車,從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發(fā),開始時油箱為空。
給定兩個整數(shù)數(shù)組 gas 和 cost ,如果你可以繞環(huán)路行駛一周,則返回出發(fā)時加油站的編號,否則返回 -1 。如果存在解,則 保證 它是 唯一 的。
示例 1:
輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋:
從 3 號加油站(索引為 3 處)出發(fā),可獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站,此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站,此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站,此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站,此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站,你需要消耗 5 升汽油,正好足夠你返回到 3 號加油站。
因此,3 可為起始索引。
示例 2:
輸入: gas = [2,3,4], cost = [3,4,3]
輸出: -1
解釋:
你不能從 0 號或 1 號加油站出發(fā),因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發(fā),可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站,此時油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站,此時油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站,因為返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,無論怎樣,你都不可能繞環(huán)路行駛一周。
提示:
- gas.length == n
- cost.length == n
- 1 <= n <= 105
- 0 <= gas[i], cost[i] <= 104
方法一:
函數(shù)圖像法:
sum 代表路途中油箱的油量,如果把這個「最低點」作為起點,即把這個點作為坐標(biāo)軸原點,就相當(dāng)于把圖像「最大限度」向上平移了:
如果經(jīng)過平移后圖像全部在 x 軸以上,就說明可以行使一周。
代碼一:
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int minsum = 0, minpos = 0; //函數(shù)最低點的值,函數(shù)最低點的坐標(biāo)(出發(fā)站編號)int sum = 0;for(int i = 0; i < n; i++){sum += gas[i] - cost[i];if(sum < minsum) {minsum = sum;minpos = i + 1;}}if(sum < 0) return -1;return minpos % n;}
};
時間復(fù)雜度O(n),空間復(fù)雜度O(1)。
方法二:
貪心解法:
用貪心思路解決這道題的關(guān)鍵在于以下這個結(jié)論:
如果選擇站點i作為起點「恰好」無法走到站點j,那么i和j中間的任意站點k都不可能作為起點。
比如說,如果從站點1出發(fā),走到站點5時油箱中的油量「恰好」減到了負(fù)數(shù),那么說明站點1「恰好」無法到達站點5;那么你從站點2,3,4任意一個站點出發(fā)都無法到達5,因為到達站點5時油箱的油量也必然被減到負(fù)數(shù)。
如何證明這個結(jié)論?
假設(shè)sum記錄當(dāng)前油箱中的油量,如果從站點i出發(fā)(sum = 0),走到j(luò)時恰好出現(xiàn)sum < 0的情況,那說明走到i, j之間的任意站點k時都滿足sum > 0,對吧。
如果把k作為起點的話,相當(dāng)于在站點k時sum = 0,那走到j(luò)時必然有sum < 0,也就是說k肯定不能是起點。
拜托,從i出發(fā)走到k好歹sum > 0,都無法達到j(luò),現(xiàn)在你還讓sum = 0了,那更不可能走到j(luò)了對吧。
綜上,這個結(jié)論就被證明了。
回想一下我們開頭說的暴力解法是怎么做的?
如果我發(fā)現(xiàn)從i出發(fā)無法走到j(luò),那么顯然i不可能是起點。
現(xiàn)在,我們發(fā)現(xiàn)了一個新規(guī)律,可以推導(dǎo)出什么?
如果我發(fā)現(xiàn)從i出發(fā)無法走到j(luò),那么i以及i, j之間的所有站點都不可能作為起點。
看到冗余計算了嗎?看到優(yōu)化的點了嗎?
這就是貪心思路的本質(zhì),如果找不到重復(fù)計算,那就通過問題中一些隱藏較深的規(guī)律,來減少冗余計算。
代碼二:
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n;){int sum = 0;bool flag = true; //以i為出發(fā)站時能否環(huán)行一周for(int j = i; j < i + n; j++){sum += gas[j % n] - cost[j % n]; //行至第j+1個加油站時,油箱內(nèi)的油量if(sum < 0) {if(j + 1 >= n) return -1; //全部出發(fā)點已遍歷完,未找到可行解i = (j + 1) % n; //無法從第i站到第j+1站,則從中間任意一站都無法到第j+1站。那么以第j+1站為出發(fā)站繼續(xù)檢查flag = false;break;}}if(flag) return i; //以第i站為出發(fā)站可以走完一周,返回i}return -1;}
};
時間復(fù)雜度O(n),空間復(fù)雜度O(1)。