刷题--字符串

拉齐有一个01序列，他可以对这个序列进行任意多次变换，每次变换都是把序列的最后若干个元素放到最前面，例如：010011，将最后3个元素011放到最前面，序列变为011010。所有变换结束后，拉齐需要挑出一个全为1的连续区间，要求最大化区间长度。 #include<iostream> using namespace std; #include<string> #include<algorithm> int main() { string str; cin>>str; int len=str.size(); string s=str+str; int res=0; int i=0; int j=0; while(i<2*len) { while(i<2*len&&s[i]=='1') { i++; } res=max(res,i-j); i++; j=i; } // cout<<res<<endl; if(res>len) { cout<<len<<endl; } else{ cout<<res<<endl; } return 0; }

思路：把字符串相加，则一次遍历就可以求出最大联续‘1’的个数，需要注意若字符串全为1，则需要另行处理。 2.

class Solution { public: int maxlength(vector<int>&A,vector<int>&B,int addA,int addB,int len) { int res=0; int k=0; for(int i=0;i<len;i++) { if(A[addA+i]==B[addB+i]) { k++; } else { k=0; } res =max(res,k); } return res; } int findLength(vector<int>& A, vector<int>& B) { int lenA=A.size(); int lenB=B.size(); int ret=0; for(int i=0;i<lenA;i++) { int len=min(lenA-i,lenB); int maxlen=maxlength(A,B,i,0,len); ret =max(maxlen,ret); } for(int i=0;i<lenB;i++) { int len=min(lenB-i,lenA); int maxlen=maxlength(A,B,0,i,len); ret =max(maxlen,ret); } return ret; } };

这个题使用滑动窗口法进行，计算最大的子串的长度。这个题必须掌握！！！