当前位置: 首页 > news >正文

快速建站开源新闻源发稿平台

快速建站开源,新闻源发稿平台,做招聘网站需要人力资源许可,中国建设银行登录题目链接 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目解析 该题目的意思简而言之就是说,从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串,并且将他们的首字符下标集合进数组中进行返回。 滑动窗口解…

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目解析

该题目的意思简而言之就是说,从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串,并且将他们的首字符下标集合进数组中进行返回。

滑动窗口解法(未优化版本)

分析完该题目可以发现,该题是一个大小不变的滑动窗口题目。窗口大小一直为p字符串的大小,并且我们出窗口和进窗口的大小是相同的,就相当于我们拿着一个窗口在s字符串上去滑动,直到我们找到合适的子串。

如以下动图所示:

 代码如下(含详细注释)

// 该题是一个大小固定的滑动窗口题目
class Solution 
{
public:// 设计一个函数来检查两个哈希表是否相等bool check_hash(int hash1[],int hash2[]){for(int i=0;i<26;i++)if(hash1[i]!=hash2[i]) return false;return true;}vector<int> findAnagrams(string s, string p) {int p_hash[26]={0};int s_hash[26]={0};int ns=s.size();int np=p.size();// 将p字符串中的字符插入到p_hash中for(auto&e:p) p_hash[e-'a']++;vector<int> ret;for(int left=0,right=0;right<ns;right++){// 直接将right对应位置字符进行入哈希表char in=s[right];s_hash[in-'a']++;// 如果right-left+1>np说明已经超过我们滑动窗口的大小了if(right-left+1>np){// 直接从左边进行出窗口char out=s[left++];s_hash[out-'a']--;}// 检查是否符合条件(两个哈希表是否相等)if(check_hash(s_hash,p_hash))// 相等就把该字符串最左边字符的下标入ret数组中ret.push_back(left);}return ret;}
};

滑动窗口(优化版本)

该题只存放了小写字母,因此我们检查两个哈希表其实时间复杂度是非常低的,倘若存入的不止是小写字母,那么我们检查的这一步操作时间复杂度就会非常高,并且检查的这一步操作每一次滑动的时候我们都要进行检测,因此我们可以使用一个count来记录s_hash哈希表中有效字符(存在的字符是p_hash中的字符)的数量,进窗口的时候我们将count++,出窗口的时候我们将count--。

代码如下(含详细注释)

// 优化版本
// 该题是一个大小固定的滑动窗口题目
class Solution 
{
public:vector<int> findAnagrams(string s, string p) {int p_hash[26]={0};int s_hash[26]={0};int ns=s.size();int np=p.size();// 将p字符串中的字符插入到p_hash中for(auto&e:p) p_hash[e-'a']++;vector<int> ret;for(int left=0,right=0,count=0;right<ns;right++){char in=s[right];// 当前字符插入s_hash之后// 如果s_hash中该字符对应的次数<=p_hash[in-'a']// 说明若不是该字符次数在s_hash中的次数与p_hash中的次数一样// 那就是插入之后还比p_hash中的次数少// 无论哪种情况均能说明该字符存在于p_hash中 符合我们要找的字符// 因此count++ 也就是统计的是s_hash中的有效字符数量if(++s_hash[in-'a']<=p_hash[in-'a']) count++;// 如果right-left+1>np说明已经超过我们滑动窗口的大小了if(right-left+1>np){char out=s[left++];// 这一步同理上一步 // 当我们将该字符移除之前该字符次数在s_hash中小于p_hash// 说明该字符是有效字符// 就算该字符不是我们要的有效字符 仍然可以出窗口 只不过count不进行--操作罢了if(s_hash[out-'a']--<=p_hash[out-'a']) count--;}// 如果此时count==np说明当前情况完全满足我们的要求 加入该结果即可if(count==np)ret.push_back(left);}return ret;}
};

http://www.zhongyajixie.com/news/15021.html

相关文章:

  • wordpress 哪些网站吗链接怎么做
  • 400元做网站送网推信息流优化师是做什么的
  • 水贝做网站公司整站优化加盟
  • 建设一个会员积分网站朋友圈软文范例
  • 青岛做外贸网站的公司简介网站流量分析
  • 中国龙头企业十大排行榜优化百度搜索
  • 企业网站源码php重庆企业seo
  • 推广引流吸引人的标题百度seo优化招聘
  • 企业营销型网站建设哪家公司好地方网站建设
  • 网页设计与网站建设 作业seo自动推广工具
  • ps怎么网站首页郑州网站排名优化公司
  • 手机网站有什么不同南京网页搜索排名提升
  • 网站优化注意事项品牌推广与传播方案
  • 做软装有什么网站找图片百度商城app下载
  • 国外网页设计网站电商项目策划书
  • div css网站布局案...郑州seo优化外包热狗网
  • 什么网站上面能接点小活做台州百度快照优化公司
  • 沂水网站建设网上企业推广
  • 开通网站软件的会计科目怎么做线上营销活动方案
  • 园林公司网站建设费用百度搜索排行榜前十名
  • 广州网站设计平台西安网站建设公司十强
  • 个人博客网站实验报告小程序制作费用一览表
  • 康体设备网站建设湖南网站建设平台
  • 龙南建设局网站北京seo排名优化网站
  • php网站开发教程广州线上教学
  • 境外网站建设网站建设7个基本流程
  • 开福区网站建设论坛优化营商环境条例全文
  • wordpress 随机读取一篇文章七台河网站seo
  • 上海个人医疗网站备案表互联网营销行业前景
  • 海口网站建设方案咨询免费推广的方式