📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: 匿名
跳转到指定楼层
上一主题 下一主题
收起左侧

G到场表演

🔗
fatalme 2020-1-28 15:41:01 | 只看该作者
全局:
本帖最后由 fatalme 于 2020-1-28 16:19 编辑

时间O(NL), 空间O(1)

  1.     class Solution {
  2.     public:
  3.         vector<int> matching(string& A, vector<string>& ws) {
  4.             int m = ws[0].size(), L = m * (int)ws.size(), last, N = A.size();
  5.             for (string& w : ws) {  // 三重循环耗时O(ws.size() * m * A.size()) = O(L * A.size())
  6.                 last = -L;  // 如果在L的范围内,word w没有重复,就可以算作是一个candidate了,记下last,last为上次w出现的位置。
  7.                 for (int i = 0; i < m; i++) {
  8.                     for (int j = i; j < A.size(); j += m) {
  9.                         if (A.substr(j, m) == w) {  // use "==" for illustration, should compare using (mod 130)
  10.                             if (j - last >= L) A += 130;  //假设都是lower case。也可以用 A |= (unsigned char)127.
  11.                             last = j;
  12.                         }
  13.                     }
  14.                 }
  15.             }

  16.             vector<int> res;
  17.             for (int j = 0; j < m; j++) {
  18.                 int sum = 0;
  19.                 for (int i = j; i < A.size(); i += m) {
  20.                     sum += A[i] > 130 ? 1 : 0;
  21.                     if (i >= L) sum -= A[i - L] > 130 ? 1 : 0;
  22.                     if (sum == ws.size()) res.push_back(i - L + 1);
  23.                 }
  24.             }
  25.             return res;
  26.         }
  27.     };

复制代码


[/i]

补充内容 (2020-1-29 03:04):
last = -L; 应该在第二重循环内。
回复

使用道具 举报

🔗
fatalme 2020-1-28 15:48:40 | 只看该作者
全局:
匿名者 发表于 2020-1-28 15:36
interviewer的hint是用regular expression

那太**了,g现在出的题越来越差了,反映的水平不知道是不是越来越差。上次去我去onsite,
就出了道看似非常简单,其实非常难的题。我估计面试官自己也没弄清楚。
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-XV0HV  2020-1-28 16:00:19
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
fatalme 2020-1-28 16:03:45 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-XV0HV  2020-1-28 16:12:15
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
Siil 2020-1-28 17:20:00 来自APP | 只看该作者
全局:
可以考虑将每个字符串哈希成一个数字。
然后维护一个长度为l的滑窗,和窗口的哈希值,划过去时,每次增加与删除处理一下,复杂度是
预处理O(m*l) list长度为m,滑窗O(n)
回复

使用道具 举报

🔗
yezhengli_mr9 2020-2-12 01:55:48 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
mylarryshell 2020-2-12 02:12:34 | 只看该作者
全局:
应该就是slinding window吧。把words想象成一个个不同的字母,就是求正好包含所有的字母的字串。这题能用sliding window是因为所有的word都是定长的,如果不定长就该用DP了。
回复

使用道具 举报

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

本版积分规则

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