logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
广州華景里
avatar
广州華景里# Joke - 肚皮舞运动
h*n
1 楼
两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i(s1[i]-s2
[i])，怎么找距离最大的两个substring?
根据距离的定义，应该是找两个长度相同的substring
咋做，穷举？
还有一道
一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
这个也只能穷举吗？
avatar
x*o
2 楼
年度最爱情照片。没有拥抱，没有接吻，没有落日，没有沙滩，有的只不过是一个1米
多的座位，男人体贴地伸出手挡住妻子的座位让她安稳睡觉，男人的眼中满是血丝，脚
下是一包包的药，看得出男人很疲惫。如果一起甜蜜叫爱情，那么风雨同舟则是爱情的
真谛。
avatar
l*b
3 楼
sum 里要加绝对值不？
avatar
l*e
4 楼
赞
avatar
p*2
5 楼
能给几个例子吗？
avatar
h*n
6 楼
这个定义应该不要紧，你就当做是加绝对值吧

【在 l*******b 的大作中提到】
: sum 里要加绝对值不？
avatar
c*t
7 楼
嗯，我只会穷举了，不过第二题可以按长度从大到小先排序，穷举过程中可以早些
break or return

s2

【在 h****n 的大作中提到】
: 两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i(s1[i]-s2
: [i])，怎么找距离最大的两个substring?
: 根据距离的定义，应该是找两个长度相同的substring
: 咋做，穷举？
: 还有一道
: 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 这个也只能穷举吗？
avatar
h*n
8 楼
第一题吧
s1 aaaab s2 zzzzb
应该有两个结果 一个就是aaaab和zzzzb，还有一个就是aaaa和zzzz
第二题应该题意很清楚吧。？

【在 p*****2 的大作中提到】
: 能给几个例子吗？
avatar
p*2
9 楼
第二题可以用trie，这样可以skip掉有相同字符的单词。
avatar
p*2
10 楼
第一题BF是n^5吧？dp可以做到n^4,好一点。
avatar
b*m
11 楼

先build一个trie，然后找最大不同分支？

【在 p*****2 的大作中提到】
: 第一题BF是n^5吧？dp可以做到n^4,好一点。
avatar
c*t
12 楼
1*n+ 2^2*(n-1) + 3^2*(n-2) +...+ n^2*1 不是n^5吧,应该是n^3？

【在 p*****2 的大作中提到】
: 第一题BF是n^5吧？dp可以做到n^4,好一点。
avatar
c*t
13 楼
我怎么觉得是多个trie, 因为然后找不同trie间的结果？

【在 b***m 的大作中提到】
:
: 先build一个trie，然后找最大不同分支？
avatar
l*b
14 楼
n^2吧，如果有绝对值，那个子字符串必然是从母字符串的一头头开始的

【在 p*****2 的大作中提到】
: 第一题BF是n^5吧？dp可以做到n^4,好一点。
avatar
p*2
15 楼

先把每个单词都sort，然后一个trie就可以了。查的时候跳过已有的字符，另外只查比
自己小的，这样可以避免重复查询，A->B只查一次，不会查两次。

【在 c********t 的大作中提到】
: 我怎么觉得是多个trie, 因为然后找不同trie间的结果？
avatar
p*2
16 楼

n^3就可以求出来？
应该有n^2个substring吧？
然后两两组合就是n^4了。然后两两比较就是n^5了。这个算法有错吗？

【在 c********t 的大作中提到】
: 1*n+ 2^2*(n-1) + 3^2*(n-2) +...+ n^2*1 不是n^5吧,应该是n^3？
avatar
b*m
17 楼

嗯，一个trie肯定就够了。

【在 p*****2 的大作中提到】
:
: n^3就可以求出来？
: 应该有n^2个substring吧？
: 然后两两组合就是n^4了。然后两两比较就是n^5了。这个算法有错吗？
avatar
R*y
18 楼
第一题，假设两个string A.length()同的子串吧。

s2

【在 h****n 的大作中提到】
: 两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i(s1[i]-s2
: [i])，怎么找距离最大的两个substring?
: 根据距离的定义，应该是找两个长度相同的substring
: 咋做，穷举？
: 还有一道
: 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 这个也只能穷举吗？
avatar
h*n
19 楼
转换trie后是否等同于n叉树找两条最长的从root开始的path就行了？

【在 p*****2 的大作中提到】
:
: n^3就可以求出来？
: 应该有n^2个substring吧？
: 然后两两组合就是n^4了。然后两两比较就是n^5了。这个算法有错吗？
avatar
h*n
20 楼
根据定义应该是吧

