“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

344. Reverse the string

Topic describes

Write a function that reverses the input string. The input string is given as a character array s.

Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.

Example 1:

Input: s = "h", "e", "l", "l", "o"] output: [" o ", "l", "l", "e", "h"]Copy the code

Example 2:

Input: s = "H", "a", "n", "n", "a", "H"] output: [" H ", "a", "n", "n", "a", "H"]Copy the code

Double pointer method

The problem describes modifying an array explicitly, so consider using a double pointer

class Solution
{
public:
    void reverseString(vector<char> &s)
    {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            chartmp = s[left]; s[left] = s[right]; s[right] = tmp; left++; right--; }}};Copy the code

541. Reverse string II

Topic describes

Given a string s and an integer k, invert the first K characters of the 2k character for every 2k character count from the beginning of the string.

• If there are fewer characters leftk, all the remaining characters are reversed.
• If the remaining characters are less than2kBut greater than or equal tok, then reverse beforekThe rest of the characters remain unchanged.

 

Example 1:

Input: s = "abcdefg", k = 2 Output: "bacdfeg"Copy the code

Example 2:

Input: s = "abcd", k = 2Copy the code

Train of thought

1. Set the index to move 2k steps at a time
2. Determine whether the remaining characters are greater than k or, if greater than k, greater than 2k, and the condition will be reversed
3. Invert the remaining characters less than K

code

Implement the reverse function yourself

class Solution1
{
public:
    // Implement the reverse algorithm yourself
    void myReverse(string &s, int start, int end)
    {
        for (int i = start, j = end; i < j; i++, j--)
        {
            swap(s[i], s[j]); }}string reverseStr(string s, int k)
    {

        for (int i = 0; i < s.size(a); i += (2 * k))
        {
            //1. Invert the first k characters for every 2k characters
            //2, the remaining characters are greater than k but less than 2k, invert the first k
            if (i + k <= s.size())
            {
                myReverse(s, i, i + k - 1);
                continue;
            }
            // all remaining characters smaller than k are reversed
            myReverse(s, i, s.size() - 1);
        }
        returns; }};Copy the code

Call the library function reverse

class Solution
{
public:
    string reverseStr(string s, int k)
    {
        for (int i = 0; i < s.size(a); i += (2 * k))
        {
            //1. Invert the first k characters for every 2k characters
            //2, the remaining characters are greater than k but less than 2k, invert the first k
            if (i + k <= s.size())
            {
                // Invert the first k characters
                reverse(s.begin() + i, s.begin() + i + k);
                continue;
            }

            // if the number of characters is less than k, all characters are reversed
            reverse(s.begin() + i, s.begin() + s.size());
        }
        returns; }};Copy the code