面试题58：翻转字符串

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

思路：
使用python的特性，利用split函数以及join，注意split在参数缺省时会以空格tab以及换行符作为分割依据进行分割。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        #python 特性
        #特殊情况
        temp = s.split()  #空格 tab 换行都会分割
        if len(temp)==0:
            return s
        #分割字符串

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

思路二：
使用两次翻转的思想，首先对目前整个字符串翻转，然后对每个单词反转，这样可以达到目标，具体如下:

58 翻转字符串.png

代码实现二：

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        if not s:
            return s
        s = list(s)
        self.ReverseCore(s,0,len(s)-1)

        begin = end  = 0 #初始化指针
        while end < len(s):
            if begin == ' ':
                begin +=1
                end +=1
            elif end == len(s)-1:
                self.ReverseCore(s,begin,end)
                break
            elif s[end] == ' ':
                self.ReverseCore(s,begin,end-1)
                end +=1
                begin = end
            else:
                end +=1
        return ''.join(s)


    #翻转字符串
    def ReverseCore(self,s,start,end):
        if len(s) == 0:
            return
        while start < end:
            s[start],s[end] = s[end],s[start]
            start +=1
            end -=1

提交结果：

image.png 思路二

题目二：左旋字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路一：
三次旋转即可，首反转前n个字符，然后再反转n到最后的字符，最后再整体反转即可

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if not s or n<0 or len(s)<n:
            return '' 
        #一般情况
        s = list(s)
        self.reverseCore(s,0,n-1)
        self.reverseCore(s,n,len(s)-1)
        self.reverseCore(s,0,len(s)-1)
        return ''.join(s)

    def reverseCore(self, s,start,end):
        if not s:
            return
        while start<end:
            s[start],s[end] = s[end],s[start]
            start +=1
            end -=1

思路二：
利用python特性进行拼接，将前n个拼接到后面即可

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if not s or n<0 or len(s)<n:
            return ''
        return s[n:]+s[:n]

提交结果：

image.png 思路二提交结果