a*u
2 楼
难
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
f*y
3 楼
怎么做，完全不会
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
j*g
4 楼
这个答案难道不是 1121 ?
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
f*y
5 楼
啊，对，看来人脑做是不太靠谱
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
s*s
6 楼
N个字符串是相同长度？
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
l*i
7 楼
you want hamitonian path, not eulerian path, shortest superstring is NP-hard
a*m
8 楼
难。。。。
b*e
9 楼
这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
a*m
10 楼
旅行商是np hard
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
相关阅读
Lyft发布第一份员工多样性报告 (转载)有愿意给这家中国人公司干活的吗？要求也忒高了sign on bonus一般能赖吗免费提供数据分析方面的职业咨询和简历review亚麻的hr真是搞笑。。。。amazon 要90亿收购slackData Scientist 加州毁约有什么后果？背景调查有discrepancy一般怎么办？在职怎么面多个？有在西雅图Infosys工作/工作过的前辈吗？Data Scientist 加州请问onsite前两天又加一轮电话面试是什么情况最近绿卡广告职位多起来了？uber面试要刷题么？Uber八成要内部调整了Uber创始人卡兰尼克辞去CEO职务[bssd]上天快给牛肉姐一个uber offer 吧雅虎要雷2千人 (转载)Hiring in northern NJ. If interested, contact me via mitbbs. Thanks.