情人节送老婆的花 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

情人节送老婆的花

情人节送老婆的花# Joke - 肚皮舞运动

g*m2012-02-16 08:02

1 楼

在leetcode上做了几道DP的题目，用的是很标准的二维数组。judge small都过了，
judge large的时候说memory limit exceed。（用动态数组，如果用静态，显示
runtime error）。试着把数组砍掉一半变成三角形，还是超。
有什么好办法么？可以想到的是，动态数组一边算一边删不用的空间，但code很难写啊
，几乎肯定得出错...

z*r2012-02-16 08:02

2 楼

PERM audit的business necessity justification怎么写？PERM要求是MS+6个月经验。
律师找老板要，老板不太会写，于是问我，可是我也不太清楚……不知道有没有模板或
者是标准的写法？
另外，这个文件是不是对于PERM audit的通过与否非常关键？
多谢！

w*D2012-02-16 08:02

3 楼

请问这个东西好用吗？自己可以装吗还是必须请人来安装呢？
谢谢

r*e2012-02-16 08:02

4 楼

情人节送老婆的花.jpg

i*e2012-02-16 08:02

5 楼

是哪一道题呢？
我帮你看看吧。
你可以 return 空答案，然后看 large input 的testcase最大size，然后 allocate
那个size应该就好了。
面试时不用 dynamic alloc，assume input 不会超过这个size就好了。

r*x2012-02-16 08:02

6 楼

this is awesome.

g*m2012-02-16 08:02

7 楼

Jump game II 和 Largest Rectangle in Histogram。
我可以看到fail的test case，就是一个size特别大的数组（里面的元素并不大）。我
就是根据input数组长度定义二维数组的，（三角形，砍了一半已经）
int **res;
res = new int *[n+1];
for (int i = 0; i < n; i++)
res[i] = new int[n+1-i];
剩下的为空，都是memory limit exceed。
这个input size感觉是分配n的空间不会超过，n^2就不行了。

【在 i**********e 的大作中提到】

: 是哪一道题呢？
: 我帮你看看吧。
: 你可以 return 空答案，然后看 large input 的testcase最大size，然后 allocate
: 那个size应该就好了。
: 面试时不用 dynamic alloc，assume input 不会超过这个size就好了。

e*e2012-02-16 08:02

8 楼

EDIBLE ARRANGEMENT还有水果做成的花。这个是让老婆在家做饭LOL

l*82012-02-16 08:02

9 楼

Jump game II 不需要二维数组吧。

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

: Jump game II 和 Largest Rectangle in Histogram。
: 我可以看到fail的test case，就是一个size特别大的数组（里面的元素并不大）。我
: 就是根据input数组长度定义二维数组的，（三角形，砍了一半已经）
: int **res;
: res = new int *[n+1];
: for (int i = 0; i < n; i++)
: res[i] = new int[n+1-i];
: 剩下的为空，都是memory limit exceed。
: 这个input size感觉是分配n的空间不会超过，n^2就不行了。

w*l2012-02-16 08:02

10 楼

惊艳了。

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

: 情人节送老婆的花.jpg

i*e2012-02-16 08:02

11 楼

对，因为 n 最大可以大到 25000.n^2 空间肯定不行。

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

a*e2012-02-16 08:02

12 楼

亮点是热狗？

g*m2012-02-16 08:02

13 楼

hmm...
所以有什么办法能把DP的空间降到n^2以下呢？除了一边算一边动态释放空间。

【在 i**********e 的大作中提到】

: 对，因为 n 最大可以大到 25000.n^2 空间肯定不行。

g*g2012-02-16 08:02

14 楼

胡萝卜

【在 a*******e 的大作中提到】

: 亮点是热狗？

l*82012-02-16 08:02

15 楼

这道题目是求图上两点间最近距离的特例，可以用Dijkstra算法的简化版.

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

: hmm...
: 所以有什么办法能把DP的空间降到n^2以下呢？除了一边算一边动态释放空间。

a*e2012-02-16 08:02

16 楼

哦，更硬一点

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

: 胡萝卜

i*e2012-02-16 08:02

17 楼

jump game 可以用 greedy，可以考古本版，火鸡给过很好的解法。
histogram 那题用 cache 来做的方法需要 O(n^2) 空间，过不了large testcase。
large testcase需要最优解法，可以参考网上给的 stack 解答。
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.htm

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

: hmm...
: 所以有什么办法能把DP的空间降到n^2以下呢？除了一边算一边动态释放空间。