Leetcode question brushing (5.31) string

1. Reverse string

344

subject ：
Write a function , Its function is to invert the input string . Input string as character array s Given in the form of .

Do not allocate extra space to another array , You have to modify the input array in place 、 Use O(1) To solve this problem .

 Input ：s = ["h","e","l","l","o"]
 Output ：["o","l","l","e","h"]

Ideas ：
Double pointer , Different from reverse linked list （ A string is an array , Continuously distributed in memory ）

note ：
utilize Python Properties that can be assigned at the same time , Array of swap Operations can be assigned at the same time

s[left], s[right] = s[right], s[left]

Why do not you need to set tmp Variables to hold intermediate values ？

int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

Because the assignment operation is executed in the order of equal signs from right to left , Simply put the value s.size() - 1, 0 Assign to s[left], s[right], And operate separately , Once assigned s[i] = s[j],s[i] Will be overwritten by the new value , So save the intermediate variables first .

C++：

class Solution {
    
public:
    void reverseString(vector<char>& s) {
    
        for(int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--){
    
            swap(s[i], s[j]);
        }
    }
};

Python：

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """ Do not return anything, modify s in-place instead. """

        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

2. Reverse string II

541

subject ：
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 .

 Input ：s = "abcdefg", k = 2
 Output ："bacdfeg"

Ideas ：
Break the inherent for loop k++ thinking ：i Each move 2*k that will do

Two topics “ If ” Conditions , It can be understood as always before reversing k individual （<=）, And move on 2k Step , It's difficult before reversing k individual （<=） To deal with ：
about C++, Is to see whether it is reverse [i, i + k) still [i, n) , It can be used min() Judge
about Python, If the boundary of the slice is not reached （ such as s[0:999]）, The last value of the actual string is returned by default , So you don't have to judge “ The remaining characters are less than k The circumstances of ”.

note ：
notes ：C++ reverse() The function is left open and right closed , The scope is [first,last) Reverse all inside .
The point is not to investigate reverse() operation , So you can use library functions

C++：

class Solution {
    
public:
    string reverseStr(string s, int k) {
    
        int n = s.size();
        for (int i = 0; i < n; i += (2 * k)) {
    
            // 1.  every other  2k  Before characters  k  Characters to reverse 
            // 2.  The remaining characters are less than  2k  But greater than or equal to  k  individual , Before reversal  k  Characters 
            // 3.  The remaining characters are less than  k  individual , Reverse all remaining characters .—— min() take n The situation of 
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};

Python：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        t = list(s)
        for i in range(0, len(t), 2 * k):
        	#  Even if the string is insufficient k Long , No errors reported , The actual length is returned 
            t[i: i + k] = reversed(t[i: i + k])
        return "".join(t)

3. Replace blank space

The finger of the sword Offer 05

subject ：
Please implement a function , Put the string s Replace each space in with "%20".

 Input ：s = "We are happy."
 Output ："We%20are%20happy."

Ideas ：
It's easy to see , Just for Loop detection. If you encounter spaces, replace them with characters ok, However, it does not take into account the different length of spaces and new characters , So it's impossible to change in place , We must expand space .

use In situ reverse filling ： Expand first size, Then reverse the double pointer filling It can minimize the space complexity .

But for the Python and JAVA, Strings are designed to 「 immutable 」 The type of ,（C++ string variable ） That is, you cannot directly modify a character of the string , You need to create a new string implementation （ Fill the new string in sequence ）.

note ：
Pay attention to the examination ：

 s.resize(sOldSize + 2 * count);

Why not 3 * count ? “%20” Mingmingzhan 3 position ？ Because the original space is occupied 1 position

C++：

class Solution {
    
public:
    string replaceSpace(string s) {
    
        int count = 0;
        int sOldSize = s.size();
        //  Count the number of spaces 
        for (char c : s) {
    
            if (c == ' ') count++;
        }
        //  modify  s  length 
        s.resize(sOldSize + 2 * count);
        int sNewSize = s.size();
        //  Traversal modification in reverse order 
        for(int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
    
            if (s[j] != ' ')
                s[i] = s[j];
            else {
    
                s[i - 2] = '%';
                s[i - 1] = '2';
                s[i] = '0';
                i -= 2;
            }
        }
        return s;
    }
};

Python：

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for c in s:
            if c == ' ': res.append("%20")
            else: res.append(c)
        return "".join(res)