Sui Xin's Blog

[剑指Offer]翻转单词顺序

Posted on In Disqus:

题目描述

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

解题思路

  • 方法一：Python作弊法。不断的把读到的单词添加到结果字符串的前面；
  • 方法二：先将整个字符串翻转，再对其中每个单词进行翻转。

代码

Python(2.7.3)

方法一：Python作弊法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        length = len(s)
        if length < 2:
            return s
        start, end = 0, 0
        res = ''
        while end < length:
            if s[end] == ' ':
                res = ' ' + s[start:end] + res
                start = end +1
            elif end == length - 1:
                return s[start:] + res
            end += 1
        return s

运行时间：19ms
占用内存：5724k

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        length = len(s)
        if length < 2:
            return s
        s = self.reverseStr(s, 0, length - 1)
        start, end = 0, 0
        while end < length:
            if s[end] == ' ':
                s = self.reverseStr(s, start, end - 1)
                start = end +1
            elif end == length - 1:
                return self.reverseStr(s, start, end)
            end += 1
        return s
    
    def reverseStr(self, string, start, end):
        str_ls = list(string)
        left, right = start, end
        while left < right:
            str_ls[left], str_ls[right] = str_ls[right], str_ls[left]
            left += 1
            right -= 1
        return ''.join(str_ls)

运行时间：26ms
占用内存：5628k

Related Posts