hiho 1485 尺取法 [Offer收割]编程练习赛11 problem A hiho字符串

时间:2023-02-13 18:04:27

#1485 : hiho字符串

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

如果一个字符串恰好包含2个'h'、1个'i'和1个'o',我们就称这个字符串是hiho字符串。  

例如"oihateher"、"hugeinputhugeoutput"都是hiho字符串。

现在给定一个只包含小写字母的字符串S,小Hi想知道S的所有子串中,最短的hiho字符串是哪个。

输入

字符串S  

对于80%的数据,S的长度不超过1000  

对于100%的数据,S的长度不超过100000

输出

找到S的所有子串中,最短的hiho字符串是哪个,输出该子串的长度。如果S的子串中没有hiho字符串,输出-1。

样例输入
happyhahaiohell
样例输出
5

给一个长度100000的字符串,求恰好包含2个h,1个o,1个i的子串的最小长度

今天比赛的第一个题,用尺取法贪心解决的,我自己都不想看我写的代码,写的太挫了,很多可以优化的地方,反正交上去A了就再也不看这代码了,再也不看了。。。。

用4个标记存一下hiho的位置,控制好l和r,然后就是取啦。。。



#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;


char S[100009];
int main(){
    while(scanf("%s",S)!=EOF){
        int len=strlen(S);
        int ans=999999;
        int l=0;
        int r=0;
        int po=-1,pi=-1,ph1=-1,ph2=-1;
        int num_h=0;
        for(int i=0;i<len;i++){
            if(S[i]=='h'){
                if(num_h==0){
                    ph1=i;
                    num_h++;
                    //if(l==-1)l=i;
                    r=i;
                    //r=i;
                }
                else if(num_h==1){
                    ph2=i;
                    num_h++;
                    r=i;
                }
                else{
                    l=ph1+1;
                    ph1=ph2;
                    ph2=i;
                    r=i;
                }

                if(pi<l)pi=-1;
                if(po<l)po=-1;

                //r=i;
                if(pi>=l&&pi<=r&&po>=l&&po<=r&&num_h==2){
                    l=min(pi,po);
                    l=min(l,ph1);
                    ans=min(ans,r-l+1);
                }

            }
            if(S[i]=='o'){
                if(po==-1){
                    r=i;
                    po=i;
                }
                else{
                    r=i;
                    l=po+1;
                    po=i;
                }
                if(pi<l)pi=-1;
                if(ph1<l&&ph1!=-1){
                    ph1=-1;
                    num_h--;
                    ph1=ph2;
                    ph2=-1;
                }
                if(ph1<l&&ph1!=-1){
                    ph1=-1;
                    num_h--;
                }
                if(pi>=l&&pi<=r&&ph1>=l&&ph1<=r&&num_h==2&&po>=l){
                    l=min(pi,po);
                    l=min(l,ph1);
                    ans=min(ans,r-l+1);
                }
            }
            if(S[i]=='i'){
                if(pi==-1){
                    r=i;
                    pi=i;
                }
                else{
                    r=i;
                    l=pi+1;
                    pi=i;
                }
                if(po<l)po=-1;
                if(ph1<l&&ph1!=-1){
                    ph1=-1;
                    num_h--;
                    ph1=ph2;
                    ph2=-1;
                }
                if(ph1<l&&ph1!=-1){
                    ph1=-1;
                    num_h--;
                }
                if(pi>=l&&pi<=r&&ph1>=l&&ph1<=r&&num_h==2&&po>=l&&po<=r){
                    l=min(pi,po);
                    l=min(l,ph1);
                    ans=min(ans,r-l+1);
                }
            }
        }
        if(ans==999999)cout<<-1<<endl;
        else cout<<ans<<endl;
        //cout<<ans<<endl;
    }
    return 0;
}