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

前几天的 骨骼店面

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

那如果B= “ABCA” 就不太对了
回复

使用道具 举报

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

很厉害的解法,想请问下,双指针这样的是怎么计算出来的时间复杂度呢?
回复

使用道具 举报

🔗
xxw289 2018-8-11 06:22:30 | 只看该作者
全局:
TomD 发表于 2018-8-11 03:39
很厉害的解法,想请问下,双指针这样的是怎么计算出来的时间复杂度呢?

我觉得我说错了,时间复杂度应该是O(m * n).
看这个例子:A = "CCCCCCCC", B = "DDDDDC", 每匹配一个A中的C都要扫一遍B.

评分

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

查看全部评分

回复

使用道具 举报

全局:
我觉得找出A和B的count, 然后相除, 如果A的某个字符大于0的同时B的这个字符小于0, 那么就是不存在, 然后把A的frequency 除以B的frequency 加上1 假设A ="AAAAA" B = "AA" 5/2 默认是2 因为ceiling的缘故, 但是实际上是需要至少3个B来组成A,所以就找哪个倍数最大的那个就是了
"
回复

使用道具 举报

🔗
TomD 2018-8-11 06:56:20 | 只看该作者
全局:
xxw289 发表于 2018-8-11 06:22
我觉得我说错了,时间复杂度应该是O(m * n).
看这个例子:A = "CCCCCCCC", B = "DDDDDC", 每匹配一个A中 ...

嗯,那就和我想的一样了,谢谢!
回复

使用道具 举报

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

感觉有个bug… 如果串1是aaabc,串2是aabcaaa,结果应该是2,这个算法似乎会return -1?
回复

使用道具 举报

🔗
sean1993519 2018-8-17 01:51:57 | 只看该作者
全局:
chrislee 发表于 2018-8-16 13:23
感觉有个bug… 如果串1是aaabc,串2是aabcaaa,结果应该是2,这个算法似乎会return -1?

不会啊,先匹配了aaa后匹配了bc,他是每次都把j归0了。不过感觉不好之处在于,时间复杂度最坏情况是O(mn)而不是O(m+n),比如aaaaaaaa和abcdefghi
回复

使用道具 举报

🔗
chrislee 2018-8-17 04:58:39 | 只看该作者
全局:
sean1993519 发表于 2018-8-17 01:51
不会啊,先匹配了aaa后匹配了bc,他是每次都把j归0了。不过感觉不好之处在于,时间复杂度最坏情况是O(mn) ...

哦哦这个例子没举例好  abcabcdd 和 abcadd 这个返回2,正确答案应该是3。 不能光reset j,还得reset i.
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
sean1993519 2018-8-17 07:36:08 | 只看该作者
全局:
chrislee 发表于 2018-8-16 16:58
哦哦这个例子没举例好  abcabcdd 和 abcadd 这个返回2,正确答案应该是3。 不能光reset j,还得reset i.

咦我怎么感觉正确答案就是2,第一次abca,第二次bcdd(根据楼主题意,每次选的可以不是str2的substring而是subsequence)
回复

使用道具 举报

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

本版积分规则

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