String - 541. Reverse string II

1 Title Description

541. Reverse string II
     Given a string s And an integer k, From the beginning of the string , Each count to 2k Characters , Just reverse this 2k The first... In the character k Characters .

If the remaining characters are less than k individual , Reverse all remaining characters .
If the remaining characters are less than 2k But greater than or equal to k individual , Before reversal k Characters , The rest of the characters remain the same .

2 Title Example

Example 1：
Input ：s = “abcdefg”, k = 2
Output ：“bacdfeg”

Example 2：
Input ：s = “abcd”, k = 2
Output ：“bacd”

3 Topic tips

1 <= s.length <= 104
s It consists of lowercase English only
1 <= k <= 104

4 Ideas

Method 1 ： simulation
Let's simulate directly according to the meaning of the question ： Invert each subscript from 2k2k Starting with a multiple of , The length is kk The string of . If the length of the substring is insufficient kk, Then invert the whole substring .
Some students may be dealing with logic ： every other 2k Before characters k The characters of , Write a bunch of logic code or make a counter , To statistics 2k, Before statistics k Characters .

In fact, in the process of traversing the string , As long as you make i += (2 * k),i Each move 2 * k That's all right. , And then determine whether there is a reverse interval .

Because what we are looking for is every 2 * k Starting point of interval , Write it like this , The program will be much more efficient .

So when it's time to deal with strings in a regular way , Think about it in for Do something on the expression of the loop .

Complexity analysis

Time complexity ：O(n), among n Is string s The length of .

Spatial complexity ：O(1) or O(n), Depending on the nature of the string type in the language used . If the string is modifiable , Then we can directly modify the original string , The space complexity is O(1), Otherwise you need to use O(n) Space to temporarily convert the string into a data structure that can be modified （ For example, an array of ）, The space complexity is O(n).

5 My answer

class Solution {
    
    public String reverseStr(String s, int k) {
    
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
    
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
    
        while (left < right) {
    
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

// Solution 2 （ It seems easier to understand ）
// In fact, the meaning of the title is   every other 2k Before the first reversal k individual , Not enough mantissa k All reverse at one time 
class Solution {
    
    public String reverseStr(String s, int k) {
    
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
    
            int start = i;
            // Here is to judge whether the mantissa is enough k It depends end The position of the pointer 
            int end = Math.min(ch.length - 1, start + k - 1);
            // Invert with XOR  
            while(start < end){
    
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}