狗狗ng挂经 有些无奈

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

djmiss 发表于 2021-6-12 06:56
第四题楼主怎么做的？
假设词库里有n个单词，每个长度是k，给定的string 长度m. 一般 n >> m, m >= k
如 ...

暴力不是n *m吧，暴力你也要遍历所有subsequence

Falldawn 发表于 2021-6-12 07:01
暴力不是n *m吧，暴力你也要遍历所有subsequence

暴力，拿出一个词库里的词，O(m)判断是不是subsequence，一共n个词。

djmiss 发表于 2021-6-12 07:05
暴力，拿出一个词库里的词，O(m)判断是不是subsequence，一共n个词。

你也说了长度为m的单词有2 ^m个subsequence，单词库有n个单词，即使set查重是O(1)，那也是2^m * n啊

Falldawn 发表于 2021-6-12 07:11
你也说了长度为m的单词有2 ^m个subsequence，单词库有n个单词，即使set查重是O(1)，那也是2^m * n啊

查找一个string是不是另一个string M的subsequence不是用双指针O(n)的复杂度么？

djmiss 发表于 2021-6-12 07:16
查找一个string是不是另一个string M的subsequence不是用双指针O(n)的复杂度么？

多谢，明白你的意思了

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问楼主第四题是不是刷题网的792，不过返回的是单词而不是numbers of subsequence ？

匿名者 发表于 2021-6-12 05:47
第三题是这个意思就是返回的ouput也是key msg pair

第二题优化要求是需要尽量少的call randint

randint最少要call 25次吧，楼主call了几次？