劍指offer 58 翻轉字元串、左旋轉字元串（offset=offset%length；）

題目一：

輸入一個英文句子，翻轉句子中單詞的順序，但單詞内字元的順序不變。為簡單起見，标點符号和普通字母一樣處理。例如輸入字元串"I am a student. "，則輸出"student. a am I"。

示例 1：

輸入: "the sky is blue"

輸出: "blue is sky the"

示例 2：

輸入: "  hello world!  "

輸出: "world! hello"

解釋: 輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。

示例 3：

輸入: "a good   example"

輸出: "example good a"

解釋: 如果兩個單詞間有多餘的空格，将反轉後單詞間的空格減少到隻含一個。

說明：

無空格字元構成一個單詞。

輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。

如果兩個單詞間有多餘的空格，将反轉後單詞間的空格減少到隻含一個。

思路1：

1、将單個完整單詞放在棧中，然後将棧中字元流出，拼接成一個字元串

2、考慮特殊情況，字元串開頭有空格

3、字元串結尾有空格

思路2：

反轉字元串

現将整個字元反轉：eulb si yks eht

再将反轉後的字元串中的每個單詞反轉并考慮空格的特殊情況：blue is sky the

思路1代碼：

class Solution {
public:
    string reverseWords(string s) {
        stack<string>res;
        string temp;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]!=' ') {
                temp+=s[i];
            }
            
            if((i+1) == s.size() && !temp.empty()) {
                res.push(temp);
                break;
            }
            
            if(s[i]==' ' && !temp.empty()) {
                res.push(temp);
                temp.clear();
            }   
        }
        
        string str;
        while(!res.empty())
        {
            str+=res.top();
            str+=' ';
            res.pop();
        }
        
        return str.substr(0,str.size()-1);

    }
};
  
           

題目二：

左旋轉字元串

對于一個給定的字元序列S，請你把其循環左移K位後的序列輸出。例如，字元序列S=”abcXYZdef”,要求輸出循環左移3位後的結果，即“XYZdefabc”。

思路：

• 和上面的思路類似，我們可以将字元串分成兩部分，先分别翻轉兩部分子字元串；
• 然後對翻轉後的字元串整體再進行一次翻轉。
• 代碼：

class Solution {
public:
    /**
     * @param str: An array of char
     * @param offset: An integer
     * @return: nothing
     */
    void rotateString(string &str, int offset) {
        // write your code here
      int length=str.size();
      if(length==0)
       return;
      offset=offset%length;
       if(length>0&&offset>0&&offset<length)
       { int begin1=length-offset;
        int end1=length-1;
        int begin2=0;
        int end2=length-offset-1;
        Reverse(str,begin1,end1);
        Reverse(str,begin2,end2);
        Reverse(str,0,length-1);
       }
    }
   void Reverse(string &str,int begin,int end) 
   { if(begin<0||end<0) 
   return; 
   while(begin<end) 
   { 
       char temp=str[begin]; 
       str[begin]=str[end]; 
       str[end]=temp;
       begin++;
       end--; 
  }
   }
};