w******n
发帖数: 61 | 1 给一个string的dictionary。求所有不share char的string pair中长度乘积最大的。
比如给了 cat dog map fast所求pair就是 (dog, fast) 输出12.
follow up： 求所有只share一个char的string pair中长度乘积最大的。
好像以前在本版见过这个题找不到链接了。。。 |
s****a
发帖数: 794 | |
m*****n
发帖数: 2152 | 3 按长度从大到小排序，然后，一个个试过去？
def max_product(A):
A.sort(key=len, reverse=True)
result = 0
for i in range(len(A)):
for j in range(i+1, len(A)):
if result < len(A[i])*len(A[j]):
if not any(c for c in A[i] if c in A[j]):
result = len(A[i])*len(A[j])
else: break
return result
follow up, 就改一行，
if not any(c for c in A[i] if c in A[j]):
改成
if len(list(c for c in A[i] if c in A[j]))==1:
【在 w******n 的大作中提到】
: 给一个string的dictionary。求所有不share char的string pair中长度乘积最大的。
: 比如给了 cat dog map fast所求pair就是 (dog, fast) 输出12.
: follow up： 求所有只share一个char的string pair中长度乘积最大的。
: 好像以前在本版见过这个题找不到链接了。。。
|
x*******6
发帖数: 262 | |
f*********5
发帖数: 1237 | 5 你这样暴力解法就不用排序了吧
[在 maxthon (JobHunting) 的大作中提到：]
：按长度从大到小排序，然后，一个个试过去？
：
：........... |
M**********7
发帖数: 378 | 6 这里对第一问讨论比较详细了
http://www.mitbbs.com/article_t/JobHunting/32868775.html
【在 w******n 的大作中提到】
: 给一个string的dictionary。求所有不share char的string pair中长度乘积最大的。
: 比如给了 cat dog map fast所求pair就是 (dog, fast) 输出12.
: follow up： 求所有只share一个char的string pair中长度乘积最大的。
: 好像以前在本版见过这个题找不到链接了。。。
|
m*****n
发帖数: 2152 | 7 这个方法，用在第二问就完蛋了。
【在 M**********7 的大作中提到】
: 这里对第一问讨论比较详细了
: http://www.mitbbs.com/article_t/JobHunting/32868775.html
|
w******n
发帖数: 61 | 8 谢谢啦。就是这个帖子。当时懒了没看之后就找不到了。。。
【在 M**********7 的大作中提到】
: 这里对第一问讨论比较详细了
: http://www.mitbbs.com/article_t/JobHunting/32868775.html
|
M**********7
发帖数: 378 | 9 不客气。
请问follow up是至多一个重复还是恰好一个重复?
【在 w******n 的大作中提到】
: 谢谢啦。就是这个帖子。当时懒了没看之后就找不到了。。。
|
M**********7
发帖数: 378 | 10 嗯， 可以想一下优化方法。 假设是要求有且仅有一个字符重复（该字符可以重复多次
）。
感觉第一步的变成字符集的方法还是会有帮助。这样再暴力也是(2^|a|)^2 = 2^(|a|+1
)。
第二步可以对每个字符重复，把含该字符的字符集分组，之后去掉该字符，在组内使用
原方法。
每个字符处理的字符集会有重复，复杂度会提高，但是不会太变态。
每次的集合数是 2^(|a|-1)，这样要做|a|次。
要求完全不重复的时候是2^|a|个集合，做一次。
所以比完全不重复提高了|a|/2的复杂度。
【在 m*****n 的大作中提到】
: 这个方法，用在第二问就完蛋了。
|
w******n
发帖数: 61 | 11 我看的描述是恰好一个重复
【在 M**********7 的大作中提到】
: 不客气。
: 请问follow up是至多一个重复还是恰好一个重复?
|
M**********7
发帖数: 378 | 12 这样啊，谢谢。
【在 w******n 的大作中提到】
: 我看的描述是恰好一个重复
|
