服务器之家

服务器之家 > 正文

C++实现LeetCode(186.翻转字符串中的单词之二)

时间:2021-12-10 15:16     来源/作者:Grandyang

[LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二

Given an input string , reverse the string word by word. 

Example:

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Note: 

  • A word is defined as a sequence of non-space characters.
  • The input string does not contain leading or trailing spaces.
  • The words are always separated by a single space.

Follow up: Could you do it in-place without allocating extra space?

这道题让我们翻转一个字符串中的单词,跟之前那题 Reverse Words in a String 没有区别,由于之前那道题就是用 in-place 的方法做的,而这道题反而更简化了题目,因为不考虑首尾空格了和单词之间的多空格了,方法还是很简单,先把每个单词翻转一遍,再把整个字符串翻转一遍,或者也可以调换个顺序,先翻转整个字符串,再翻转每个单词,参见代码如下:

解法一:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void reverseWords(vector<char>& str) {
        int left = 0, n = str.size();
        for (int i = 0; i <= n; ++i) {
            if (i == n || str[i] == ' ') {
                reverse(str, left, i - 1);
                left = i + 1;
            }
        }
        reverse(str, 0, n - 1);
    }
    void reverse(vector<char>& str, int left, int right) {
        while (left < right) {
            char t = str[left];
            str[left] = str[right];
            str[right] = t;
            ++left; --right;
        }
    }
};

我们也可以使用 C++ STL 中自带的 reverse 函数来做,先把整个字符串翻转一下,然后再来扫描每个字符,用两个指针,一个指向开头,另一个开始遍历,遇到空格停止,这样两个指针之间就确定了一个单词的范围,直接调用 reverse 函数翻转,然后移动头指针到下一个位置,在用另一个指针继续扫描,重复上述步骤即可,参见代码如下:

解法二:

?
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseWords(vector<char>& str) {
        reverse(str.begin(), str.end());
        for (int i = 0, j = 0; i < str.size(); i = j + 1) {
            for (j = i; j < str.size(); ++j) {
                if (str[j] == ' ') break;
            }
            reverse(str.begin() + i, str.begin() + j);
        }
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/186

类似题目:

Reverse Words in a String III

Reverse Words in a String

Rotate Array

参考资料:

https://leetcode.com/problems/reverse-words-in-a-string-ii/

https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/53851/Six-lines-solution-in-C%2B%2B

https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/53775/My-Java-solution-with-explanation

到此这篇关于C++实现LeetCode(186.翻转字符串中的单词之二)的文章就介绍到这了,更多相关C++实现翻转字符串中的单词之二内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://www.cnblogs.com/grandyang/p/6703311.html

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部