Massive Algorithms: ITint5 2- 环形路加油

ITint5 2- 环形路加油

https://github.com/AnnieKim/ITint5/blob/master/002_%E7%8E%AF%E5%BD%A2%E8%B7%AF%E5%8A%A0%E6%B2%B9.cpp
链接: http://www.itint5.com/oj/#2
问题:
有一个环形公路上有n个加油站，第i个加油站的油量为a[i]。
假设有一辆邮箱体积无穷大的汽车，初始邮箱是空的，汽车从加油站i行驶到加油站i+1需耗油g[i]。
问是否能够选出某个加油站作为起点，使汽车能够绕环形公路行驶一圈返回到该加油站。
实现函数int selectGasStation(int a[], int g[], int n)。
如果存在满足条件的加油站，返回该加油站的序号(0-based)。否则返回-1。
提示：n可能达到106，O(n^2)的枚举算法会超出时间限制。
http://xsk.tehon.org/den/index.php/category/tech/gas-station-on-the-circle.html

方法一：从左往右遍历，在油量和最少的位置的下一个位置出发。

int res = 0, min = N[0] - g[0], sum = min, i = 1;
while(i < n) {
    sum += N[i] - g[i];
    if(sum < min) {
        min = sum;
        res = i;
    }
    ++i;
}
return sum >= 0 ? (res + 1) % n : -1;

方法二：开辟一个长度为N的数组v，记录N[i]-g[i]。从后往前遍历数组v，如果v[i]小于零，将其与v[i-1]合并，因为此时i不可能作为起点。如果v[i]不小于零，记入sum，并记录该位置pos（有可能作为起点）。最后，如果v[0]大于等于零，说明整个路段已经没有负的v[i]。返回0即可。如果v[0]+sum>=0，有满足条件的加油站，返回pos。否则，返回-1。

int v[n];
for(int i = 0; i < n; ++i)
    v[i] = N[i] - g[i];
int sum = 0, pos = -1;
for(int i = n-1; i > 0; --i) {
    if(v[i] >= 0) {
        sum += v[i];
        pos = i;
    } else {
        v[i-1] += v[i];
    }
}
if(v[0] >= 0) 
    return 0;
else if(v[0] + sum >= 0)
    return pos;
else 
    return -1;

方法三：开辟一个长度为2*n-1的数组v，记录N[i]-g[i]，这样就把一个环转化为一条线。使用两个指针start和end。如果[start,end]区间和小于0，令start=end+1并继续。直至找到长度为N的区间[start,end]，并且区间和大于等于0。找到返回start，找不到返回-1。

int v[2 * n];
for (int i = 0; i < n; ++i) {
    v[i] = N[i] - g[i];
    v[i+n] = N[i] - g[i];
}
int sum = 0;
for (int start = 0, end = 0; start <= n && end < 2 * n; end++) {
    if(sum + v[end] < 0) {
        start = end + 1;
        sum = 0;
    } else {
        if(end - start == n - 1) 
            return start;
        sum += v[end];
    }
}
return -1;

以上三种解法的时间复杂度均为O(n)。对于任意一个O(n)复杂度的DP题目，必有辅助数组仅与n有关，若刨除不需要计算的量还与两个以上的量有关，则不可能做到O(n)。
http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html

环形，即可以考虑2*N-1的展开处理。定义

c[i]=a[i]−g[i]表示完成某一路段真实耗油量（因为起点加了一些油）。于是，问题转化为求以某一起点slow开始到长度n节点的所有前缀和均为正的问题。

以slow点起始位置，如果在途中的fast点，出现前缀和为负数的情况，那么slow到fast之间的点，则不可能满足约束。因此直接跳过这些点，从slow = fast +1开始找。因此，时间复杂度为

O(N)。

int selectGasStation(const vector<int> &a, const vector<int> &g) {
    if(a.size() == 0 || g.size() == 0 || a.size() != g.size()) return -1;
    vector<int> c(a.size() * 2 -1);
    int gas_count = a.size();
    for(int i=0; i<gas_count; i++)
    {
        c[i] = a[i] - g[i];
        if (i < gas_count - 1)
            c[i+gas_count] = a[i] - g[i];
    }
    int slow = 0;
    int fast = 0;
    int has_gas = 0;
    while(fast < c.size()){
        has_gas += c[fast];
        if (has_gas < 0) {
            slow = fast+1;
            has_gas = 0;
        }
        if (fast - slow +1 == gas_count) return slow;
        fast++;
    }
    return -1;
}

Solution:
1. 从左往右遍历，记住油量和最少的位置，从其下一个位置出发。
2. 开辟一个长度为N的数组v，记录a[i]-g[i]。
从后往前遍历数组v。
如果v[i]小于零，将其与v[i-1]合并，因为此时i不可能作为起点。
如果v[i]不小于零，记入sum，并记录该位置pos（有可能作为起点）。
最后，如果v[0]大于等于零，说明整个路段已经没有负的v[i]。返回0即可。
如果v[0]+sum>=0，有满足条件的加油站，返回pos。
否则，返回-1。
3. 开辟一个长度为2*N-1的数组v，记录a[i]-g[i]（环转化为线性）。
使用两个指针start和end。
如果[start, end]区间和小于0，令start = end + 1并继续。
直至找到长度为N的区间[start, end]，并且区间和大于等于0。找到返回start。
以上三种方案的时间复杂度皆为O(N)。
*/

