在dermstore买的backorder的东西什么时候能发货# Fashion - 美丽时尚
l*1
1 楼
假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
并且满足word1和word2没有common letter.
并且满足word1和word2没有common letter.
l*y
2 楼
oct14 买的怎么还没发货
是不是要等很久？
是不是要等很久？
h*a
3 楼
没有 common letter比较麻烦
A*c
4 楼
先把所有的单词排序得出anagram，因为单词不长，可以算constant，这步O(n)
然后再比较common letter是不是会好点，可以early stop。这步有没有比暴力更好的
方法？
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
然后再比较common letter是不是会好点，可以early stop。这步有没有比暴力更好的
方法？
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
f*e
5 楼
用map
每个string用一个整数表示, 然后第二个表示max length。
判断两个string 是否相交，就为 i & j == 0.
在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
【在 A*********c 的大作中提到】
: 先把所有的单词排序得出anagram，因为单词不长，可以算constant，这步O(n)
: 然后再比较common letter是不是会好点，可以early stop。这步有没有比暴力更好的
: 方法？
每个string用一个整数表示, 然后第二个表示max length。
判断两个string 是否相交，就为 i & j == 0.
在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
【在 A*********c 的大作中提到】
: 先把所有的单词排序得出anagram，因为单词不长，可以算constant，这步O(n)
: 然后再比较common letter是不是会好点，可以early stop。这步有没有比暴力更好的
: 方法？
A*c
6 楼
嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
也可以接受。
感觉比anagram的想法好。
【在 f*****e 的大作中提到】
: 用map
: 每个string用一个整数表示, 然后第二个表示max length。
: 判断两个string 是否相交，就为 i & j == 0.
: 在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
也可以接受。
感觉比anagram的想法好。
【在 f*****e 的大作中提到】
: 用map
: 每个string用一个整数表示, 然后第二个表示max length。
: 判断两个string 是否相交，就为 i & j == 0.
: 在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
M*a
7 楼
然后可以按照长度排序，大的算到小的
m*g
8 楼
是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
?
?
M*a
9 楼
恩，这个好，基本O(N*average_length_of_string + 26*26)
number
【在 m**********g 的大作中提到】
: 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
: ?
number
【在 m**********g 的大作中提到】
: 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
: ?
c*p
10 楼
mark
b*e
11 楼
Not working, cannot guarantee disjoint.
【在 M*******a 的大作中提到】
: 恩，这个好，基本O(N*average_length_of_string + 26*26)
:
: number
【在 M*******a 的大作中提到】
: 恩，这个好，基本O(N*average_length_of_string + 26*26)
:
: number
b*e
12 楼
如果N巨大的话，做exponential set pre-computing吧。假设alphabet只有26个字母，
需要64M个4 bytes. 不算太离谱.
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
需要64M个4 bytes. 不算太离谱.
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
t*e
13 楼
这样找最长的words可以，但怎么保证没有common char?
number
【在 m**********g 的大作中提到】
: 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
: ?
number
【在 m**********g 的大作中提到】
: 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
: ?
l*1
14 楼
我用查表来算是否两个单词有common letter, 然后用O(N^2)来比较。估计
过不了电面
过不了电面
l*f
15 楼
trie?
w*0
16 楼
能否站看说说如何用一个整数表示一个string，如果string非常长，一个整数的长度一
定会够吗？谢谢。想了很久，没想明白。
【在 f*****e 的大作中提到】
: 用map
: 每个string用一个整数表示, 然后第二个表示max length。
: 判断两个string 是否相交，就为 i & j == 0.
: 在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
定会够吗？谢谢。想了很久，没想明白。
【在 f*****e 的大作中提到】
: 用map
: 每个string用一个整数表示, 然后第二个表示max length。
: 判断两个string 是否相交，就为 i & j == 0.
: 在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
w*0
17 楼
请教如何一个单词用4 byte表示？单词很长，也可以做到吗？谢谢
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
f*e
18 楼
就是用一个26bit的数字表示有没有相应的character。
【在 w********0 的大作中提到】
: 能否站看说说如何用一个整数表示一个string，如果string非常长，一个整数的长度一
: 定会够吗？谢谢。想了很久，没想明白。
【在 w********0 的大作中提到】
: 能否站看说说如何用一个整数表示一个string，如果string非常长，一个整数的长度一
: 定会够吗？谢谢。想了很久，没想明白。
P*d
19 楼
这个题是C特有的吗？strlen是求字符串长度吗？如果是java是不是直接遍历所有的元
素用word1.length()*word2.length()看最后哪个乘机大就行了是么？有没有共同元素
对求string长度有什么影响吗？
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
素用word1.length()*word2.length()看最后哪个乘机大就行了是么？有没有共同元素
对求string长度有什么影响吗？
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
t*8
20 楼
good
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
w*a
21 楼
后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
letter的。然后从root找，两条最长的到叶子节点的path就是了。
letter的。然后从root找，两条最长的到叶子节点的path就是了。
x*g
22 楼
“lca为root的两个叶节点就是没有common : letter的”
这个结论不对？只能判出无公共前缀，而不是无common letter.
common
【在 w****a 的大作中提到】
: 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
: letter的。然后从root找，两条最长的到叶子节点的path就是了。
这个结论不对？只能判出无公共前缀，而不是无common letter.
common
【在 w****a 的大作中提到】
: 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
: letter的。然后从root找，两条最长的到叶子节点的path就是了。
d*1
23 楼
先sort （word） 就好。
a*s
24 楼
假设有两个string，一个是abc，另一个是b.
你说的suffix tree应该怎样的？
common
【在 w****a 的大作中提到】
: 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
: letter的。然后从root找，两条最长的到叶子节点的path就是了。
你说的suffix tree应该怎样的？
common
【在 w****a 的大作中提到】
: 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
: letter的。然后从root找，两条最长的到叶子节点的path就是了。
d*1
25 楼
后缀树我没想明白，我是用trie做的。 l 是单词长度。
假如每个单词都排序完毕（O(n * l(lg l))，应该是O(n)的复杂度。
（就是一个单词里，有重复的时候，需要另外处理）
例如 输入是 bbbc, 和bbc 就要另外加东西标识出来。
假如每个单词都排序完毕（O(n * l(lg l))，应该是O(n)的复杂度。
（就是一个单词里，有重复的时候，需要另外处理）
例如 输入是 bbbc, 和bbc 就要另外加东西标识出来。
x*6
26 楼
后缀树理论建造需要n，再遍历所有internal node，每个internal node应该包含所有
经过这个node的string的信息，这样就能找到所有有common letter的string了。
经过这个node的string的信息，这样就能找到所有有common letter的string了。
x*g
27 楼
需要的是“没有common letter”。
无论字典树或者后缀树对于判定找出无common letter并不优。
将原来的s1....sn用26bit法转化成
A1.....An
对应的最大长度为： V1.....Vn
有两个好处：
1：判定无common letter即为：Ai & Aj == 0;
2：相同bit表示的不同字符串得到压缩，只需要记下长度最长的。
完了按Vn长度排序 N*Log(N)
V'n........V'1
A'n........A'1
从大到小搜索，如果Ai & Aj==0的话，L=V[i]*V[j].
那么大的那个下标就收缩到了k,V[k]>sqrt(L).
整体区间收缩到[l,r]满足
V[i]>V[l]
V[r]>V[j]
平均复杂度能N*Log(N)? ,最差当然还是N^2.
i =0;
j = n;
maxLen = 0;
highLen = INT_MAX;
lowLen = INT_MIN;
while(V[i]>sqrt(maxLen) && (i
if(V[i] < highLen)
{
for(int k=i+1;klowLen;k++)
{
if(A[i] & A[k]==0)
{
maxLen=max(maxLen,V[i]*V[k]);
lowLen = V[k];
highLen =V[i];
j=k-1;
break;
}
}
}
i++;
}
【在 x*******6 的大作中提到】
: 后缀树理论建造需要n，再遍历所有internal node，每个internal node应该包含所有
: 经过这个node的string的信息，这样就能找到所有有common letter的string了。
无论字典树或者后缀树对于判定找出无common letter并不优。
将原来的s1....sn用26bit法转化成
A1.....An
对应的最大长度为： V1.....Vn
有两个好处：
1：判定无common letter即为：Ai & Aj == 0;
2：相同bit表示的不同字符串得到压缩，只需要记下长度最长的。
完了按Vn长度排序 N*Log(N)
V'n........V'1
A'n........A'1
从大到小搜索，如果Ai & Aj==0的话，L=V[i]*V[j].
那么大的那个下标就收缩到了k,V[k]>sqrt(L).
整体区间收缩到[l,r]满足
V[i]>V[l]
V[r]>V[j]
平均复杂度能N*Log(N)? ,最差当然还是N^2.
i =0;
j = n;
maxLen = 0;
highLen = INT_MAX;
lowLen = INT_MIN;
while(V[i]>sqrt(maxLen) && (i
if(V[i] < highLen)
{
for(int k=i+1;k
{
if(A[i] & A[k]==0)
{
maxLen=max(maxLen,V[i]*V[k]);
lowLen = V[k];
highLen =V[i];
j=k-1;
break;
}
}
}
i++;
}
【在 x*******6 的大作中提到】
: 后缀树理论建造需要n，再遍历所有internal node，每个internal node应该包含所有
: 经过这个node的string的信息，这样就能找到所有有common letter的string了。
g*u
28 楼
这个现在比较直观
还有其他方法吗？
主要是 见完 最后找 product 还是个 N^2复杂度啊 这块能快吗？
大数据是不是就不行了 我觉得
因为这个题目肯定是面向大数据说的 小数据没意义 对吧
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
还有其他方法吗？
主要是 见完 最后找 product 还是个 N^2复杂度啊 这块能快吗？
大数据是不是就不行了 我觉得
因为这个题目肯定是面向大数据说的 小数据没意义 对吧
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
相关阅读