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

[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 的方法做的，而这道题反而更简化了题目，因为不考虑首尾空格了和单词之间的多空格了，方法还是很简单，先把每个单词翻转一遍，再把整个字符串翻转一遍，或者也可以调换个顺序，先翻转整个字符串，再翻转每个单词，参见代码如下：

解法一：

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 函数翻转，然后移动头指针到下一个位置，在用另一个指针继续扫描，重复上述步骤即可，参见代码如下：

解法二：

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++实现翻转字符串中的单词之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(172.求阶乘末尾零的个数)

    [LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数 Given an integer n, return the number of trailing zeroes in n!. Example 1: Input: 3 Output: 0 Explanation: 3! = 6, no trailing zero. Example 2: Input: 5 Output: 1 Explanation: 5! = 120, one trailing

  • C++实现LeetCode(168.求Excel表列名称)

    [LeetCode] 168.Excel Sheet Column Title 求Excel表列名称 Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:     1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 O

  • C++实现LeetCode(169.求大多数)

    [LeetCode] 169. Majority Element 求大多数 Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1

  • C++实现LeetCode(167.两数之和之二 - 输入数组有序)

    [LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++实现LeetCode(171.求Excel表列序号)

    [LeetCode] 171.Excel Sheet Column Number 求Excel表列序号 Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example:     A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -&g

  • C++实现LeetCode(173.二叉搜索树迭代器)

    [LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and

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

    [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&qu

  • C++实现LeetCode(151.翻转字符串中的单词)

    [LeetCode] 151.Reverse Words in a String 翻转字符串中的单词 Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". Update (2015-02-12): For C programmers: Try to solve it in-p

  • C++实现LeetCode(557.翻转字符串中的单词之三)

    [LeetCode] 557.Reverse Words in a String III 翻转字符串中的单词之三 Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1: Input: "Let's take LeetCode conte

  • C语言如何实现翻转字符串中的单词

    目录 C语言翻转字符串中的单词 另外开辟一个空间,来存放翻转的字符串 直接在原数组上进行操作 C语言字符串各单词的反转 思路 代码实现 代码编译 调试输出 C语言翻转字符串中的单词 另外开辟一个空间,来存放翻转的字符串 单词之间是以空格间隔的,所以我们翻转需要一个一个字符进行翻转,我们需要找寻空格,找到空格表示一个字符已经找到,进行以下的步骤: 1. 首先获取原字符串的长度,申请一个长度+1的空间,因为还需要一个结束符. 2. 定义一个变量i,初始化为0,用i进行字符串的遍历,定义一个start

  • 利用golang的字符串解决leetcode翻转字符串里的单词

    利用golang的字符串解决leetcode翻转字符串里的单词

    题目 给定一个字符串,逐个翻转字符串中的每个单词. 示例 1: 输入: "the sky is blue" 输出: "blue is sky the" 示例 2: 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括. 示例 3: 输入: "a good example" 输出: "exampl

  • python3翻转字符串里的单词点的实现方法

    python3翻转字符串里的单词点的实现方法

    给定一个字符串,逐个翻转字符串中的每个单词. 说明: 无空格字符构成一个 单词 . 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括. 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个. 示例 1: 输入:"the sky is blue" 输出:"blue is sky the" 示例 2: 输入:" hello world! " 输出:"world! hello" 解释:输入字符串可以在前

  • php ucwords() 函数将字符串中每个单词的首字符转换为大写(实现代码)

    php ucwords() 函数将字符串中每个单词的首字符转换为大写, 本文章向码农介绍php ucwords() 函数的基本使用方法和实例,感兴趣的码农可以参考一下. 定义和用法 ucwords() 函数把字符串中每个单词的首字符转换为大写. 注释:该函数是二进制安全的. 相关函数: lcfirst() - 把字符串中的首字符转换为小写 strtolower() - 把字符串转换为小写 strtoupper() - 把字符串转换为大写 ucfirst() - 把字符串中的首字符转换为大写 语法

  • php返回字符串中所有单词的方法

    本文实例讲述了php返回字符串中所有单词的方法.分享给大家供大家参考.具体分析如下: 这段代码返回字符串中的所有单词,当$distinct=true时去除重复元素.代码如下: <?php function split_en_str($str,$distinct=true) { preg_match_all('/([a-zA-Z]+)/',$str,$match); if ($distinct == true) { $match[1] = array_unique($match[1]); } so

  • C++实现LeetCode(142.单链表中的环之二)

    C++实现LeetCode(142.单链表中的环之二)

    [LeetCode] 142. Linked List Cycle II 单链表中的环之二 Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexe

  • C语言左旋转字符串与翻转字符串中单词顺序的方法

    左旋转字符串 题目: 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部. 如把字符串 abcdef  左旋转 2  位得到字符串 cdefab.请实现字符串左旋转的函数. 要求时间对长度为 n  的字符串操作的复杂度为 O(n),辅助内存为 O(1). 分析: 网上看到解法很多种,就不详细说明了. 我采用的是数组不对称的交换时间复杂度应该是O(n). 代码实现(GCC编译通过): #include "stdio.h" #include "stdlib.h&q

随机推荐