int selectGasStation_1(const vector<int> &a, const vector<int> &g) {
int N = a.size();
int res = 0, min = a[0] - g[0], sum = min;
for (int i = 1; i < N; ++i)
{
sum += a[i] - g[i];
if (sum < min) {
min = sum;
res = i;
}
}
return sum >= 0 ? (res + 1) % N : -1;
}

int selectGasStation_2(const vector<int> &a, const vector<int> &g) {
int N = a.size();
int v[N];
for (int i = 0; i < a.size(); ++i)
v[i] = a[i] - g[i];
int sum = 0, pos = -1;
for (int i = N-1; i > 0; --i)
{
if (v[i] >= 0) {
sum += v[i];
pos = i;
} else {
v[i-1] += v[i];
}
}
if (v[0] >= 0) return 0;
else if (v[0] + sum >= 0) return pos;
else return -1;
}

int selectGasStation_3(const vector<int> &a, const vector<int> &g) {
int N = a.size();
int v[2 * N];
for (int i = 0; i < N; ++i)
{
v[i] = a[i] - g[i];
v[i+N] = a[i] - g[i];
}
int sum = 0;
for (int start = 0, end = 0; start <= N && end < 2 * N; end++)
{
if (sum + v[end] < 0) {
start = end + 1;
sum = 0;
} else {
if (end - start == N - 1)
return start;
sum += v[end];
}
}
return -1;
}

int selectGasStation(const vector<int> &a, const vector<int> &g)
{
vector<int> f;
if (a.size() <= 1)
return 0;
int size = a.size();
int i;
for (i = 0; i < size; ++ i)
f.push_back(a[i] - g[i]);
vector<int> result(2 * size + 1, -1);
result[0] = f[0];
int count = 0;
i = 1;
while (count < size && i <= 2*size)
{
if (result[i-1] >= 0) {
result[i] = result[i-1] + f[i%size];
count ++;
} else {
count = 0;
result[i] = f[i%size];
}
i ++;
}
if (count == size) {
return (i-1)%size;
}
return -1;
}
https://github.com/ralphite/ITint5-Answers-Java/blob/master/%E7%8E%AF%E5%BD%A2%E8%B7%AF%E5%8A%A0%E6%B2%B9.java
public int selectGasStation(int[] a, int[] g) {
if(a == null || g == null || a.length != g.length) return -1;
int totalLeftGas = 0;
int leftGas = 0;
int startIndex = 0;
for(int i = 0; i < a.length; i++) {
totalLeftGas += a[i] - g[i];
leftGas += a[i] - g[i];
if(leftGas < 0) {
startIndex = i + 1;
leftGas = 0;
}
}

return totalLeftGas >= 0 ? startIndex : -1;
}
https://github.com/zdzapple/itint5/blob/master/%E7%8E%AF%E5%BD%A2%E8%B7%AF%E5%8A%A0%E6%B2%B9.cpp
/**
计算辅助数组f(i),其含义为从i点开始到达i+1时，汽车所剩的油。有:
f(i) = g(i)-d(i)
若f(i)<0 则显然从i点出发不可能完成任务。

题目的O(n)解法依赖于以下结论，在面试的时间内，要迅速发现这个规律不是一件容易的事。
从任意一个点s开始扫描,如果到点e之前汽车没油了,那么说明从s到e-1中的所有点出发，都不可能完成任务。

设从s点到e时，油箱中剩下的油为t(s,e). 完成不了任务，说明t(s,e)<0
证明：
显然t(s,e) = f(s) + t(s+1,e)
若从s开始是合理的，则必有f(s)>=0
因此t(s+1,e) = t(s+1,e)-f(s)
若t(s,e)<0,那么必有t(s+1,e)<0,显然从s+1开始也完成不了任务。
由此可得结论。

对于任意一个O(n)复杂度的DP题目，都需要类似的结论做支持，即f(n)仅与一个变量n有关，如果和两个变量相关即f(s,n)那么复杂度必定不为O(n)。
这个题目中直观看到相关的变量有起始点和终止点2个，所以要通过分析，剔除和无关的变量，消除无需计算的部分，才能得出正确结果。
之后MS又加了一面,题目是有一个环路,中间有N个加油站,加油站里面的油是g1,g2...gn,加油站之间的距离是d1,d2...dn,问其中是否能找到一个加油站,使汽车从这个加油站出发,走完全程,这个题有一个O(n)的算法,最多扫描2N次元素,就是先从任意一个点a开始扫描,如果到点b和点b-1之前汽车没油了,那么说明点a到点b-1都不是可能的解,所以只要从点b开始继续扫就可以了,直到有一个点c,从c出发能够成功返回到c,那么c就是需要的解,如果再次扫描到了点a还没有找到解则说明无解.最坏情况就是c=a-1,那么需要扫描2N-1个加油站,当然可以在第一圈扫描时记载部分结果来使第二圈扫描更快.

ITint5 2- 环形路加油

Labels

Popular Posts