資訊專欄INFORMATION COLUMN
摘要：這樣我們開始遍歷數(shù)組，如果是負(fù)數(shù)，說明開出該加油站后無法到達(dá)下一個(gè)加油站，這樣旅程的起點(diǎn)更新為下一個(gè)加油站。
Gas Station
貪心法 復(fù)雜度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.
時(shí)間 O(N) 空間 O(K)
思路我們把將gas中每個(gè)值都減去cost中對應(yīng)的值，這樣gas就成為了開出該加油站到下一個(gè)加油站時(shí)，該加油站加的油用剩到多少。這樣我們用一個(gè)tank變量記錄汽車每開到一個(gè)加油站后油箱里累計(jì)剩下多少油，每到一個(gè)加油站就更新。這樣我們開始遍歷gas數(shù)組，如果tank是負(fù)數(shù)，說明開出該加油站后無法到達(dá)下一個(gè)加油站，這樣旅程的起點(diǎn)更新為下一個(gè)加油站。因?yàn)槁贸淌黔h(huán)狀的我們遍歷的加油站數(shù)組應(yīng)為2*gas.length-1，這樣能保證我們以最后一個(gè)加油站為起點(diǎn)時(shí)也能繼續(xù)驗(yàn)證。
代碼public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// gas減去cost，得到凈油值
for(int i = 0; i < cost.length; i++){
gas[i] -= cost[i];
}
int tank = 0, res = -1;
for(int i = 0; i < gas.length * 2 - 1; i++){
int idx = i % gas.length;
// 更新油箱
tank += gas[idx];
// 如果油箱為負(fù)，說明走不到下一個(gè)加油站
if(tank < 0){
res = idx + 1;
tank = 0;
}
}
// 如果起點(diǎn)在最后一個(gè)加油站之后，說明無解
return res >= gas.length ? -1 : res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64649.html
摘要：看到這個(gè)題目，怎樣可以不把它當(dāng)成一個(gè)環(huán)路來分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點(diǎn)四個(gè)參數(shù)。大體上說，只要，一定有解。所以跳過這個(gè)耗油量很大的油站，然后將下一個(gè)油站作為起點(diǎn)繼續(xù)判斷即可。 Problem There are N gas stations along a circular route, where the amount ...
摘要：先實(shí)現(xiàn)棧操作遍歷鏈表，把每個(gè)節(jié)點(diǎn)都進(jìn)中然后再遍歷鏈表，同時(shí)節(jié)點(diǎn)依次出棧，二者進(jìn)行比較。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個(gè)人主頁：應(yīng)無...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個(gè)人主頁：應(yīng)無所住而生...
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 1602·2021-11-16 11:44
閱讀 7504·2021-09-22 15:00
閱讀 4539·2021-09-02 10:20
閱讀 1974·2021-08-27 16:20
閱讀 2404·2019-08-26 14:00
閱讀 2917·2019-08-26 11:44
閱讀 1650·2019-08-23 18:33
閱讀 1882·2019-08-22 17:28
