一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 508|回复: 9
收起左侧

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

[复制链接] |试试Instant~ |树/链表/图, 刷题
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   69% (1033)
 
 
30% (451)    👎

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

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

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
下一篇:从零学大数据分析学习记录帖~
Facebook面试高频题 LeetCode 480 Sliding Window Median 视频讲解 点击查看完整课程
我的人缘0
337845818 2019-9-18 05:04:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   81% (789)
 
 
18% (176)    👎
真是道好题啊, 我看也看不懂, 自然是不会做的了
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
Airtnp 2019-9-19 22:35:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (215)
 
 
4% (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)   👎
全局: 👍   69% (1033)
 
 
30% (451)    👎
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)   👎
全局: 👍   95% (215)
 
 
4% (9)    👎

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-4 04:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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