剑指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--; 
  }
   }
};