📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 6060| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

欧拉回路or哈密顿回路

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
看到一道google面经题,感觉很难啊,求思路,听我学长说好像可以用欧拉或者哈密顿回路做出来……但是,并不懂……
一堆密码箱,每个密码都是四位0-9之间,算一个暴力破解序列,包含所有可能的四位序列,让这个序列尽量短

上一篇:大家来刷题:求问一道coding题,最近被问到了...
下一篇:再开一帖暴力刷题
🔗
stellari 2016-1-15 00:16:50 | 只看该作者
全局:
你说的这个叫做de Bruijn序列
https://en.wikipedia.org/wiki/De_Bruijn_sequence

解法是,在一个4维的de Bruijn图上,找出Hamilton回路(或者在一个3维的de Bruijn图上,找出欧拉回路)。所以你学长说的是对的。这些内容上面那个链接中都有,不妨一看。总之我觉得现场要在不了解这些知识的情况下解出还是太困难了。
回复

使用道具 举报

🔗
 楼主| 神罗天征 2016-1-15 01:18:08 | 只看该作者
全局:
stellari 发表于 2016-1-15 00:16
你说的这个叫做de Bruijn序列
https://en.wikipedia.org/wiki/De_Bruijn_sequence

太厉害了……这种题遇到必跪啊
回复

使用道具 举报

🔗
 楼主| 神罗天征 2016-1-15 02:13:43 | 只看该作者
全局:
  1. public String generateDeBruijnSequence(int k, int n) {
  2.                 StringBuilder sequence = new StringBuilder();
  3.                 generateLyndonWords(1, 1, k, new int[n+1], sequence);
  4.                 return sequence.toString();
  5.         }

  6.         private void generateLyndonWords(int t, int p, int k, int[] a, StringBuilder sequence) {
  7.                 if (t > a.length-1) {
  8.                         if((a.length-1)%p==0) {
  9.                                 for(int i = 1; i < p+1;i++) {
  10.                                         sequence.append(a[i]);
  11.                                 }
  12.                         }
  13.                 } else {
  14.                         a[t] = a[t-p];
  15.                         generateLyndonWords(t+1,p, k, a, sequence);
  16.                         for(int j=a[t-p]+1; j<=k-1; j++) {
  17.                                 a[t] = j;
  18.                                 generateLyndonWords(t+1,t, k, a, sequence);
  19.                         }
  20.                 }
  21.         }
复制代码


Google找到的代码,大家可以参考参考,不过,看不懂这是思路
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表