网站文章更新频率,免费微网站系统,文案策划网站,网页设计与制作教程题库151.反转字符串中的单词#xff0c;需二刷
//先去除多余空格#xff0c;再反转所有字符#xff0c;再反转单词#xff0c;即可反转字符串中的单词 void removeWhiteSpace(string s){int slowIndex 0;for(int fastIndex 0; fastIndex s.size(); fastIndex){if(…151.反转字符串中的单词需二刷
//先去除多余空格再反转所有字符再反转单词即可反转字符串中的单词 void removeWhiteSpace(string s){int slowIndex 0;for(int fastIndex 0; fastIndex s.size(); fastIndex){if(s[fastIndex] ! ){if(slowIndex ! 0){s[slowIndex] ;}while(fastIndex s.size() s[fastIndex] ! ){s[slowIndex] s[fastIndex];}}}s.resize(slowIndex);}void swapword(string s, int left, int right){for(; left right; left, right--){swap(s[left], s[right]);}}string reverseWords(string s) {removeWhiteSpace(s);swapword(s, 0, s.size()-1);int start 0;for(int i 0; i s.size(); i){if(s[i] || i s.size()){swapword(s,start,i-1);start i 1;}}return s;}
55.右旋字符串
//了解反转再反转的用法
#includeiostream
#includealgorithm
using namespace std;int main(){int k;string s;cin k;cin s;reverse(s.begin(),s.end());reverse(s.begin(), s.begin()k-1);reverse(s.begin()k,s.end());cout s;
}
28.找出字符串中第一个匹配项的下标需二刷
//KMP经典问题需了解KMP算法中的具体步骤及实现细节主要了解最长公共前后缀的概念以及字符不匹配时从j以前字符串的最长公共前后缀位置开始重新匹配 void getNext(int* next, string needle){int j 0;next[j] 0;for(int i 1; i needle.size(); i){while(j 0 needle[i] ! needle[j]){j next[j - 1];}if(needle[i] needle[j]){j;}next[i] j;}}int strStr(string haystack, string needle) {vectorint next(needle.size());getNext(next[0], needle);int j 0;for(int i 0; i haystack.size(); i){while(j 0 haystack[i] ! needle[j]){j next[j - 1];}if(haystack[i] needle[j]){j;}if(j needle.size()){return (i - needle.size() 1);}}return -1;}
459.重复的子字符串需二刷
//解法1 KMP算法需了解为何最长公共前后缀不包含的字符串什么时候是代表s的最小重复子串 void getNext(int* next, string s){int j -1;next[0] -1;for(int i 1; i s.size(); i){while(j0 s[i] ! s[j1]){j next[j];}if(s[i] s[j1]){j;}next[i] j;}}bool repeatedSubstringPattern(string s) {vectorint next(s.size());getNext(next[0], s);int len s.size();int token len - (next[len - 1] 1);if((next[len - 1] ! -1) (len % token 0)){return true;}return false;}
//解法2.移动匹配
//如果由重复子串构成则能在拼接出的字符串中找到新的相同字符串 bool repeatedSubstringPattern(string s) {string t s s;t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾if (t.find(s) ! std::string::npos) return true; // rreturn false;}
