s*****r
发帖数: 108 | 1 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
少加油次数，特此分享
题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
限大的。问最少加油次数到达终点，或者不能走到。 |
s********u
发帖数: 1109 | |
m**********g
发帖数: 153 | 3 想不出来DP的方法。 DFS应该可以， two choices at each station, skip it or
pump gas. record the decisions and prune if next station/end point not
reachable |
t******d
发帖数: 1383 | |
D**********d
发帖数: 849 | |
d*k
发帖数: 207 | 6 題目的意思應該是從原點（0）到最後一點（n-1)，而不是像gas station要從任意點走
一圈。抛砖引玉说一个复杂度较高的DP。
f(i, p)表示位於i點，油量為p時候的解。令m = P + B(0) + B(1) + ... + B(n-1) 。
dist(i, j)表示i, j兩點間的距離。
顯然對於0 <= p <= m，有f(n-1, p) = 0
對於f(i, j), 0 <= i <= n -2, 0 <= j <= m，
若j >= dist(i, n - 1)則f(i, j) = 0
否則f(i, j) = 1 + min(f(k+1, j - dist(i, k＋1) + B(k)), k需要滿足條件
(1) i <= k <= n - 2。
(2) j >= dist(i, k)
(3) j - dist(i, k) + B(k) >= dist(k, k+1)
(4) f(k + 1, j - dist(i, k+1 ) + B(k)) >= 0
若無滿足條件的k，則f(i,j) = -1
最後返回f(0, P)。时间复杂度n * n * m。
我想如果面试可以先这么回答看看面试官的反应，实际上搜素加剪枝应该效果更好。比
如，对于每个点，预先计算从它开始走到最后一个点至少需要多少油。如果搜索时到这
个点油量已经低于最低油量，则可以跳过当前方案。应该还有很smart的剪枝。
期待楼主公布答案啊。
【在 s*****r 的大作中提到】
: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。
|
f******n
发帖数: 208 | 7 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
站取出优先队列。
这个题好像经常用在ACM入门题库里。 |
t**********r
发帖数: 2153 | 8 只要油箱大小不限，没有本质区别。
【在 s*****r 的大作中提到】
: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。
|
n****e
发帖数: 678 | 9 这个想法好.
【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。
|
s*****r
发帖数: 108 | 10 正解，此题和 jump game 还有 gas station 是完全不同的
【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。
|
|
|
b*******e
发帖数: 123 | 11 如果每次到一个加油站加油前必须把油箱倒空的话，那就是jump game。
不能用heap么？因为只要知道最值，相同的B_i不用保证顺序FILO
O(nlogn) |
d***n
发帖数: 832 | 12 我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
// Jump Game II using Greedy Method
public static int JumpGame2(int[] array)
{
if (array == null) return 0;
int n = array.Length;
if (n == 0 || n == 1) return 0;
int maxJump = 0;
int maxPosition = 0;
int i = 0;
while(i
{
maxPosition = Math.Max(maxPosition, array[i] + i);
if (maxPosition > 0) maxJump++;
if (maxPosition >= n - 1) return maxJump;
int savedI = i;
int subMaxPosition = 0;
for (int j = i + 1; j <= maxPosition; j++)
{
int temp = array[j] + j;
if (temp > subMaxPosition)
{
subMaxPosition = temp;
i = j;
}
}
if (savedI == i) return 0; // make progress in case there is
no path
}
return 0;
}
【在 s*****r 的大作中提到】
: 正解，此题和 jump game 还有 gas station 是完全不同的
|
b*******e
发帖数: 123 | 13
我第一开始也以为是，区别是你在每个index有可能有剩余。
例如
【2，1，0，0】
jump game II 不可能达到indiex 3, 这个能达到。
【在 d***n 的大作中提到】
: 我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
: // Jump Game II using Greedy Method
: public static int JumpGame2(int[] array)
: {
: if (array == null) return 0;
: int n = array.Length;
: if (n == 0 || n == 1) return 0;
: int maxJump = 0;
: int maxPosition = 0;
: int i = 0;
|
d***n
发帖数: 832 | 14 多谢。还真是，面试中要是碰到这个基本就挂了
【在 b*******e 的大作中提到】
:
: 我第一开始也以为是，区别是你在每个index有可能有剩余。
: 例如
: 【2，1，0，0】
: jump game II 不可能达到indiex 3, 这个能达到。
|
s*****r
发帖数: 108 | 15 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
少加油次数，特此分享
题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
限大的。问最少加油次数到达终点，或者不能走到。 |
s********u
发帖数: 1109 | |
m**********g
发帖数: 153 | 17 想不出来DP的方法。 DFS应该可以， two choices at each station, skip it or
pump gas. record the decisions and prune if next station/end point not
reachable |
t******d
发帖数: 1383 | 18 跟那个jump game有联系么？可以联想下。 |
D**********d
发帖数: 849 | |
d*k
发帖数: 207 | 20 題目的意思應該是從原點（0）到最後一點（n-1)，而不是像gas station要從任意點走
一圈。抛砖引玉说一个复杂度较高的DP。
f(i, p)表示位於i點，油量為p時候的解。令m = P + B(0) + B(1) + ... + B(n-1) 。
dist(i, j)表示i, j兩點間的距離。
顯然對於0 <= p <= m，有f(n-1, p) = 0
對於f(i, j), 0 <= i <= n -2, 0 <= j <= m，
若j >= dist(i, n - 1)則f(i, j) = 0
否則f(i, j) = -1, 若dist(i, i+1) > B(i) + j
= 1 + f(i+1, j + B(i) - dist(i, i + 1), 若 j < dist(i, i + 1)
<= j + B(i)
= min(1 + f(i+1, j + B(i) - dist(i, i + 1), f(i+1, j)), 若
dist(i, i+1) <= j
最後返回f(0, P)。时间复杂度n * m。
我想如果面试可以先这么回答看看面试官的反应，实际上搜素加剪枝应该效果更好。比
如，对于每个点，预先计算从它开始走到最后一个点至少需要多少油。如果搜索时到这
个点油量已经低于最低油量，则可以跳过当前方案。应该还有很smart的剪枝。
期待楼主公布答案啊。
【在 s*****r 的大作中提到】
: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。
|
|
|
f******n
发帖数: 208 | 21 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
站取出优先队列。
这个题好像经常用在ACM入门题库里。 |
t**********r
发帖数: 2153 | 22 只要油箱大小不限，没有本质区别。
【在 s*****r 的大作中提到】
: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。
|
n****e
发帖数: 678 | 23 这个想法好.
【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。
|
s*****r
发帖数: 108 | 24 正解，此题和 jump game 还有 gas station 是完全不同的
【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。
|
b*******e
发帖数: 123 | 25 如果每次到一个加油站加油前必须把油箱倒空的话，那就是jump game。
不能用heap么？因为只要知道最值，相同的B_i不用保证顺序FILO
O(nlogn) |
d***n
发帖数: 832 | 26 我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
// Jump Game II using Greedy Method
public static int JumpGame2(int[] array)
{
if (array == null) return 0;
int n = array.Length;
if (n == 0 || n == 1) return 0;
int maxJump = 0;
int maxPosition = 0;
int i = 0;
while(i
{
maxPosition = Math.Max(maxPosition, array[i] + i);
if (maxPosition > 0) maxJump++;
if (maxPosition >= n - 1) return maxJump;
int savedI = i;
int subMaxPosition = 0;
for (int j = i + 1; j <= maxPosition; j++)
{
int temp = array[j] + j;
if (temp > subMaxPosition)
{
subMaxPosition = temp;
i = j;
}
}
if (savedI == i) return 0; // make progress in case there is
no path
}
return 0;
}
【在 s*****r 的大作中提到】
: 正解，此题和 jump game 还有 gas station 是完全不同的
|
b*******e
发帖数: 123 | 27
我第一开始也以为是，区别是你在每个index有可能有剩余。
例如
【2，1，0，0】
jump game II 不可能达到indiex 3, 这个能达到。
【在 d***n 的大作中提到】
: 我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
: // Jump Game II using Greedy Method
: public static int JumpGame2(int[] array)
: {
: if (array == null) return 0;
: int n = array.Length;
: if (n == 0 || n == 1) return 0;
: int maxJump = 0;
: int maxPosition = 0;
: int i = 0;
|
d***n
发帖数: 832 | 28 多谢。还真是，面试中要是碰到这个基本就挂了
【在 b*******e 的大作中提到】
:
: 我第一开始也以为是，区别是你在每个index有可能有剩余。
: 例如
: 【2，1，0，0】
: jump game II 不可能达到indiex 3, 这个能达到。
|
n*****f
发帖数: 17 | 29 维护一个大顶堆，每遇到一个station，先判断现在油量是否为负。为负就不停从取堆
顶元素加上直到变正。然后把这个station的油量加到堆里。O(nlogn) |
