一亩三分地

 找回密码 注册账号

扫描二维码登录本站


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 1371|回复: 10
收起左侧

[树/链表/图] 面试题讨论-TRIE

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
blfi | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎

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

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

x
有道面试题想跟大家讨论下最优解法,问题是:生成一个数列0-999任选,要求任意三个相邻数字的组合不能重复出现。比如:1,5,4,3,2... (1,5,4)不能在之后以这样的排列再次出现。

评分

参与人数 2大米 +7 收起 理由
adorming + 1 有意思
14417335 + 6

查看全部评分


上一篇:what is wrong with my clone graph code
下一篇:转专业刷题遇到瓶颈,求帮助

本帖被以下淘专辑推荐:

  • · 刷题|主题: 2, 订阅: 0
我的人缘0
cikedewu 2019-7-21 07:59:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
我连普通解法都不会,请问楼主,普通解法是什么思路?
回复

使用道具 举报

我的人缘0
 楼主| blfi 2019-7-21 08:30:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
generate 数据的时候对比前两个有没有重复,重复的话就排除已经出现过的第三个,比如说,1,2,4 以前出现过,那么如果当要generate的数字之前的两个是1,2, 那么这个数字就不能是4。 也可以用树形来理解。这样的话比较慢,因为要考虑所有可能性。
回复

使用道具 举报

我的人缘0
flypanda 2019-7-21 09:13:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
本帖最后由 flypanda 于 2019-7-21 09:17 编辑

楼主所说的TRIE 就应该是最优解法吧。
可以稍微优化一下TRIE NODE 的结构。
或者一个nestedMap就ok吧。Map<Integer, Map<Integer, Set<Integer>>
可以用这个map记录available的那些数字。
再产生数列的过程当中,不断更新这个nestedMap,应该就能generate那个数列
回复

使用道具 举报

我的人缘0
everin 2019-7-21 10:01:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
本帖最后由 everin 于 2019-7-21 10:07 编辑

leetcode某次周赛好像有这个题目。

找错链接了 先修改下一会改
回复

使用道具 举报

我的人缘0
quus 2019-7-21 10:05:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (31)
 
 
0% (0)    👎
回复

使用道具 举报

我的人缘0
everin 2019-7-21 10:12:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
一种是找环路,还有一种是贪心算法构造Lyndon word

https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction
https://en.wikipedia.org/wiki/Lyndon_word

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| blfi 2019-7-21 12:40:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
谢谢大家❤️❤️❤️
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (996)
 
 
9% (106)    👎
没看懂题目

生成多长的数列?

1,4,5,14,56
这个算145重复吗14 56含有145
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-8-23 04:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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