s****n
发帖数: 70 | 1 面的时候被这个题难住了，题目大概是有一个 4位数长的密码，每一位From 0 - 9. 让
你给出一个最短的string，使它的substring包含所有可能的combination.
举例： 123456 包含 1234， 2345，3456三个组合。
求高手解答！ |
f********a
发帖数: 4239 | 2 什么叫combination？2563算不？2709算不？
【在 s****n 的大作中提到】
: 面的时候被这个题难住了，题目大概是有一个 4位数长的密码，每一位From 0 - 9. 让
: 你给出一个最短的string，使它的substring包含所有可能的combination.
: 举例： 123456 包含 1234， 2345，3456三个组合。
: 求高手解答！
|
M********5
发帖数: 715 | |
s****n
发帖数: 70 | 4 就是所有的组合，4位密码的组合共有10^4个
【在 s****n 的大作中提到】
: 面的时候被这个题难住了，题目大概是有一个 4位数长的密码，每一位From 0 - 9. 让
: 你给出一个最短的string，使它的substring包含所有可能的combination.
: 举例： 123456 包含 1234， 2345，3456三个组合。
: 求高手解答！
|
d****o
发帖数: 1055 | 5 重新定义一下输入和输出
【在 s****n 的大作中提到】
: 面的时候被这个题难住了，题目大概是有一个 4位数长的密码，每一位From 0 - 9. 让
: 你给出一个最短的string，使它的substring包含所有可能的combination.
: 举例： 123456 包含 1234， 2345，3456三个组合。
: 求高手解答！
|
M********5
发帖数: 715 | 6 我觉得你理解的substring是不是狭义的substring，1345应该也是substring
如果是我理解的这样的话，那么这个string是不是19位的。。。 |
l****c
发帖数: 782 | 7 如果说10^4个substring，包括它的最小string应该老大了吧。。。。 |
f*****e
发帖数: 2992 | 8 找一个eulerian path。balanced就guarantee了。
【在 s****n 的大作中提到】
: 面的时候被这个题难住了，题目大概是有一个 4位数长的密码，每一位From 0 - 9. 让
: 你给出一个最短的string，使它的substring包含所有可能的combination.
: 举例： 123456 包含 1234， 2345，3456三个组合。
: 求高手解答！
|
g*****g
发帖数: 34805 | 9 我来抛砖引玉，1万个combination。每个一个结点，
相邻做有向图，比如0000->0001->0015，求遍历途径
【在 s****n 的大作中提到】
: 面的时候被这个题难住了，题目大概是有一个 4位数长的密码，每一位From 0 - 9. 让
: 你给出一个最短的string，使它的substring包含所有可能的combination.
: 举例： 123456 包含 1234， 2345，3456三个组合。
: 求高手解答！
|
j*****o
发帖数: 394 | 10 每个NODE在尾数加0-9你是指
比如1234加一个7变成2347？
感觉不太对
因为1234后面要以接4开头,也可以投34开头的。。还有234开头的。。
【在 f*****e 的大作中提到】
: 找一个eulerian path。balanced就guarantee了。
|
|
|
g*****g
发帖数: 34805 | 11 1万个substring，最少也要10003个字符还能做出来。
如果能证明可以一次遍历，那就是10003。
除了0000，1111.。。。9999，都是10个入，10个出的边。
那几个是9个入，9各出。
【在 j*****o 的大作中提到】
: 每个NODE在尾数加0-9你是指
: 比如1234加一个7变成2347？
: 感觉不太对
: 因为1234后面要以接4开头,也可以投34开头的。。还有234开头的。。
|
s****n
发帖数: 70 | 12 我绝的Ls几位说的很有道理，应该可以转化为hamilton图的问题。 如果是NP-complete
的，我想他们大概是想要一个approximation algorithm, 不知道最好的approximation
ratio是多少 |
j*****o
发帖数: 394 | 13 这是电面题还是ONSITE啊。。。？
complete
approximation
【在 s****n 的大作中提到】
: 我绝的Ls几位说的很有道理，应该可以转化为hamilton图的问题。 如果是NP-complete
: 的，我想他们大概是想要一个approximation algorithm, 不知道最好的approximation
: ratio是多少
|
g*****g
发帖数: 34805 | 14 我估计你能转成hamilton图就差不多了。题并不是一定要答出来的，
看你的思维能力而已。
complete
approximation
【在 s****n 的大作中提到】
: 我绝的Ls几位说的很有道理，应该可以转化为hamilton图的问题。 如果是NP-complete
: 的，我想他们大概是想要一个approximation algorithm, 不知道最好的approximation
: ratio是多少
|
j*****o
发帖数: 394 | 15 赞神搜索能力。。。
膜拜学习去。。。
【在 f*****e 的大作中提到】
: 找一个eulerian path。balanced就guarantee了。
|
p*****2
发帖数: 21240 | 16 hamilton图是啥东西呀？一个月没做题，彻底out了。 |
