剑指Offer_58_翻转字符串 | 廖家龙的博客网站

❗️LeetCode_151_翻转字符串里的单词

题目1描述：翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例：

输入: "the sky is blue"
输出: "blue is sky the"

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：
1. 无空格字符构成一个单词。
2. 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
3. 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解法1：栈

//从最后一个字符开始，遇到单词则入栈，遇到空格或第一个字符都要检查一下栈中是否有单词可以弹出，若有则全部弹出并拼接，每弹出一个完整的单词就添加一个空格
class Solution {
public:
    string reverseWords(string s) {

        stack<char> word;  //定义一个栈
        string result = "";

        for (int i = s.size() - 1; i >= 0; --i) {

            //遇到单词则入栈
            if (s[i] != ' ') word.push(s[i]);

            //遇到空格或第一个字符都要检查一下栈中是否有单词可以弹出
            if (s[i] == ' ' || i == 0) {  

                //bool flag = false; 这一行不能去掉
                //输入："  hello world!  "
                //输出："  world! hello "
                //预期结果："world! hello"
                bool flag = false;  //标记是否发生出栈

                while (!word.empty()) {

                //因为word栈存储的元素为char型，而result为string型，故不能相加，只能使用push_back()
                    result.push_back(word.top()); 
                    word.pop();

                    flag = true;
                }

                //每弹出一个完整的单词就添加一个空格
                if (flag == true) result += " ";  
            }

        }

        //最后一个单词后面会多加一个空格，所以只需要截取前面的部分就行
        return result.substr(0, result.size() - 1);  
    }
};

题目2描述：左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：1 <= k < s.length <= 10000

解法1：

//将字符串倍增成为两个同样的字符串拼接的长字符串
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        
        int len = s.size();
        s += s;
        return s.substr(n,len);
    }
};

解法2：

class Solution {
public:
    string reverseLeftWords(string s, int n) {

        //左闭右开
        reverse(s.begin(),s.begin()+n);
        reverse(s.begin()+n,s.begin()+s.size());
        reverse(s.begin(),s.end());
    
        return s;
    }
};