楼主: xiaocase
跳转到指定楼层
上一主题 下一主题
收起左侧

前几天的 骨骼店面

🔗
 楼主| xiaocase 2018-8-10 11:16:33 | 只看该作者
全局:
xxw289 发表于 2018-8-10 11:11
这题我想用greedy从A中匹配尽量多的B中的元素(用反证法可以证出这样肯定最少),然后双指针扫A和B,B扫完了 ...

感谢!受教了
回复

使用道具 举报

🔗
xxw289 2018-8-10 11:18:30 | 只看该作者
全局:

不敢不敢,我也是先写了个O(n^3)的DP优化了一个小时想出来的。。。
回复

使用道具 举报

🔗
samuelhuang 2018-8-10 12:06:45 | 只看该作者
本楼:
全局:
恭喜楼主!
回复

使用道具 举报

全局:
oo小天使oo 发表于 2018-8-10 10:31
可不可以用一个hashmap存B中character和对应的顺序值
例如 B是“ABCD“” 那么hashmap中 A-1 B-2 C-3 D-4
...

这样如果B里面的字符有重复会不会有问题啊?比如B是“ABCDA”,这样A的顺序好像就没办法处理了

评分

参与人数 1大米 +3 收起 理由
UUOlidd + 3 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

🔗
oo小天使oo 2018-8-10 14:02:08 | 只看该作者
全局:
duohedianshuiha 发表于 2018-8-10 13:43
这样如果B里面的字符有重复会不会有问题啊?比如B是“ABCDA”,这样A的顺序好像就没办法处理了

对的 刚刚我把思路写代码的时候发现这个问题不行 xxw289的做法是对的 你可以去参考代码!!

补充内容 (2018-8-10 14:03):
谢谢指出~~~~~(๑•̀ㅂ•́)و✧
回复

使用道具 举报

🔗
gongpumiao0 2018-8-10 17:13:09 | 只看该作者
全局:
请问一下,你的oa是什么题目呢??
回复

使用道具 举报

🔗
jli7 2018-8-10 17:25:30 | 只看该作者
全局:
很有用的信息!
回复

使用道具 举报

全局:
ivanyang 发表于 2018-8-10 06:54
这个感觉可以dfs + memorization
记录下sub  string 是否可以由挖去字符串构成就行。

这样就要记录下所有的substring, 空间复杂度很高吧
回复

使用道具 举报

🔗
 楼主| xiaocase 2018-8-10 21:29:29 | 只看该作者
全局:
gongpumiao0 发表于 2018-8-10 17:13
请问一下,你的oa是什么题目呢??

是求最接近时间和开花问题的变种
回复

使用道具 举报

🔗
linduijue 2018-8-10 22:51:38 | 只看该作者
全局:
xxw289 发表于 2018-8-10 11:11
这题我想用greedy从A中匹配尽量多的B中的元素(用反证法可以证出这样肯定最少),然后双指针扫A和B,B扫完了 ...

ABCABCDD, ABCD
回复

使用道具 举报

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

本版积分规则

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