y*******o
发帖数: 6632 | 1 1 loop method:
class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n<=1){
return 0;
}
int iend=A[0];
int stepCount=1;
int nextEnd=A[0];
int i=1;
while(i
if(iend
return -1;
}
while(i<=iend){
if(nextEnd
nextEnd=i+A[i];
}
++i;
}
stepCount++;
iend=nextEnd;
}
return stepCount;
}
};
应该比下面的greedy好，因为只有一次遍历
greedy?
int jump(int A[], int n) {
int hops = 0;
int end = n-1;
while(end)
{
for(int i = 0; i <= end; i++)
{
if((A[i]+i)>=end)
{
hops++;
end = i;
}
}
}
return hops;
} |
j********x
发帖数: 2330 | 2 int jump_gameII(const std::vector& input) {
int cur = 0;
int step = 0;
int max = 0;
for (int i = 0; i < input.size(); ++i) {
if (i > cur && i <= max) {
++step;
cur = max;
} else if (i > max) {
return -1; // cannot reach i;
}
max = std::max(max, i + input[i]);
}
return step;
} |
c****7
发帖数: 4192 | 3 public class Solution {
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;j
if(A[j]+j>=i){
step++;
i=j;
break;
}
}
}
return step;
}
} |
n*******w
发帖数: 687 | 4 换个方向DP更好
P[i] = 1 + min { P[i+j] }
0
给个python的
arr = [2, 2, 2, 100, 1, 1, 1]
len_arr = len(arr)
DP = [sys.maxsize] * len_arr
DP[len_arr-1] = 0
def JumpII(arr, len_arr, DP):
for i in range(len_arr - 2, -1, -1):
for j in range(1, arr[i]+1):
tmp = 1
if i+j+1 < len_arr:
tmp += DP[i+j]
DP[i] = min(DP[i], tmp)
return DP[0]
print(JumpII(arr, len_arr, DP))
【在 c****7 的大作中提到】
: public class Solution {
: public int jump(int[] A) {
: int i=A.length-1;
: int step=0;
: while(i>0){
: for(int j=0;j: if(A[j]+j>=i){
: step++;
: i=j;
: break;
|
c****7
发帖数: 4192 | 5 正方向dp大数据超时了～～
【在 n*******w 的大作中提到】
: 换个方向DP更好
: P[i] = 1 + min { P[i+j] }
: 0: 给个python的
: arr = [2, 2, 2, 100, 1, 1, 1]
: len_arr = len(arr)
: DP = [sys.maxsize] * len_arr
: DP[len_arr-1] = 0
: def JumpII(arr, len_arr, DP):
: for i in range(len_arr - 2, -1, -1):
|
N*D
发帖数: 3641 | 6 大牛，DP玩得这么熟啊
【在 c****7 的大作中提到】
: 正方向dp大数据超时了～～
|
n*******w
发帖数: 687 | 7 多谢testing啊。想了想，应该是数组里边存在很大的数。
可以优化这一行，for j in range(1, arr[i]+1):
改成
for j in range(1, min(arr[i], len_arr - i -1)+1):
这样算感觉不会比你那个方向差才对。
请问数据是哪的，我也试试。
【在 c****7 的大作中提到】
: 正方向dp大数据超时了～～
|
c****7
发帖数: 4192 | 8 就是leetcode上的数据呀。也许我正向dp没有做对？
1):
【在 n*******w 的大作中提到】
: 多谢testing啊。想了想，应该是数组里边存在很大的数。
: 可以优化这一行，for j in range(1, arr[i]+1):
: 改成
: for j in range(1, min(arr[i], len_arr - i -1)+1):
: 这样算感觉不会比你那个方向差才对。
: 请问数据是哪的，我也试试。
|
c****7
发帖数: 4192 | 9 尼码，寒碜我是不是？
【在 N*D 的大作中提到】
: 大牛，DP玩得这么熟啊
|
c****7
发帖数: 4192 | 10 没有给你test。python不会。呵呵。
这是我理解的从前往后dp，大数据最后一个超时：
public int jump(int[] A) {
int[]dp=new int[A.length];
for(int i=1;i
for(int j=0;j
if(A[j]>=i-j&&(dp[i]==0||dp[i]>dp[j]+1)){
dp[i]=dp[j]+1;
}
}
}
return dp[A.length-1];
}
也许和你的不一样吧？
1):
【在 n*******w 的大作中提到】
: 多谢testing啊。想了想，应该是数组里边存在很大的数。
: 可以优化这一行，for j in range(1, arr[i]+1):
: 改成
: for j in range(1, min(arr[i], len_arr - i -1)+1):
: 这样算感觉不会比你那个方向差才对。
: 请问数据是哪的，我也试试。
|
c****7
发帖数: 4192 | 11 再来一个从前往后greedy的：
public int jump(int[] A) {
int min=0,max=0;
int newmax=0;
int jump=0;
while(newmax
jump++;
for(int i=min;i<=max;i++){
if(A[i]+i>=newmax)newmax=A[i]+i;
}
min=max+1;
max=newmax;
}
return jump;
} |
t****a
发帖数: 1212 | 12 楼主能贴出个大数据case来么，有多大？
下面的dp能解到500个长
(let [a (vec (apply concat (repeat 100 [2 3 1 4 4])))]
(def jump
(memoize
(fn [n]
(if (zero? n)
0
(let [ix (for [i (range n)
:when (<= n (+ i (get a i)))]
i)
m-set (map inc (remove nil? (map jump ix)))
m (if (empty? m-set)
nil
(apply min m-set))]
m)))))
(jump (dec (count a)))) |
n*******w
发帖数: 687 | 13 最大的case是range（25000, 0，-1），就是25000 ~ 1
其实应该包含另一种极端情况，就是25000个元素全是1
比较了两个方向的DP，发现了一点有意思的地方。
DP的方向是可能影响复杂度的。
方法1
如果递归式从后往前写，在 i 位置前面顺序判断任意一个位置能不能到i
那么如果数组里边的数字都很大，甚至达到O(n)的话，复杂度是O(n)
如果数组里边数字都很小，比如全是1，那么复杂度变成O(n^2)
方法2
递归式从前往后写，在i位置判断i往后能达到的任意一个位置。
复杂度刚好相反。
做了一些testing，假设数组大小n=10000
数组里边元素全是k，哪个更快，时间单位是ms，那个true表示两行种方法结果相同
方法2 方法1
k= 1 True 34.02304649353027 6190.130949020386
k= 8 True 43.0300235748291 773.5168933868408
k= 15 True 71.04706764221191 411.27490997314453
k= 22 True 98.0679988861084 277.18400955200195
k= 29 True 123.08311462402344 212.1419906616211
k= 36 True 149.09791946411133 170.11404037475586
k= 43 True 167.1130657196045 141.09301567077637
大概k=40的时候，两个方向的运行时间差不多。
如果理论上计算，
n* （n/k）/2 = nk
k0 = sqrt(n/2)
k>k0的时候从后往前快，否则从前往后快。
【在 t****a 的大作中提到】
: 楼主能贴出个大数据case来么，有多大？
: 下面的dp能解到500个长
: (let [a (vec (apply concat (repeat 100 [2 3 1 4 4])))]
: (def jump
: (memoize
: (fn [n]
: (if (zero? n)
: 0
: (let [ix (for [i (range n)
: :when (<= n (+ i (get a i)))]
|