【在 R********y 的大作中提到】
: 第一题，假设两个string A.length(): 同的子串吧。
:
: s2
avatar
b*m
21 楼
对的。

【在 h****n 的大作中提到】
: 转换trie后是否等同于n叉树找两条最长的从root开始的path就行了？
avatar
c*t
22 楼
有错啊，只要比较相同长度的啊

【在 p*****2 的大作中提到】
:
: n^3就可以求出来？
: 应该有n^2个substring吧？
: 然后两两组合就是n^4了。然后两两比较就是n^5了。这个算法有错吗？
avatar
e*l
23 楼
第一题： sum(a[i]-b[i]) = sum(a[i]) - sum(b[i])
所以至少有O(n^2)的解法：
定义 f(i,t) = s[i] + s[i+1] + ... + s[i+t-1]
for t = 1 to n/2

for i = 0 to n-t
f(i,t)=f(i,t-1)+s[i+t-1]
end
a = min (f(*,t))
b = max (f(*,t))
dis[t] = b - a
end

max(dis)就是答案
avatar
R*y
24 楼
用绝对值的话，你的等式不成立吧...

【在 e***l 的大作中提到】
: 第一题： sum(a[i]-b[i]) = sum(a[i]) - sum(b[i])
: 所以至少有O(n^2)的解法：
: 定义 f(i,t) = s[i] + s[i+1] + ... + s[i+t-1]
: for t = 1 to n/2
:
: for i = 0 to n-t
: f(i,t)=f(i,t-1)+s[i+t-1]
: end
: a = min (f(*,t))
: b = max (f(*,t))
avatar
l*b
25 楼
NO
a a z z
a b z
正解应该是 z z 对 a b

【在 h****n 的大作中提到】
: 根据定义应该是吧
avatar
R*y
26 楼
那穷举也只有O(mn)的复杂度啊。我觉得可以做到O(m+n)，用sliding window，细节得
再想想...

【在 h****n 的大作中提到】
: 根据定义应该是吧
avatar
R*y
27 楼
刚看到楼上说的是对的。短子串不一定两头都占，但至少占一头，所以复杂度不变，穷
举还是O(mn)。

【在 R********y 的大作中提到】
: 那穷举也只有O(mn)的复杂度啊。我觉得可以做到O(m+n)，用sliding window，细节得
: 再想想...
avatar
l*b
28 楼
对，加绝对值我只想到这样了。。。
不加绝对值，这个还不对，只想到了n^2 + O(n) space的做法
嗯，做DP不需要额外空间，n^2时间够了

【在 R********y 的大作中提到】
: 刚看到楼上说的是对的。短子串不一定两头都占，但至少占一头，所以复杂度不变，穷
: 举还是O(mn)。
avatar
p*2
29 楼

奥，没注意这个。那应该是n^4吧？
n/2*n/2*n/2, 考虑一半长度的时候比较就是n^3了。

【在 c********t 的大作中提到】
: 有错啊，只要比较相同长度的啊
avatar
p*2
30 楼

为什么至少占一头？
ab abcdab
不是应该返回中间的cd吗？

【在 R********y 的大作中提到】
: 刚看到楼上说的是对的。短子串不一定两头都占，但至少占一头，所以复杂度不变，穷
: 举还是O(mn)。
avatar
p*2
31 楼

这个不一定吧？
ab
aaaac
b和c也是一个解
你的意思是必有一个解的长度跟A相同吗？

【在 R********y 的大作中提到】
: 第一题，假设两个string A.length(): 同的子串吧。
:
: s2
avatar
p*2
32 楼

如果是这个规律的话BF是m*n, DP就是O(n)了吧？

【在 l*******b 的大作中提到】
: 对，加绝对值我只想到这样了。。。
: 不加绝对值，这个还不对，只想到了n^2 + O(n) space的做法
: 嗯，做DP不需要额外空间，n^2时间够了
avatar
c*t
33 楼
他是说短的那个string,至少占一头，我觉得好像是

【在 p*****2 的大作中提到】
:
: 如果是这个规律的话BF是m*n, DP就是O(n)了吧？
avatar
D*d
34 楼
第一题 DP
f(str1,str2) = max{f(str1-1,str2), f(str1,str2-1), g(str1-1,str2-1)+ str1[
end] - str2[end]},
where g(str1,str2) is the max distance of suffix.

s2

