1. reverse string
Title:
Write a function that reverses the input string. The input string is given as a character array s.
Do not allocate additional space to another array. You must modify the input array in place and use the additional space of O(1) to solve this problem.
Input: s = ["h","e","l","l","o"] Output:["o","l","l","e","h"]
Idea:
Double pointer, different from the reverse linked list (string is an array, which is continuously distributed in memory)
Notes:
Using Python's feature of simultaneous assignment, the swap operation of arrays can be assigned at the same time
s[left], s[right] = s[right], s[left]
Why not set the tmp variable to save the intermediate value?
int tmp = s[i]; s[i] = s[j]; s[j] = tmp;
Since the assignment operation is performed in the order of equal signs from right to left, the values s.size() - 1, 0 are simply assigned to s[left], s[right], and the separate operations. Once the assignment s[i] = s[j], s[i] will be overwritten by the new value, so the intermediate variable must be saved 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
Title:
Given a string s and an integer k, the first k characters in the 2k characters are reversed for every 2k characters counted from the beginning of the string.
If there are less than k remaining characters, all remaining characters are reversed.
If the remaining characters are less than 2k but greater than or equal to K, the first k characters are reversed and the remaining characters remain the same.
Input: s = "abcdefg", k = 2 Output:"bacdfeg"
Idea:
Break the inherent for loop k++ thinking: i move 2*k each time
The two "if" conditions of the topic can be understood as always reversing the first k (< =) and then moving forward 2k steps. It is difficu lt to deal with the first k (< =) before reversing:
For C++, whether to reverse [i, i + k) or [i, n) can be judged by min()
For Python, if the slice writing boundary is not reached (e.g. s[0:999]), the last value of the actual string is returned by default, so there is no need to judge "the case where the remaining characters are less than k".
Notes:
Note: the C++ reverse() function is left open and right closed, and the range is [first,last).
The focus is not on the reverse() operation, so you can use the library function
C++:
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n; i += (2 * k)) {
// 1. reverse the first k characters every 2k characters
// 2. if the remaining characters are less than 2k but greater than or equal to K, the first k characters will be reversed
// 3. if the remaining characters are less than k, all the remaining characters will be reversed—— min() takes n
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 less than k long, no error will be reported, and the actual length will be returned
t[i: i + k] = reversed(t[i: i + k])
return "".join(t)
3. replace spaces
Title:
Please implement a function to replace each space in the string s with "%20".
Input: s = "We are happy." Output:"We%20are%20happy."
Idea:
It looks very simple. It's ok to use the for loop to detect that if you encounter a space, you can replace it with a character. However, the problem that the length of the space is different from that of the new character is not taken into account, so it is impossible to replace it in place. You must expand the space.
Reverse fill in place: first expand the size, and then reverse the double pointer filling to minimize the space complexity.
However, for Python and JAVA, strings are designed as "immutable" (C++ string is variable), that is, a certain character of the string cannot be modified directly. You need to create a new string implementation (fill the new string in sequence).
Notes:
Note:
s.resize(sOldSize + 2 * count);
Why not 3 * count? "%20" clearly occupies 3 places? Because the space originally occupied 1 place
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();
// Reverse traversal modification
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)