avatar
s*r
1
做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station,关心的是最
少加油次数,特此分享
题目是这样的,有 N 个加油站(给出坐标)直线排列,每个加油站最多加 B(i) 升油
。一开始车有 P 升油在原点,单位油走单位长度,需要行驶 L 长度。同样油箱也是无
限大的。问最少加油次数到达终点,或者不能走到。
avatar
s*u
2
lz是Gas station问题迷,哈哈
avatar
m*g
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
avatar
t*d
4
跟那个jump game有联系么?可以联想下。
avatar
D*d
5
这不是 Jump game 吗?
avatar
d*k
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 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点,或者不能走到。

avatar
f*n
7
这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利,把
这个权利放入优先队列。等你发现没油了,就从优先队列里找油最多的站来加,并将此
站取出优先队列。
这个题好像经常用在ACM入门题库里。
avatar
t*r
8
只要油箱大小不限,没有本质区别。

【在 s*****r 的大作中提到】
: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station,关心的是最
: 少加油次数,特此分享
: 题目是这样的,有 N 个加油站(给出坐标)直线排列,每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点,单位油走单位长度,需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点,或者不能走到。

avatar
n*e
9
这个想法好.

【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利,把
: 这个权利放入优先队列。等你发现没油了,就从优先队列里找油最多的站来加,并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

avatar
s*r
10
正解,此题和 jump game 还有 gas station 是完全不同的

【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利,把
: 这个权利放入优先队列。等你发现没油了,就从优先队列里找油最多的站来加,并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

avatar
b*e
11
如果每次到一个加油站加油前必须把油箱倒空的话,那就是jump game。
不能用heap么?因为只要知道最值,相同的B_i不用保证顺序FILO
O(nlogn)
avatar
d*n
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 是完全不同的
avatar
b*e
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;

avatar
d*n
14
多谢。还真是,面试中要是碰到这个基本就挂了

【在 b*******e 的大作中提到】
:
: 我第一开始也以为是,区别是你在每个index有可能有剩余。
: 例如
: 【2,1,0,0】
: jump game II 不可能达到indiex 3, 这个能达到。

avatar
s*r
15
做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station,关心的是最
少加油次数,特此分享
题目是这样的,有 N 个加油站(给出坐标)直线排列,每个加油站最多加 B(i) 升油
。一开始车有 P 升油在原点,单位油走单位长度,需要行驶 L 长度。同样油箱也是无
限大的。问最少加油次数到达终点,或者不能走到。
avatar
s*u
16
lz是Gas station问题迷,哈哈
avatar
m*g
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
avatar
t*d
18
跟那个jump game有联系么?可以联想下。
avatar
D*d
19
这不是 Jump game 吗?
avatar
d*k
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 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点,或者不能走到。

avatar
f*n
21
这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利,把
这个权利放入优先队列。等你发现没油了,就从优先队列里找油最多的站来加,并将此
站取出优先队列。
这个题好像经常用在ACM入门题库里。
avatar
t*r
22
只要油箱大小不限,没有本质区别。

【在 s*****r 的大作中提到】
: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station,关心的是最
: 少加油次数,特此分享
: 题目是这样的,有 N 个加油站(给出坐标)直线排列,每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点,单位油走单位长度,需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点,或者不能走到。

avatar
n*e
23
这个想法好.

【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利,把
: 这个权利放入优先队列。等你发现没油了,就从优先队列里找油最多的站来加,并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

avatar
s*r
24
正解,此题和 jump game 还有 gas station 是完全不同的

【在 f******n 的大作中提到】
: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利,把
: 这个权利放入优先队列。等你发现没油了,就从优先队列里找油最多的站来加,并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

avatar
b*e
25
如果每次到一个加油站加油前必须把油箱倒空的话,那就是jump game。
不能用heap么?因为只要知道最值,相同的B_i不用保证顺序FILO
O(nlogn)
avatar
d*n
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 是完全不同的
avatar
b*e
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;

avatar
d*n
28
多谢。还真是,面试中要是碰到这个基本就挂了

【在 b*******e 的大作中提到】
:
: 我第一开始也以为是,区别是你在每个index有可能有剩余。
: 例如
: 【2,1,0,0】
: jump game II 不可能达到indiex 3, 这个能达到。

avatar
n*f
29
维护一个大顶堆,每遇到一个station,先判断现在油量是否为负。为负就不停从取堆
顶元素加上直到变正。然后把这个station的油量加到堆里。O(nlogn)
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。