剑指offer 左旋转字符串

Posted on |

左旋转字符串

题目

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

方法

1
2
3
4
5
6
7
8
9
10
11
# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if not s:
            return ''
        n=n%len(s)
        if n==0:
            return s
        s=s[n:]+s[:n]
        return s

方法2

把前n个字符转移到后面。

  • 字符串划分为两部分，前若干个字符为第一部分，后面的字符为第二部分
  • 先分别反转这两部分字符，得到’’
    -
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    # -*- coding:utf-8 -*-
    class Solution:
        def LeftRotateString(self, s, n):
            # write code here
            if len(s)<=0 or len(s)<n or n<0:
                return ''
            strlist=list(s)
            self.Reverse(strlist)
            pivot=len(s)-n
            frontList=self.Reverse(strlist[:pivot])
            behindList=self.Reverse(strlist[pivot:])
            result=''.join(frontList)+''.join(behindList)
            return result

        def Reverse(self, alist):
            if not alist or len(alist)<=0:
                return ''
            start, end = 0, len(alist)-1
            while start<end:
                alist[start],alist[end]=alist[end],alist[start]
                start+=1
                end-=1
            return alist