剑指offer

剑指offer

问题一：翻转单词序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

解法一：栈

记得最后一个单词需要再push一下（循环之外）；

class Solution {
public:string ReverseSentence(string str) {if(str.length()<=1)    return str;string tmp = "", result="";int nlength = str.length();stack<string> stack1;for(int i=0; i<nlength; i++){if(str[i] != ' '){tmp += str[i];}else{stack1.push(tmp);stack1.push(" ");tmp = "";}}stack1.push(tmp);while(!pty()){result += p();stack1.pop();}return result;}
};

解法二：书上原解

先整个翻转，然后给每一个单词再转一次

class Solution {
public:string ReverseSentence(string str) {if(str.length()<=1)    return str;int nlength=str.size(), begin=0, end=nlength-1;reverse(str, begin, end);begin = end = 0;for(int i=0; i<nlength; i++){if(str[i]==' '){reverse(str, begin, end-1);begin = end = i+1;}else    end++;}reverse(str, begin, end-1);return str;}void reverse(string &str, int begin, int end){while(begin<end){swap(str[begin], str[end]);begin++;    end--;}}
};

问题二：左旋转字符串

和上一题一样，用三次翻转。

源码：

class Solution {
public:string LeftRotateString(string str, int n) {int nlength = str.size();if(nlength<=1 || n<=0 || n>=nlength)    return str;reverse(str, 0, nlength-1);reverse(str, 0, nlength-n-1);reverse(str, nlength-n, nlength-1);return str;}void reverse(string &str, int begin ,int end){while(begin<end){swap(str[begin], str[end]);begin++;    end--;}}
};