剑指Offer（四十四）：翻转单词顺序序列

2018年1月18日20:30:31 4 4,175 °C

摘要

翻转单词顺序序列，将“student. a am I”翻转成正确的“I am a student.”

剑指Offer（四十四）：翻转单词顺序序列

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

观察字符串变化规律，你会发现这道题很简单。只需要对每个单词做翻转，然后再整体做翻转就得到了正确的结果。

2、代码

C++：

class Solution {
public:
    string ReverseSentence(string str) {
        string result = str;
        int length = result.size();
        if(length == 0){
            return "";
        }
        // 追加一个空格，作为反转标志位
        result += ' ';
        int mark = 0;
        // 根据空格，反转所有单词
        for(int i = 0; i < length + 1; i++){
            if(result[i] == ' '){
                Reverse(result, mark, i - 1);
                mark = i + 1;
            }
        }
        // 去掉添加的空格
        result = result.substr(0, length);
        // 整体反转
        Reverse(result, 0, length - 1);
        
        return result;
    }
private:
    void Reverse(string &str, int begin, int end){
        while(begin < end){
            swap(str[begin++], str[end--]);
        }
    }
};

class Solution {

public:

string ReverseSentence(string str) {

string result = str;

int length = result.size();

if(length == 0){

return "";

}

// 追加一个空格，作为反转标志位

result += ' ';

int mark = 0;

// 根据空格，反转所有单词

for(int i = 0; i < length + 1; i++){

if(result[i] == ' '){

Reverse(result, mark, i - 1);

mark = i + 1;

}

// 去掉添加的空格

result = result.substr(0, length);

// 整体反转

Reverse(result, 0, length - 1);

return result;

}

private:

void Reverse(string &str, int begin, int end){

while(begin < end){

swap(str[begin++], str[end--]);

}

};

Python：

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        s_list = s.split(' ')
        return ' '.join(s_list[::-1])

# -*- coding:utf-8 -*-

class Solution:

def ReverseSentence(self, s):

# write code here

s_list = s.split(' ')

return ' '.join(s_list[::-1])

微信公众号

分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。

目前评论：4 其中：访客 2 博主 2

裸奔的麻瓜

广东省深圳市罗湖区电信 3
回复 2019年1月3日上午9:57 沙发

请问一下大神，这个“追加空格，作为反转的标志位”，似乎没有起到作用呢

Jack Cui Admin 黑龙江省哈尔滨市联通
回复 2019年1月3日上午9:59 1层
@裸奔的麻瓜起作用了吧，根据空格反转。

xiaobaicai

山西省太原市电信 4
回复 2019年1月12日上午10:36 板凳

不需要加空格，可以加 if(result[i] == ‘ ‘ || result[i] == ‘\0’)

Jack Cui Admin 黑龙江省哈尔滨市联通
回复 2019年1月12日上午11:10 1层
@xiaobaicai 嗯嗯，这样也可以。

发表评论取消回复

裸奔的麻瓜 广东省深圳市罗湖区电信 3
回复 2019年1月3日上午9:57 沙发
请问一下大神，这个“追加空格，作为反转的标志位”，似乎没有起到作用呢
- Jack Cui Admin 黑龙江省哈尔滨市联通
  回复 2019年1月3日上午9:59 1层
  @裸奔的麻瓜起作用了吧，根据空格反转。
xiaobaicai 山西省太原市电信 4
回复 2019年1月12日上午10:36 板凳
不需要加空格，可以加 if(result[i] == ‘ ‘ || result[i] == ‘\0’)
- Jack Cui Admin 黑龙江省哈尔滨市联通
  回复 2019年1月12日上午11:10 1层
  @xiaobaicai 嗯嗯，这样也可以。