Leetcode——344. Reverse string /541 Invert string ii/151 Reverse the word / Sword finger in the string offer 58 - ii Rotate string left

summary

344. Reverse string

541. Reverse string II

151. Invert words in string

The finger of the sword Offer 58 - II. Left rotation string

• These questions are all related to string flipping

analysis

344

• The title requires modification in place , Consider using double pointers +swap() Function implementation

  actually , Built in functions reverse() It is through this ;

541

• This question , We make use of reverse() Just simulate the operation

151

• Personally, I think this is a skill problem , Be able to think of using the idea of multiple reversals
  • First flip the entire string
  • Then flip each word once , To achieve the final effect

There is a difficulty here , How to determine a word for the second flip

** The finger of the sword Offer 58 **

• This question , Personally, I think it is also a skill problem , and 151 equally , Use the idea of multiple flips

Ideas

151

How to determine a word in the second flip ？

• It is easy for us to think of using spaces to distinguish words , But according to the title ： There are leading spaces 、 Trailing spaces and multiple spaces between words , So we still need to deal with it carefully
• First of all, after the first flip , Three special blank spaces in the title still exist , We can deal with it according to the situation ：
  • For leading spaces and multiple spaces between words , We can determine one letter at a time , Then look for the word of the letter
  • And it is usually the use of spaces to distinguish words . But considering that there may be no space at the end , You can't distinguish the last word , So for unified operation , We can manually add a space at the end

Code

344

class Solution {
    
public:
    void reverseString(vector<char>& s) {
    
        int left = 0, right = s.size() - 1;		//  Double pointer 
        while (left < right) {
    
            swap(s[left++], s[right--]);		// STL swap() 
        }
    }
};

541

class Solution {
    
public:
    string reverseStr(string s, int k) {
    
        for (int i = 0; i < s.size();i += (2 * k)) {
    		//  Simulation operation 
            if (i + k <= s.size()) {
    
                reverse(s.begin() + i, s.begin() + i + k );
                continue;
            }
            reverse(s.begin() + i, s.begin() + s.size());
        }
        return s;
    }
};

151

class Solution {
    
public:
    string reverseWords(string s) {
    
        reverse(s.begin(), s.end());        //  First flip all characters 

        s.push_back(' ');       //  Unified operation , Add a space at the end 
        for(int i = 0; i < s.size(); ++i) {
    
            if (s[i] != ' ') {
    		//  Until the first letter appears , It can handle leading spaces and multiple spaces between words 
                int j = i + 1;
                for (; j < s.size(); ++j) {
    
                    if (s[j] == ' ') {
    		//  Encountered a space , You can determine the index of the front and back positions of the word 
                        reverse(s.begin() + i, s.begin() + j);      //  Turn over a single word 
                        i = j;  		//  To continue processing  
                        break;			
                    }
                }
            }
        }
        //  Remove extra space . Using two finger acupuncture , Move forward 
        int i = 0, j = 0;
        for(;j < s.size(); ++j) {
    
            if (s[j] != ' ')
                s[i++] = s[j];
            else if(s[j] == ' ' && i > 0 && s[i - 1] != ' ')
                s[i++] = ' ';

        }
        s.resize(i - 1);     //  narrow string, Leave something useful 
        return s;
    }
};

Tips ：

Direct use of resize() To delete the memory at the end

The finger of the sword Offer 58

class Solution {
    
public:
    string reverseLeftWords(string s, int n) {
    
        reverse(s.begin(), s.end());		//  Flip the whole string for the first time 

        int size = s.size();
        //  The next two flips are to restore the normal order , If you don't understand, you can simulate it manually 
        reverse(s.begin(), s.begin() + size - n);	
        reverse(s.begin() + size - n, s.end());

        return s;
    }
};