📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1162| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] leetcode 567 permutation in string

全局:

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

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

x

这个题需要比较出现次数是否一致。感觉必须比较两个vector, memcmp, etc.
有可能通过一个计数如required, difference来实现吗?


我的解法,比较了两个vector. 想知道此处能否优化?


bool checkInclusion(const std::string &search, const std::string &text) {
  if (search.size() > text.size()) {
    return false;
  }


  static const int kCharSize = 128;
  std::vector<int> searchCount(kCharSize, 0);
  std::vector<int> textCount(kCharSize, 0);


  // First init counts based on search
  auto searchSize = search.size();
  for (std::size_t i = 0; i < searchSize; ++i) {
    char s = search[i];
    ++searchCount[s - '0'];
    char t = text[i];
    ++textCount[t - '0'];
  }
  if (searchCount == textCount) {
    return true;
  }


  for (std::size_t start = 1; start < text.size() - searchSize; ++start) {
    // Remove start-1 and add end
    char t = text[start - 1];
    --textCount[t - '0'];


    std::size_t end = start + searchSize - 1;
    t = text[end];
    ++textCount[t - '0'];


    if (searchCount == textCount) {
      return true;
    }
  }


  return false;
}

上一篇:找有偿算法私教有用吗
下一篇:吐槽向: coding面试用吸佳佳
🔗
argumentt 2024-9-8 04:27:39 | 只看该作者
全局:
可以的,你维护一个difference,因为窗口大小是固定的,每次都是start和end各自加一,所以你只需要看start和end对应的两个char是不是多余的,如果不是(应该要算count)就更新difference,如果是(不应该算count)就不更新,然后看difference是否等于0.
回复

使用道具 举报

🔗
 楼主| 生产队队长 2024-9-8 12:41:19 | 只看该作者
全局:
argumentt 发表于 2024-9-7 13:27
可以的,你维护一个difference,因为窗口大小是固定的,每次都是start和end各自加一,所以你只需要看start ...

>>> 只需要看start和end对应的两个char是不是多余的,
这个怎么能知道?比如
text:   aacbabc
search: ba
time window = 2

first is: aa
second is: (a)ac
这时候,不知道a是不是多余的吧。已经有一个了。去掉这个a实际上是多余的,但无法从search里面知道。
回复

使用道具 举报

🔗
argumentt 2024-9-8 13:01:33 | 只看该作者
全局:
本帖最后由 argumentt 于 2024-9-7 22:04 编辑
生产队队长 发表于 2024-9-7 21:41
>>> 只需要看start和end对应的两个char是不是多余的,
这个怎么能知道?比如
text:   aacbabc

可以知道的,因为你数了“a”在text和在search里的数量,在text里的数量多,所以它是多余的,就不要更新difference。这时候再往右走一步到(a)cb,这时候“a”在text里的计数不比在search里多,它就不是多余的,要更新difference。
回复

使用道具 举报

🔗
 楼主| 生产队队长 2024-9-9 12:00:20 | 只看该作者
全局:
argumentt 发表于 2024-9-7 22:01
可以知道的,因为你数了“a”在text和在search里的数量,在text里的数量多,所以它是多余的,就不要更新d ...

>>> 可以知道的,因为你数了“a”在text和在search里的数量,在text里的数量多,所以它是多余的

这个是假定只有一个a,如果search里面有2个,就需要第三个的时候不更新。
但如何知道几个的时候更新?要么需要一个hash_map来记录。如果没有,怎么知道呢?
回复

使用道具 举报

🔗
argumentt 2024-9-9 12:48:04 | 只看该作者
全局:
生产队队长 发表于 2024-9-8 21:00
>>> 可以知道的,因为你数了“a”在text和在search里的数量,在text里的数量多,所以它是多余的

这个 ...

在你顶楼的code里,已经有searchCount和textCount这两个vector用来记录数量了,所以看这两个向量里的计数就知道应该什么时候算
回复

使用道具 举报

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

本版积分规则

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