题目
背景: 有一辆汽车, 有n个汽油站.
给定两个数组, 第一个数组表示每个汽油站的汽油量, 第二个数组表示走到下一个汽油站耗费的汽油.
求汽车从哪个站出发可以回到该站, 回不到该站返回-1.
Input: gas: [1,2,3,4,5], cost: [3,4,5,1,2]
Output: 3
Input: gas: [2,3,4], cost: [3,4,3]
Output: -1
思路1
双循环. 假设从每个站出发, 看是否可以到达终点.
时间复杂度O(n²)
int canCompleteCircuit2(vector<int>& gas, vector<int>& cost) {
vector<int> cache;
int num = 0;
for (int i = 0;i < gas.size();i++) {
num = gas[i] - cost[i];
if (num < 0) continue;
for (int j = 1;j <= gas.size();j++) {
int index = (i + j) % gas.size();
num += gas[index] - cost[index];
if (num < 0) {
break;
}
}
if (num >= 0) {
return i;
}
}
return -1;
}
思路2
通过数学变换, 如果汽油总量大于花费总量, 就一定可以回到终点.
问题就是找到出发点, 出发点应该是最缺汽油的位置, 即总路程的汽油最少的位置.
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum = 0, start = 0, min = INT_MAX;
for(int i = 0; i < gas.size(); i++){
sum += gas[i]-cost[i];
if(sum < min){
min = sum;
start = i;
}
}
return sum < 0 ? - 1 : (start+1) % gas.size();
}
总结
貌似DP和递归都可以, 还是要使用常规方案解答. 在循环的时候可以添加缓存.
网友评论