【在 h****n 的大作中提到】
: 两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i(s1[i]-s2
: [i])，怎么找距离最大的两个substring?
: 根据距离的定义，应该是找两个长度相同的substring
: 咋做，穷举？
: 还有一道
: 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 这个也只能穷举吗？
avatar
l*b
35 楼
这样的，加了绝对值。考虑对齐的字符串能不能延伸。因为延伸以后距离一定更大。所
以有三种情况
*******sddff********
kjhhg
sdj************
****kgc
*************ljgd
dssj************
如果要返回所有距离最大的，只要把这种里面两头相同的部分踢剃掉就好了。

【在 c********t 的大作中提到】
: 他是说短的那个string,至少占一头，我觉得好像是
avatar
w*o
36 楼
第一题看上去好像是连续子数组最大值的变种。
先计算一个二维数组d[][]，其中d[i][j] = s1[i] - s2[j]。然后把每个斜边作为一个
数组，比如d[0][0],d[1][1]...，或者d[0][1],d[1][2], d[2][3]....
对每个斜边求有最大值的连续子数组，或者最小负值。
O(n^2) + O(n^2)
avatar
l*b
37 楼
没必要都存起来，dp只读一遍数据。所以是O(1) space

【在 w***o 的大作中提到】
: 第一题看上去好像是连续子数组最大值的变种。
: 先计算一个二维数组d[][]，其中d[i][j] = s1[i] - s2[j]。然后把每个斜边作为一个
: 数组，比如d[0][0],d[1][1]...，或者d[0][1],d[1][2], d[2][3]....
: 对每个斜边求有最大值的连续子数组，或者最小负值。
: O(n^2) + O(n^2)
avatar
S*1
38 楼
I don't think so....
Let's use the trie on wiki for example: http://en.wikipedia.org/wiki/Trie
"ten" and "inn" are n叉树两条最长的从root开始的path, but they have same
character 'n'.

【在 b***m 的大作中提到】
: 对的。
avatar
w*o
39 楼
为什么短一定要占一头？
试试这个：
aezea
gag
答案当然是s1的z和s2的a。s2两头都不占。
avatar
l*b
40 楼
看sum 里加不加绝对值。不加的话是不一定。两个问题有些区别
ac
bb
距离为0,不太合理，哈哈

【在 w***o 的大作中提到】
: 为什么短一定要占一头？
: 试试这个：
: aezea
: gag
: 答案当然是s1的z和s2的a。s2两头都不占。
avatar
w*o
41 楼
对第一题的理解有点混乱，我想可能有三种情况：
1. dist = sum_i(s1[i] - s2[i]);
2. dist = sum_i(|s1[i] - s2[i]|);
3. dist = |sum_i(s1[i] - s2[i])|;
我觉得这题本意是要考第三种情况。
avatar
j*2
42 楼
如果是绝对值的话，那结果一定跟短的一个string等长。因为增加长度不会减少和。
如果两个string等长，那就无论如何一定是两个string本身啊。
如果是aaazaaa vs.abbb, 答案是zaaa和abbb。
比如aaazaaa vs. aaaabbb，答案即aaazaaa和aaazbbb。
所以只要拿短的对着长的一个一个扫就行了。time: O(n*m), space: O(1)

【在 h****n 的大作中提到】
: 这个定义应该不要紧，你就当做是加绝对值吧
avatar
q*m
43 楼
对于第一道题，如果是绝对值的和的话，那么这两个字符串不会在原来string 的中间
，只有一种情况，那就是一个字符串包含第一个字符，另外一个字符串包含最后一个字
符，这样的话就是线性了

s2

【在 h****n 的大作中提到】
: 两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i(s1[i]-s2
: [i])，怎么找距离最大的两个substring?
: 根据距离的定义，应该是找两个长度相同的substring
: 咋做，穷举？
: 还有一道
: 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 这个也只能穷举吗？
相关阅读
郑州土豪称愿花100万租女友过年【点赞有风险 下手需谨慎】快到期末考试了小弟你这么入戏啊原来如此， 转静芬的童年不一般经典的中英文自由转换，有不服的么？江苏两会午餐安排庆丰包子：和习近平吃的一样 (转载)攀房“裸佛”亮相济南似“佛跳墙”郭德纲在河内示威 (转载)吃饭了，吃饭了 (转载)Re: 狗不理包子降价50% 董事长称放下身段 (转载)意大利一名修女因胃痛就医 不料诞下婴儿 (转载)42岁老mm陪师妹去看电影，结果挨了她一个很响的嘴巴 ; (转载)惊人的爆发力印度狙击手我的家只有一个，那就是中国zt (转载)谁有这样的女同事可幸福死了。几个笑话 -- 奇淫合欢散
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。