一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

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

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

[树/链表/图] 纠结的一道题 返回所有对称子集

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

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   66% (798)
 
 
33% (409)    👎

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

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

x
如题  
许多年前onsite的一道题,当时挂的心服口服
所以一直纠结,这道题最后到底应该怎么解,才能符合面试官要求?
得到所有的子集,再filter对称的brute force是不可能符合要求的.
抛砖引玉下


补充内容 (2019-9-18 07:38):
return not count Different Palindromic Subsequences
leetcode 730 进阶版,不是统计个数,要得到所有的subsequences

评分

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

查看全部评分


上一篇:I can't access educative.io anymore
下一篇:从零学大数据分析学习记录帖~
我的人缘0
337845818 2019-9-18 05:04:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   72% (403)
 
 
27% (150)    👎
真是道好题啊, 我看也看不懂, 自然是不会做的了
回复

使用道具 举报

我的人缘0
heymine_ 2019-9-18 07:00:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (73)
 
 
9% (8)    👎
楼主能把题目描述的再详细一点吗
回复

使用道具 举报

我的人缘0
lz4321234 2019-9-18 12:26:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (78)
 
 
2% (2)    👎
楼主面的L家么…返回所有回文子序列?
回复

使用道具 举报

我的人缘0
 楼主| 我一辈子赖美帝 2019-9-18 12:28:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   66% (798)
 
 
33% (409)    👎
lz4321234 发表于 2019-9-18 12:26
楼主面的L家么…返回所有回文子序列?

对的  不过是若干年前面的,突然想到这题了
回复

使用道具 举报

我的人缘0
lz4321234 2019-9-18 12:47:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (78)
 
 
2% (2)    👎
我一辈子赖美帝 发表于 2019-9-18 12:28
对的  不过是若干年前面的,突然想到这题了

我的想法是 返回所有状态得深搜 但是很多子串会重复搜到 记忆化一下 搞个字典记录一下之前搜到的状态 上来先判断是否搜过当前这个串的所有子串 如果有 就直接返回即可
回复

使用道具 举报

我的人缘0
Airtnp 2019-9-19 22:35:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (159)
 
 
5% (9)    👎
http://csie.npu.edu.tw/joomla/Seminar/6/C/3.pdf
搜出来一个
先找出所有相同的字符对, 然后k从2到n/2做 k-1组字符对 和 1组字符对 匹配, 要求下标在外面
> Obviously, the time complexity of this sample algorithm is O(n3)

但我觉得这是n^2 2^n的...

或者DFS存 前缀 和 下标 爆搜
回复

使用道具 举报

我的人缘0
 楼主| 我一辈子赖美帝 2019-9-19 22:43:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   66% (798)
 
 
33% (409)    👎
Airtnp 发表于 2019-9-19 22:35
http://csie.npu.edu.tw/joomla/Seminar/6/C/3.pdf
搜出来一个
先找出所有相同的字符对, 然后k从2到n/2做 ...

sorry no chinese input


I asked the interviewer after the linkeded in onsite, the guy said O(n3) is correct answer
回复

使用道具 举报

我的人缘0
Airtnp 2019-9-20 00:21:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (159)
 
 
5% (9)    👎

平均情况下可能是的
但是对于aaaaaaaaaaaaa这个就是n^2 2^n了啊
回复

使用道具 举报

我的人缘0
Shen.TT 2019-9-26 05:03:47 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
我也想了好久,重点在于如何避免重复。我的想法核心按目标串顺序找,用上DP。比如先找a,b,c,d, 再找aa, bb, cc, dd,再找aaa, aba, aca, ada.... 按这个顺序来
这个情况就可以变成先从两侧找俩a,再从俩a之间找所有的sebsuquence,找俩b,找俩b之间所有的subsequence,以此类推。
用上memorization以后,复杂度三次方
回复

使用道具 举报

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

本版积分规则

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

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

手机版||一亩三分地

GMT+8, 2019-10-24 02:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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