大卡车侧翻压扁小车 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

大卡车侧翻压扁小车

大卡车侧翻压扁小车# Joke - 肚皮舞运动

y*o2012-12-27 08:12

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(iif(iendreturn -1;
}
while(i<=iend){
if(nextEndnextEnd=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;
}

L*g2012-12-27 08:12

2 楼

会不会是假货或陈货?
EL beautiful Love 香水专卖柜台买要48刀. 而它是 35 刀,有买过的说说看.

x*o2012-12-27 08:12

3 楼

j*x2012-12-27 08:12

4 楼

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;
}

l*82012-12-27 08:12

5 楼

有风险，大多是tester吧。。

g*r2012-12-27 08:12

6 楼

这就是奇瑞啊

【在 x****o 的大作中提到】

: h

c*72012-12-27 08:12

7 楼

public class Solution {
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;jif(A[j]+j>=i){
step++;
i=j;
break;
}
}
}
return step;
}
}

n*n2012-12-27 08:12

8 楼

不。我觉得amazon自家卖的比fragrancenet好。

r*e2012-12-27 08:12

9 楼

废品处理的办法

【在 x****o 的大作中提到】

: h

n*w2012-12-27 08:12

10 楼

换个方向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;

j*a2012-12-27 08:12

11 楼

嗯
仔细读介绍不过自己用一般也没事
【在 lolita88 (lolita) 的大作中提到: 】

f*y2012-12-27 08:12

12 楼

在国内见过原装帕萨特被载重车压成这样的，真不是质量问题，就是太重。
只有美国黄皮校车可以抗衡18轮

【在 g*r 的大作中提到】

: 这就是奇瑞啊

c*72012-12-27 08:12

13 楼

正方向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):

c*o2012-12-27 08:12

14 楼

人怎么样了

N*D2012-12-27 08:12

15 楼

大牛，DP玩得这么熟啊

【在 c****7 的大作中提到】

: 正方向dp大数据超时了～～

s*a2012-12-27 08:12

16 楼

very sad
not funny at all

【在 x****o 的大作中提到】

: h

n*w2012-12-27 08:12

17 楼

多谢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大数据超时了～～

b*n2012-12-27 08:12

18 楼

什么情况？竟然使出了武装平暴这一失传二十多年的神技！

【在 x****o 的大作中提到】

: h

c*72012-12-27 08:12

19 楼

就是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*72012-12-27 08:12

20 楼

尼码，寒碜我是不是？

【在 N*D 的大作中提到】

: 大牛，DP玩得这么熟啊

c*72012-12-27 08:12

21 楼

没有给你test。python不会。呵呵。
这是我理解的从前往后dp，大数据最后一个超时：
public int jump(int[] A) {
int[]dp=new int[A.length];
for(int i=1;ifor(int j=0;jif(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 的大作中提到】

c*72012-12-27 08:12

22 楼

再来一个从前往后greedy的：
public int jump(int[] A) {
int min=0,max=0;
int newmax=0;
int jump=0;
while(newmaxjump++;
for(int i=min;i<=max;i++){
if(A[i]+i>=newmax)newmax=A[i]+i;
}
min=max+1;
max=newmax;
}
return jump;
}

t*a2012-12-27 08:12

23 楼

楼主能贴出个大数据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*w2012-12-27 08:12

24 楼

最大的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)))]