Topic: Define the left rotation operation of a string: Move several characters in front of the string to the end of the string. If the string abcdef is rotated left by 2 bits to get the string cdefab. Please implement the function of rotating the left string. The complexity of time to string operations with length n is O(n) and the auxiliary memory is O(1).
Analysis: If the limitations of time and space complexity are not taken into account, the easiest way is to regard this question as dividing the string into two parts, and exchanging the positions of these two parts through rotation operation. So we can open a new auxiliary space with length n+1, copy the second half of the original string to the first half of the new space, and copy the first half of the original string to the second half of the new space. It is not difficult to see that the time complexity of this idea is O(n), and the auxiliary space required is also O(n).
The next idea may be a little more troublesome. Let's assume that the string is rotated left by m bit. So we first save the 0th character, put the mth character at the 0th position, put the 2m character at the mth position... and so on, move until the last character can be moved, and finally put the original 0th character at the position we just moved. Then save the first character and move the m+1th element to the first position... Repeat the previous step of processing the 0th character until the previous m characters are processed.
This idea is relatively easy to understand, but when the length n of the string is not an integer multiple of m, it will be a bit troublesome to write a program. Interested friends can try it yourself. Since we will introduce a better method below, I will not provide the code for this idea.
We still regard the string as composed of two segments, and the digit XY is recorded. Rotating left is equivalent to turning the string XY into YX. We first define a flip operation on the string, which is to flip the order of characters in the string. Turn X into XT. Obviously there is (XT)T=X.
We first flip the two segments X and Y respectively, so that we can get XTYT. Then flip XTYT to obtain (XTYT)T=(YT)T(XT)T=YX. It happened to be the result we were looking forward to.
After analyzing this, we will return to the original topic. All we need to do is divide the string into two segments, the first segment is the first m characters, and the rest of the characters are divided into the second segment. Define a function that flips the string and flips it three times in the previous steps. Both the time complexity and the space complexity meet the requirements.
public class Test_21 {
public static void main(String[] args){
StringBuilder str = new StringBuilder("abcde");
int index =5;
(LeftTurn(str,index));
}
public static String LeftTurn(StringBuilder sb,int index){
int strlen = ();
if(sb !=null&&index>=0&&index<=strlen){
int firststart = 0;
int firstend = index-1;
int secondfirst = index;
int secondend = strlen-1;
ReverseString(sb,firststart,firstend);
ReverseString(sb,secondfirst, secondend);
ReverseString(sb,firststart,secondend);
return ();
}
return null;
}
public static void ReverseString(StringBuilder str,int begin, int end){
while(begin<=end){
char temp = (begin);
(begin, (end));
(end, temp);
begin++;
end--;
}
(str);
}
}