344. Reverse String
Write a function whose function is to reverse the input string. The input string is given in the form of a character array s.
Don't allocate extra space for another array; you must modify the input array in place, use the\(O(1)\) of additional space to address this issue.
Example 1:
Input: s = ["h", "e", "l", "l", "o"]
Output: ["o", "l", "l", "e", "h"]
Example 2:
Input: s = ["H", "a", "n", "n", "a", "h"]
Output: ["h", "a", "n", "n", "a", "H"]
Tip:
1 <= <= 105
s[i] are all printable characters in the ASCII code table.
Positive solution (double pointer)
Upcode (●'◡'●)
class Solution {
public:
void reverseString(vector<char>& s) {
for (int i = 0, j = () - 1; i < ()/2; i++, j--) {
swap(s[i],s[j]);
}
}
};
541. Inverted strings II
Given a string s and an integer k, for every 2k characters counted from the beginning of the string, the first k characters of the 2k characters are reversed.
If there are less than k characters remaining, then 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 rest are left as is.
Example 1:
Input: s = "abcdefg", k = 2
Output: "bacdfeg"
Example 2:
Input: s = "abcd", k = 2
Output: "bacd"
Tip:
1 <= <= 104
s Consists of lowercase English only
1 <= k <= 104
Positive solutions (analog + STL)
This question is actually a simulation, and implementing the inversion rules specified in the question is all that is required.
In fact, during the traversal of the string, just let i += (2 * k), i moves 2 * k each time, and then determine if there needs to be an inverted interval.
Since it is also the start of every 2 * k interval that is to be found, the program will be much more efficient when written this way.
So when you need to process strings one paragraph at a time with a fixed regularity, think about doing something with the expression in the for loop.
Upcode (●'◡'●)
class Solution {
public.
string reverseStr(string s, int k) {
for (int i = 0; i < (); i += (2 * k)) {
// 1. Reverse the first k characters of every 2k characters.
// 2. if the remaining characters are less than 2k but greater than or equal to k, invert the first k characters
if (i + k <= ()) {
reverse(() + i, () + i + k ); } else { reverse(() + i, () + i + k ); }
} else {
// 3. If there are less than k characters left, reverse all remaining characters.
reverse(() + i, ());
}
}
return s; }
}
}; }
Cardcode.com: 54. Replacement of numbers
Title Description
Given a string s that contains lowercase alphabetic and numeric characters, write a function that leaves the alphabetic characters in the string unchanged and replaces each numeric character with a number. For example, for the input string "a1b2c3", the function should convert it to "anumberbnumbercnumber".
Input Description
Enter a string s,s containing only lowercase letters and numeric characters.
Output Description
Prints a new string in which each numeric character is replaced with a number.
Input Example
a1b2c3
Sample output
anumberbnumbercnumber
Alerts
Scope of data:
1 <= < 104
Positive solution (double pointer)
First expand the array to the size of each numeric character after replacing it with "number".
For example, if the length of the string "a5b" is 3, then the length of the string "anumberb" after turning the number characters into the string "number" is 8.
The numeric characters are then replaced from back to front, also known as the double pointer method, in the following process: i points to the end of the new length and j points to the end of the old length.
In fact, many of the array filling class problems are done by pre-filling the array with the size of the filled band first, and then operating from back to front.
There are two advantages to doing this:
- No need to request a new array.
- Filling elements from back to front avoids the problem of having to move all elements after the added element backward each time an element is added when filling elements from front to back.
Upcode (●'◡'●)
#include <iostream>
using namespace std.
int main() {
string s; while (cin >> s) {
while (cin >> s) {
int sOldIndex = () - 1; int count = 0; // Count the number of digits.
int count = 0; // count the number of digits
for (int i = 0; i < (); i++) {
if (s[i] >= '0' && s[i] <= '9') {
s[i] <= '9') { count++;
}
}
// Expand the size of the string s, i.e., replace each number with a "number".
(() + count * 5); int sNewIndex = sNewIndex
int sNewIndex = () - 1; // Replace "number" with "number" from the beginning.
// Replace the numbers with "number" from back to front.
while (sOldIndex >= 0) {
if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
s[sNewIndex--] = 'r';
s[sNewIndex--] = 'e';
s[sNewIndex--] = 'b';
s[sNewIndex--] = 'm'; s[sNewIndex--] = 'm'; s[sNewIndex--] = 'm'
s[sNewIndex--] = 'u'; s[sNewIndex--] = 'u'; s[sNewIndex--] = 'u'
s[sNewIndex--] = 'n';
} else {
s[sNewIndex--] = s[sOldIndex]; }
}
sOldIndex--;
}
cout << s << endl;
}
}
The time complexity of this approach is\(O(n)\)；
In contrast, the time complexity of the front-to-back padding method is\(O(n^2)\)；
Oh, crap.
It's not easy to write a blog, so please give me some support 8~!