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

对于求子字符串的问题

全局:

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

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

x
总结下求一个字符串中的子字符串问题模版:
int findSubstring(string s){        vector<int> map(128,0);        int counter;        int begin=0, end=0;        int d; /子序列的长度        for() { /* 初始化表 如果需要的话 想76需要 3就不需要*/}        while(end<s.size()){            if(map[s[end++]]-- ?){  /* modify counter here */ }            while(/* counter condition */){                                                                 if(map[s[begin++]]++ ?){ /*modify counter here*/ }            }              /* update d here if finding maximum*/        }        return d;  }example:


76:
string minWindow(string s, string t) {        vector<int> map(128,0);        for(auto c: t) map[c]++;        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;        while(end<s.size()){            if(map[s[end++]]-->0) --counter;            while(counter==0){ //valid                if(end-begin<d)  d=end-(head=begin);                if(map[s[begin++]]++==0) ++counter;  //make it invalid            }          }        return d==INT_MAX? "":s.substr(head, d);    }3:int lengthOfLongestSubstring(string s) {              vector<int> map(128,0);        int begin =0, end =0, d =0, head =0;        int counter =0;        while(end<s.size()){            if(map[s[end++]]++ >0){counter ++;}            while(counter>0){                  if(map[s[begin++]]-->1) counter --;            }            d = max(d, end-begin);        }        return d;    }或者google 面试题给了一个char set t: {a, b, c},再给一个 string s: "abccddabcd" 最早出现包含abc的位置vector<int> map(128,0);
string s = "abccddabcd";
string t = "abcd";
int begin = 0, end =0, d =INT_MAX, counter =t.size();
int head;
for(int i=0; i<t.size();i++){
    map[t[i++;
}
while(end<s.size()){
    if(map[s[end++-->0) {
        --counter;
    }
    while(counter==0){
        if(end-begin<d)
            d = end-(head=begin);
        if(d == t.size()) {cout<<head<<endl; return 0;}
        if(map[s[begin++++==0) {
            counter++;
        }
    }
}

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

本版积分规则

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