剑指offer 面试58题

面试58题：

题目：翻转字符串

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

解题代码一：Python特性

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

class Solution:

    def ReverseSentence(self, s):

        # write code here

        temp=s.split()

        if len(temp)==0:

            return s

        return ' '.join(s.split()[::-1])

解题代码二：两次翻转法

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

class Solution:

    def ReverseSentence(self, s):

        # write code here

        if s==None or len(s)<=0:

            return ''

        s=list(s)

        s=self.Reverse(s)

        pStart=0

        pEnd=0

        listTemp=[]

        result=''

        #print(s)

        while pEnd<len(s):

            if pEnd==len(s)-1:

                #print(self.Reverse(s[pStart:]))

                listTemp.append(self.Reverse(s[pStart:]))

                break

            if s[pStart]==' ':

                pStart +=1

                pEnd +=1

                listTemp.append(' ')

            elif s[pEnd]==' ':

                #print(self.Reverse(s[pStart:pEnd]))

                listTemp.append(self.Reverse(s[pStart:pEnd]))

                pStart=pEnd

            else:

                pEnd +=1

        print(listTemp)

        for i in listTemp:

            result+=''.join(i)

        return result

    def Reverse(self,s):

        # s是一个list列表

        start=0

        end=len(s)-1

        while(start<end):

            s[start],s[end]=s[end],s[start]

            start+=1

            end-=1

        return s

拓展题目：左旋转字符串

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

解题代码一：利用Python特性：

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

class Solution:

    def LeftRotateString(self, s, n):

        # write code here

        if s is None:

            return

        if s==' ':

            return s

        if len(s)<=n:

            return s

        return s[n:]+s[:n]

解题代码二：三次翻转法

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

class Solution:

    def LeftRotateString(self, s, n):

        # write code here

        if s is None or len(s)<=0:

            return ''

        if len(s)<=n:

            return s

        s=list(s)

        listTemp=[]

        result=''

        listTemp.append(self.Reverse(s[0:n]))

        listTemp.append(self.Reverse(s[n:]))

        return ''.join(self.Reverse(sum(listTemp,[])))