C***U
发帖数: 2406 | 1 我也是从前面关于这个问题讨论里的回复得到的启发
给定的是一个整数数组A 假设长度是n
我们可以构造这样一个directed graph
vertex是v[0], v[1], ..., v[n-1]
edge是如果我们从v[i]出发到v[i+1],v[i+2],...,v[i+A[i]]都有1个edge
那么jump game 1就是寻找有没有从v[0]到v[n-1]的一条路径
jump game 2就是寻找最短从v[0]到v[n-1]的路径
两个题目都是O(n)的时间 因为我们的edge数目是小于c*n,这里c是数组A里面的最大数字
用bfs 我们的时间就是O(n)了
不知道这个讨论对不对
请大牛们指正啊 | f*********i
发帖数: 197 | 2 What is the benefit of this approach?
1) It requires data pre-processing, that is at least O(n) time, worst case O
(n^2) time, and O(n) additional space.
2) Event the directed graph has been built, it still need O(n) time, however
, we already have O(n) time and O(1) space solution...... | C***U
发帖数: 2406 | 3 1 数据不用preprocessing 可以在原来的数据结构上直接处理
2 我前面搜了帖子 说最好也要O(n^2)啊。。。。
倒不是说这个算法有多好 就是讨论一下
然后把两个题目给一个统一的解法么
O
however
【在 f*********i 的大作中提到】
: What is the benefit of this approach?
: 1) It requires data pre-processing, that is at least O(n) time, worst case O
: (n^2) time, and O(n) additional space.
: 2) Event the directed graph has been built, it still need O(n) time, however
: , we already have O(n) time and O(1) space solution......
|
|
