不做死就不会死(多gif) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

不做死就不会死(多gif)

不做死就不会死(多gif)# Joke - 肚皮舞运动

A*t2013-10-17 07:10

1 楼

算法一：DFS，当然aaaaaaaaaaaaaaaa就超时了。
算法二：DP, O(n^3), dp[i][len]纪录,每次查找O(n)。
算法三：DP, O(n^2), Java用HashSet，C++用unordered_set，理论上每次query是O(1)。
20行就写完了。
那么有没有小于这个的算法呢？比如严格o(n^2)，O(nlogn)的.

p*g2013-10-17 07:10

2 楼

s*x2013-10-17 07:10

3 楼

can you post your code for n^2?

t*g2013-10-17 07:10

4 楼

最后那个真死了？

h*n2013-10-17 07:10

5 楼

bool wordBreak(string s, unordered_set &dict) {
int N = s.size();
vector dp(N+1, false);
dp[0] = true;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= i; j++) {
if (dp[i-j] && (dict.find(s.substr(i-j, j)) != dict.end())) {
dp[i] = true;
break;
}
}
return dp[N];
}

c*n2013-10-17 07:10

6 楼

默片时代的产物
应该没死不过那个年代不会蒙太奇不会摆角度
搞的那些动作成龙看了怕都要尿

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

: 最后那个真死了？

p*e2013-10-17 07:10

7 楼

就我一外行来看，你这个不是dp呀。这个不就是O(n^2)的暴力解法嘛。不能因为变量名
字是dp,就叫dp算法吧。

><= i;="" j++)="" {="" :="" if="" (dp[i-j]="" &&="" (dict.find(s.substr(
i-j,="" j))="" !="dict.end()))" {="" :="" dp[i]="true;" :="" break;="" :=""
}="" :="" ...................="">

【在 h****n 的大作中提到】

: bool wordBreak(string s, unordered_set &dict) {
: int N = s.size();
: vector dp(N+1, false);
: dp[0] = true;
: for (int i = 1; i <= N; i++)
: for (int j = 1; j <= i; j++) {
: if (dp[i-j] && (dict.find(s.substr(i-j, j)) != dict.end())) {
: dp[i] = true;
: break;
: }

d*l2013-10-17 07:10

8 楼

自行车上栏杆那个每次看了都蛋疼，虽然看过好多遍了

n*e2013-10-17 07:10

9 楼

多么漂亮的前缀字符串 DP 被你说成了暴力解法。。。

substr(
"

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

: 就我一外行来看，你这个不是dp呀。这个不就是O(n^2)的暴力解法嘛。不能因为变量名
: 字是dp,就叫dp算法吧。
:
: ><= i;="" j++)="" {="" :="" if="" (dp[i-j]="" &&="" (dict.find(s.substr(
: i-j,="" j))="" !="dict.end()))" {="" :="" dp[i]="true;" :="" break;="" :=""
: }="" :="" ...................="">

G*Y2013-10-17 07:10

10 楼

第一个为啥会爆炸呀？没看懂

【在 d*l 的大作中提到】

: 自行车上栏杆那个每次看了都蛋疼，虽然看过好多遍了

A*t2013-10-17 07:10

11 楼

暴力的是dfs。这个算是DP了，每个位置搜到都记录下来。

substr(
"

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

d*l2013-10-17 07:10

12 楼

短路了吧

【在 G**Y 的大作中提到】

: 第一个为啥会爆炸呀？没看懂

s*d2013-10-17 07:10

13 楼

bool wordBreak(string s, unordered_set &dict) {
vector f(s.size() + 1, false);
f[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
break;
}
}
}
return f[s.size()];
}

w*t2013-10-17 07:10

14 楼

各种蛋疼, 尤其是倒数第四个, 太坏了.

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

s*x2013-10-17 07:10

15 楼

这道题总感觉应该把字典先建成trie.
网上搜索到的解法都是要试试几乎所有可能的子串，效率太差了。
至少应该先求出字典里最长单词的长度 I think.

A*k2013-10-17 07:10

16 楼

谁说那个年代不会蒙太奇，爱森斯坦在拍战舰波将金号的时候就用蒙太奇了

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

: 默片时代的产物
: 应该没死不过那个年代不会蒙太奇不会摆角度
: 搞的那些动作成龙看了怕都要尿

w*g2013-10-17 07:10

17 楼

把字典先建成trie有啥用？

H*g2013-10-17 07:10

18 楼

扔石头的那个，后面的人也可能被砸断手

p*e2013-10-17 07:10

19 楼

我想错了，这个是dp. 而且复杂度是O(n^2 * s), s是字典长度。要想进一步优化，肯
定需要trie了。复杂度可以是O(n*s) 吧。

【在 A*********t 的大作中提到】

: 暴力的是dfs。这个算是DP了，每个位置搜到都记录下来。
:
: substr(
: "

l*t2013-10-17 07:10

20 楼

为啥不能砸扁脑袋？

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

: 扔石头的那个，后面的人也可能被砸断手

s*x2013-10-17 07:10

21 楼

有了trie，复杂度应该是O(nW), where W is average of word length in the
dictionary.
假如我们忽略trie 的构建成本。

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

: 我想错了，这个是dp. 而且复杂度是O(n^2 * s), s是字典长度。要想进一步优化，肯
: 定需要trie了。复杂度可以是O(n*s) 吧。

w*g2013-10-17 07:10

22 楼

为什么有了trie，复杂度应该是O(nW)？
能不能贴个pseudo code?

s*x2013-10-17 07:10

23 楼

有了trie，checking a substring is a prefix of any words become very easy,
just traverse the path in the trie.
for example， if no word begins with abc, you do not need to check if abcd，
abcde is in the dictionary or not.
when trie is not used, you have to lookup the dictionary for all substrings
starting a given position.
可以看看boggle puzzle 那题，那题不用trie 好像没法弄。

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

: 为什么有了trie，复杂度应该是O(nW)？
: 能不能贴个pseudo code?