代码随想录算法训练营Day8 | Leetcode 151翻转字符串里的单词、卡码网：55右旋转字符串
一、翻转字符串里的单词
相关题目：Leetcode151
文档讲解：Leetcode151
视频讲解：Leetcode151
1. Leetcode151.翻转字符串里的单词
给你一个字符串 s ，请你反转字符串中单词的顺序。
- 单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
- 返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
思路：
- 移除多余空格（类似于Leetcode 27.移除元素的方法）。
- 将整个字符串反转（类似于Leetcode 344.反转字符串的方法）。
- 将每个单词反转（类似于Leetcode 541.反转字符串II的方法）。
注意：
- 单词之间顺序颠倒，但单词本身顺序不颠倒。
整体反转 + 逐词反转
class Solution:
def reverseWords(self, s: str) -> str:
# 反转整个字符串
s = s[::-1]
# 将字符串拆分为单词，并反转每个单词
# split()函数能够自动忽略多余的空白字符
s = ' '.join(word[::-1] for word in s.split())
return s
- 使用双指针
class Solution:
def reverseWords(self, s: str) -> str:
# 将字符串拆分为单词，即转换成列表类型
words = s.split()
# 反转单词
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
# 将列表转换成字符串
return " ".join(words)
- 拆分字符串 + 列表反转
class Solution:
def reverseWords(self, s):
words = s.split() #type(words) --- list
words = words[::-1] # 反转单词
return ' '.join(words) #列表转换成字符串
- 双指针去除空格 + 内部逐词反转
class Solution:
def single_reverse(self, s, start: int, end: int):
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
def reverseWords(self, s: str) -> str:
result = ""
fast = 0
# 1. 首先将原字符串反转并且除掉空格, 并且加入到新的字符串当中
# 由于Python字符串的不可变性，因此只能转换为列表进行处理
s = list(s)
s.reverse()
while fast < len(s):
if s[fast] != " ":
if len(result) != 0:
result += " "
while s[fast] != " " and fast < len(s):
result += s[fast]
fast += 1
else:
fast += 1
# 2.其次将每个单词进行翻转操作
slow = 0
fast = 0
result = list(result)
while fast <= len(result):
if fast == len(result) or result[fast] == " ":
self.single_reverse(result, slow, fast - 1)
slow = fast + 1
fast += 1
else:
fast += 1
return "".join(result)
- 逐字符扫描并遇空格分词
class Solution:
def reverseWords(self, s: str) -> str:
words = []
word = ''
s += ' ' # 帮助处理最后一个字词
for char in s:
if char == ' ': # 遇到空格就说明前面的可能是一个单词
if word != '': # 确认是单词，把它加入到一个数组中
words.append(word)
word = '' # 清空当前单词
continue
word += char # 收集单词的字母
words.reverse()
return ' '.join(words)
二、卡码网：右旋转字符串
1. 卡码网：55右旋转字符串
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
思路：
- 类似于 Leetcode 151.翻转字符串里的单词 的方法，使用整体反转+局部反转就可以实现反转单词顺序的目的。
- 相当于把字符串 s 分成长为 len(s) - k 和 k 的两个部分，先整体倒序，再分别使两个部分倒序。
注意：
- 左旋转和右旋转操作无本质差异，只是反转区间不同。
使用切片
#获取输入的数字k和字符串
k = int(input())
s = input()
#通过切片反转第一段和第二段字符串
#注意：python中字符串是不可变的，所以也需要额外空间
s = s[len(s)-k:] + s[:len(s)-k]
print(s)
- 精简版
k = int(input())
s = input()
print(s[-k:] + s[:-k])