n***a
发帖数: 222 | 1 一个密码锁四位，可以用一个长string,来每四个
每四个读来试密码，怎么设计这个长string用尽可能少的digits来试出0000-9999这一
万种可能。Hamilton回路问题，NP, dfs+recursion，Wikipedia上有代码。但是也有别
的方法。
没有找到详细的讨论。。。求解 | f*******t
发帖数: 7549 | 2 每四个数字试一次，难道string不是固定40000个digit长？ | n***a
发帖数: 222 | 3 不是哦
比如10002 就可以代表1000和0002两种密码
【在 f*******t 的大作中提到】
: 每四个数字试一次，难道string不是固定40000个digit长？
| e********2
发帖数: 495 | 4 Leetcode都没做好，还出来问。
【在 n***a 的大作中提到】
: 一个密码锁四位，可以用一个长string,来每四个
: 每四个读来试密码，怎么设计这个长string用尽可能少的digits来试出0000-9999这一
: 万种可能。Hamilton回路问题，NP, dfs+recursion，Wikipedia上有代码。但是也有别
: 的方法。
: 没有找到详细的讨论。。。求解
| j**********3
发帖数: 3211 | | n***a
发帖数: 222 | 6 请问是leetcode哪题？
【在 e********2 的大作中提到】
: Leetcode都没做好，还出来问。
| c******w
发帖数: 1108 | 7 定义1000个node的有向图，每个node代表三位数字。每个node有10条outgoing edge，
对应0-9。每个node加上它的一条outgoing edge代表一组四位密码。
题目的最优解就是能遍历该有向图所有*edge*的最短的path。实际上就是要解这个图上的
chinese postman problem。
https://simple.m.wikipedia.org/wiki/Chinese_postman_problem
因为该有向图里每个node的in-degree和out-degree都等于10，其最优解为Eulerian
circuit ：visits every edge exactly once。可以在O（|E|）内找到。 | w*****n
发帖数: 98 | 8 De Bruijn sequence
【在 n***a 的大作中提到】
: 一个密码锁四位，可以用一个长string,来每四个
: 每四个读来试密码，怎么设计这个长string用尽可能少的digits来试出0000-9999这一
: 万种可能。Hamilton回路问题，NP, dfs+recursion，Wikipedia上有代码。但是也有别
: 的方法。
: 没有找到详细的讨论。。。求解
| l*3
发帖数: 2279 | 9 此题可以不用哈密顿回路做。考虑欧拉回路即可。
首先说明一下，这个string的长度就是10003，也就是说每连续4个都是互不相同的4位
数，不会有浪费
构建方法就是：
考虑一个有向图，每个node是一个三位数，edge是四位数，node和node的连接关系是这
样的，我举个例子：
node v = (a, b, c)
其中 0 \le a, b, c \le 9
从这个node出发的edge有:
(a, b, c, 0), 连到 (b, c, 0)
(a, b, c, 1), 连到 (b, c, 1)
....
(a, b, c, 9), 连到 (b, c, 9)
这样每个node都有10个edge-in 10个 edge-out，全图是可以欧拉回路遍历的，遍历走
过的所有边就是你要的sequence | l*3
发帖数: 2279 | 10 另外一个方法是 De Bruijn sequence
不过这个方法用到一些数学知识，不如我上面说的欧拉回路那个那么好理解。我也至今
没有看懂细节。
De Bruijn sequence 是O(n) 的算法。
上面的欧拉回路做不到 O(n)， 不过也是多项式的，对于这个问题来说，我觉得欧拉回
路的算法已经够巧妙了。 |
|
