第一章 字符串

1.1字符串的旋转给定一个字符串，要求将字符串前面的若干个字符移到字符串的尾部。例如，将字符串‘abcdef’的前3个字符'a','b','c'移到字符串的尾部，那么原来的字符串将变成'defabc',请写一个函数实现该功能。

分析与解法

由于在python中字符串是不可变对象，这里就用python中的列表代替之，例如题目中的‘abcdef’对应['a', 'b', 'c', 'd', 'e', 'f']，python中s='abcdef',list(s)=['a', 'b', 'c', 'd', 'e', 'f']

解法一：蛮力移位

• 首先将左边的一个字符移到字符串的最后位置，可实现left_shift_one(s)；

• 然后调用m次left_shift_one函数，使得字符串开头的m个字符移到字符串的尾部；
  def left_shift_one(s):
  n = len(s)
  key = s[0]
  for i in range(1, n):
  s[i-1] = s[i]
  s[n-1] = key

    def left_rotate_string(s, m):
        while(m>0):
            left_shift_one(s)
            m -= 1
  

  时间复杂度为O(m*n)，空间复杂度O(1)

解法二：三步翻转

• 先将一个字符串分割成两个部分，然后将这两个部分的字符串分别反转，最后再对整个字符串进行整体反转
  def reverse_string(s, f, t):
  while f < t:
  s[fr],s[t] = s[t],s[f]
  f += 1
  t -= 1
  def left_rotate_string(s, m):
  n = len(s)
  m %= n
  reverse_string(s,0,m-1)
  reverse_string(s,m,n-1)
  reverse_string(s,0,n-1)

举一反三

单词翻转

输入一个英文句子，翻转句子中单词的顺序。要求单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号与普通字母一样处理。例如，若输入“I am a student."，则输出"student. a am I"。

def reverse_sentence(s):
    s = s.split()
    f = 0
    t = len(s)-1
    reverse_string(s,f,t)    # 调用上面的reverse_string函数
    return s