【LeetCode】541. Reverse string II

541. Reverse string II

Reading questions

1. The question is take K In the character , Turn it all over , But the starting position of the next reversal should be 2*K Starting from the position of .
2. If the next starting position starts , Following character <K individual , Then turn it all over .
3. If at first Characters are less than K, Just flip it all over .

🧸 Problem solving

 I look at the 
class Solution {
public:
    string reverseStr(string s, int k) {
		
        int len = s.size();// Record the next position of the last character 
        for(int i = 0;i<len;i+=2*k)
        {
            if(i+k<len)
            {
                reverse(s.begin()+i,s.begin()+i+k);
            }
            else{
                reverse(s.begin()+i,s.begin()+len);
            }
        }
        return s;
    }
};

🧸 Decoding code

i Is the starting position of each flipped character .
i+k Is the end position of each flip .
len Is the next position of the last character
for(int i = 0;i<len;i+=2*k)

for Loop start , Every time i+=2*k, Directly find the starting position of the next inverted character .

if(i+k<len)

i Every time +=2*k, Then as long as i The location of +k, Not more than len, Just reverse i To k Characters .

else

i The location of +k, More than the len, It indicates that the character ratio that can be flipped K Small , Then turn it all over directly .

Tail control

for example k = 2
i + k Turn it over 2 Characters .
So the subscript of the end position is 2, That is, the position of the third character , and reverse It just needs to be closed on the left and opened on the right , See the following explanation for details .

reverse

reverse(left,right) The parameter of the function is left closed and right open .
The official explanation is ： Flipped characters ： It means in left To right The character of the interval , contain left The character pointed to , It doesn't contain right The character pointed to .

🧸 The first time I wrote code

     The algorithm written for the first time : It's so long  , The train of thought is to encounter a problem , Solve it once .
        if(s.size()>=k)// Avoid flipping with only one character , direct return
        {
            int begin = 0, end = s.size();//begin Is to find 2k The location of ,end It's the end 
            int count = 0, prev = 0;//count Is the number of records flipped ,prev Yes k The position where the reversal begins 
            while (begin < end) //begin Keep going back , Until you're done 
            {
                count = 0;//count  Each start will be set 0, Is the number of characters to be flipped 
                prev = begin;// Reset to next k The position where the reversal begins 
                while (begin < end &&count < 2*k)// In the calculation   Is it enough 2k
                {
                    if (count != 2 * k)
                    {
                        ++begin;
                        ++count;
                    }
                }
                if ((count == 2 * k) || (count < 2 * k && count >= k))
                {
                    reverse(s.begin() + prev, s.begin() + prev+k);// Flip prev To k Characters between 
                }
                else if (count < k && count!=1)
                {
                	// Flip prev All characters to the end , because count Only record to end The location of 
                    reverse(s.begin() + prev, s.begin() +prev+count);
                }
            }
        }
        else
        {
            if(s.size() != 1)// Here is   If k Directly greater than   The number of characters , Just flip it all 
            {
                reverse(s.begin(),s.end());
            }
        }
        return s;
    }
 This code is redundantly written , There seem to be a lot of useless variables , I haven't changed any more . This code can be passed .

come on. , I wish you get your favorite offer！