526互联

Leetcode刷题day7-字符串.反转ⅠⅡ.反转单词.右旋转

发布时间 2023-12-06 16:14:14作者: 智障学Leetcode

344.反转字符串

344. 反转字符串 - 力扣（LeetCode）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

  • 示例 1：
    • 输入：s = ["h","e","l","l","o"]
    • 输出：["o","l","l","e","h"]
  • 示例 2：
    • 输入：s = ["H","a","n","n","a","h"]
    • 输出：["h","a","n","n","a","H"]

解题思路：
1. 双指针-while：左右指针，while left < right：交换s[left],s[right]=s[right],s[left]
2. 双指针-for：左右指针：for i in range(len(s)//2): s[i],s[-i-1]=s[-i-1],s[i]
3. 库函数reverse: s.reverse()
4. 列表推导式：直接反转

class Solution():
	def reverseString(s):  # 双指针-while
		left,right=0,len(s)-1
		while left<right:
			s[left],s[right]=s[right],s[left]
			left+=1
			right-=1

	def reverseString(s):  # 双指针-for
		for i in range(len(s)//2):
			s[i],s[-i-1]=s[-i-1],s[i]

	def reversestring(s):  # 库函数reverse
		s.reverse()

	def reverseString(s):  # 列表推导式，倒序loop
		s[:]=[s[i] for i in range(len(s)-1,-1,-1)]

514.反转字符串Ⅱ

541. 反转字符串 II - 力扣（LeetCode）
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
  • 示例 1：
    • 输入：s = "abcdefg", k = 2
    • 输出："bacdfeg"
  • 示例 2：
    • 输入：s = "abcd", k = 2
    • 输出："bacd"

解题思路：
1. 双指针-字符串累加：按2*k间隔遍历字符串，前k个字符倒序，后k个不变，累加到新字符串
2. 双指针-列表元素交换：原始字符串转列表，按2k间隔遍历，在原列表上对前k字符串倒序

class Solution():
	def reverseStr(s,k):
		g = ""
		for left in range(0,len(s),2*k):  # 双指针-字符串累加
			right = left+k
			while left<right:
				g+=s[right-1right]
				right-=1
			g+=s[left+k:left+2*k]
		return g

	def reverseStr(s,k):  # python语法糖
		g=""
		for i in range(0,len(s),2*k):
			g+=s[i:i+k][::-1]
			g+=s[i+k:i+2*k]
		return g
		
	def reverseStr(s,k):  # 双指针-列表元素交换
		def reverse(nums):
			for i in range(len(nums)//2):
				nums[i],nums[-i-1]=nums[-i-1],nums[i]
			return nums
		result = list(s)
		for i in range(0,len(s),2*k):
			result[i:i+k]=reverse(result[i:i+k])
		return ''.join(result)

151.反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意： 输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

  • 示例 1：
    • 输入：s = "the sky is blue"
    • 输出："blue is sky the"
  • 示例 2：
    • 输入：s = "  hello world  "
    • 输出："world hello"
    • 解释： 反转后的字符串中不能存在前导空格和尾随空格。
  • 示例 3：
    • 输入：s = "a good   example"
    • 输出："example good a"
    • 解释： 如果两个单词间有多余空格，反转后的字符串需要将单词间的空格减少到仅有一个。

解题思路：
1. 库函数split：split切分字符串，倒序排列并去除空元素，join连接
2. 双指针：先去除前后空格，再从右向左遍历字符串，遇到空格时，对暂存字符串temp进行反转-存储-添加空格；未遇到空格时，将字符暂存至temp

class Solution():
	def reverseWords(s):   # 库函数-split-join
		s_list = s.split(" ")
		s_list = [s_list[i] for i in range(len(s_list)-1,-1,-1) if s_list[i]!='']
		return " ".join(s_list)

	def reverseWords(s):   # 双指针
		left,right=0,len(s)-1
		res,temp = "",""
		while left<=right and s[left]==" ":
			left+=1
		while left<=right and s[right]==" ":
			right-=1
		while left<=right:
			if s[right]==" ":
				res += temp[::-1]
				res+=s[right]
				temp = ""
				while s[right]==" ": right-=1
			temp += s[right]
			right -= 1
		res += temp[::-1]
		return res

右旋转字符串

题目页面 (kamacoder.com)
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

  • 示例
    • 输入：对于输入字符串 "abcdefg" 和整数 2
    • 输出：函数应该将其转换为 "fgabcde"

解题思路：
1. 错位填充：创建 $len(s)$ 长度的空列表，从 $k%len(s)$ 位置开始填充，直到$(k+len(s))%len(s)$
2. 列表交换：字符串转列表，切分成左右两部分，再拼接

def rightString(k,s):  # 错位填充
	res = [0]*len(s)
	for i,j in enumerate(range(k,k+len(s))):
		res[j%len(s)]=s[i]
	return "".join(res)

def rightString(k,s):
	s_list = list(s)
	right = s_list[-k:]
	left = s_list[:-k]
	return "".join(right+left)