摘要:看到這個題目,怎樣可以不把它當成一個環路來分析,以及減少多余的空間呢例如,我們引入單次剩余油量,剩余油量和,總剩余油量和,以及可行起點四個參數。大體上說,只要,一定有解。所以跳過這個耗油量很大的油站,然后將下一個油站作為起點繼續判斷即可。
Problem
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.
ExampleGiven 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station"s index is 2.
ChallengeO(n) time and O(1) extra space
Note看到這個題目,怎樣可以不把它當成一個環路來分析,以及減少多余的空間呢?
例如gas[i]=[1,1,3,1], cost[i]=[2,2,1,1],我們引入單次剩余油量res,剩余油量和sum,總剩余油量和total,以及可行起點start四個參數。大體上說,只要total > 0,一定有解。下面來找起點,當sum < 0的時候,一定是上一個加油站的單次剩余油量res為負,且與上一次的剩余油量和sum相加依然為負,說明在上一個加油站出現了消耗大于補給的情況,因此一定不能將它作為起點。所以跳過這個耗油量很大的油站,然后將下一個油站作為起點繼續判斷即可。
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int start = 0, sum = 0, total = 0; for (int i = 0; i < gas.length; i++) { int res = gas[i] - cost[i]; //如果上一次的剩余油量之和sum’加上油站油量gas[i-1], //依然少于上次次的消耗油量cost[i-1] if (sum < 0) { //更新出發地點為第i個加油站 start = i; //更新剩余油量之和為到達第i個加油站補給后的剩余油量 sum = res; } //否則,將之前的剩余油量之和sum加上本次消耗及補給后的剩余油量res else { sum += res; } //累計所有油站的可補給油量和總消耗油量之差(res) total += res; } return total >= 0 ? start : -1; } }
Optimized:
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int start = 0, sum = 0, total = 0; for (int i = 0; i < gas.length; i++) { int res = gas[i] - cost[i]; sum += res; total += res; if (sum < 0) { sum = 0; start = i + 1; } } return total >= 0 ? start : -1; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65660.html
摘要:這樣我們開始遍歷數組,如果是負數,說明開出該加油站后無法到達下一個加油站,這樣旅程的起點更新為下一個加油站。 Gas Station 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 unlimi...
Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...
Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...
摘要:建立兩個堆,一個堆就是本身,也就是一個最小堆另一個要寫一個,使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里,更大的數放在最小堆,較小的數放在最大堆。同時,確保最大堆的比最小堆大,才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
摘要:首先,我們應該了解字典樹的性質和結構,就會很容易實現要求的三個相似的功能插入,查找,前綴查找。既然叫做字典樹,它一定具有順序存放個字母的性質。所以,在字典樹的里面,添加,和三個參數。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...
閱讀 4675·2021-09-22 16:06
閱讀 2074·2021-09-22 15:22
閱讀 1410·2019-08-30 15:54
閱讀 2512·2019-08-30 15:44
閱讀 2341·2019-08-29 16:31
閱讀 2010·2019-08-29 16:26
閱讀 2328·2019-08-29 12:41
閱讀 731·2019-08-29 12:22