hihocoder-Week243-hiho字符串

?

題目1 : 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

?

題解：

　　雙指針滑動窗口，前后兩個指針，如果缺少元素，則前指針前進，如果元素充足，則后指針前進，推進減少窗口。

?

?

#include <cstdlib> #include <cstdio> #include <cstring> const int MAXN = 100000 + 10;char ch[MAXN]; int len, start_id, end_id, ans; int h_num, i_num, o_num; bool check_validation() {return (h_num >= 2 && i_num >= 1 && o_num >= 1); }bool check_ok() {return (h_num == 2 && i_num == 1 && o_num == 1); }void add_item(int idx) {if(ch[idx] == 'h'){h_num += 1; }else if(ch[idx] == 'i'){i_num += 1; }else if(ch[idx] == 'o'){o_num += 1; } }void subtract_item(int idx) {if(ch[idx] == 'h'){h_num -= 1; }else if(ch[idx] == 'i'){i_num -= 1; }else if(ch[idx] == 'o'){o_num -= 1;} }int main(){ scanf("%s", ch); len = strlen(ch); start_id = 0; end_id = 0; h_num = i_num = o_num = 0;ans = len + 1; add_item(start_id); ++start_id; while(end_id < start_id){if(check_validation() || start_id >= len){if(check_ok()){ans = (ans < (start_id - end_id))?(ans):(start_id - end_id); }subtract_item(end_id);++end_id; }else{add_item(start_id);++start_id; }}if(ans > len){ans = -1; }printf("%d\n", ans); return 0; }

　　

?

轉載于:https://www.cnblogs.com/zhang-yd/p/10460946.html

總結

以上是生活随笔為你收集整理的hihocoder-Week243-hiho字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。