【代码随想录】字符串1

344. 反转字符串

link

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]

思路

从头到尾、从尾到头同时遍历，然后交换。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        while left < right:
            temp = s[left]
            s[left] = s[right]
            s[right] = temp

            left += 1
            right -= 1
        

541. 反转字符串 II

link

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = “abcdefg”, k = 2
输出：”bacdfeg”

思路

模拟过程，每过 2k 个步骤就处理一次

class Solution:

    def reserve(self, s):
        left = 0
        right = len(s) - 1
        while left < right:
            temp = s[left]
            s[left] = s[right]
            s[right] = temp

            left += 1
            right -= 1
        return "".join(s)

    def reverseStr(self, s: str, k: int) -> str:
        s_list = list(s)
        res = []

        for i in range(0, len(s_list), 2 * k):
            left = len(s_list) - i

            if left >= 2 * k:
                res.append(self.reserve(s_list[i:i+k]))
                res.append("".join(s_list[i+k:i+2*k]))
            elif left < 2 * k and left >= k:
                res.append(self.reserve(s_list[i:i+k]))
                res.append("".join(s_list[i+k:]))
            else:
                res.append(self.reserve(s_list[i:]))
        
        return "".join(res)

替换数字

link

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

思路

直接遍历，然后将结果存在数组中即可

import sys

input = sys.stdin.read

data = input()

res = []

for i in data:
    if i.isdigit():
        res.append("number")
    else:
        res.append(i)

print("".join(res))

还可以使用双指针的方法，即首先确定数字的数量，然后两个指针分别在原字符串和新的结果 list 上移动。

import sys

input = sys.stdin.read

data = input()
num = 0

for i in data:
    if i.isdigit():
        num += 1

res = ["0"] * (num * 5 + len(data))

j = 0
s = "number"
for i in range(len(data)):
    if data[i].isdigit():
        for index in range(len(s)):
            res[j+index] = s[index]
        
        j += 6
    else:
        res[j] = data[i]
        j += 1
print("".join(res))

上述代码是从前往后填充，但是某些题目要求在原对象上修改（扩容之后），所以最好是从后往前填充。示意图如下：

151.翻转字符串里的单词

link

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：”blue is sky the”

思路

相当于是使用 split() 之后在倒序。注意：split()：多个空格当成一个空格；split(‘ ‘)：多个空格都要分割，每个空格分割出来空字符串。但是要我们自己实现 split() 方法。这里使用了双指针来判断单词的起始位置，然后把单词存起来。

class Solution:
    def reverseWords(self, s: str) -> str:
        
        s_list = list(s)

        slow = 0
        fast = 0
        res = []
        while fast < len(s):
            if slow == fast: 
                if s_list[slow] == " " :
                    slow += 1
                    fast += 1
                elif fast == len(s) - 1:
                    res.append("".join(s[slow:fast+1]))
                    fast += 1
                else:
                    fast += 1
            else:
                if s_list[fast] == " ":
                    res.append("".join(s[slow:fast]))
                    slow = fast
                elif fast == len(s) - 1:
                    res.append("".join(s[slow:fast+1]))
                    fast += 1
                else:
                    fast += 1
        new_res = []
        for i in range(len(res)-1, -1, -1):
            new_res.append(res[i])

        return " ".join(new_res)

进阶

如果要求空间复杂度为 O(1) 呢？类似于之前的 移除元素 ，同样使用快慢指针，删除多余的空格。然后翻转整个字符串，再遍历其中的单词，把单词翻转回来。解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

举个例子，源字符串为：” the sky is blue “

• 移除多余空格 : “the sky is blue”
• 字符串反转：”eulb si yks eht”
• 单词反转：”blue is sky the”

这样空间复杂度为 O(1)，但是 python 的 string 不支持修改，所以可以将字符串转换为 list 来进行操作。

右旋字符串

link

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

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

思路

简单的想法肯定是用一个新的数组来存放结果。但是如果要求在原有的数组基础上进行修改，可以参考上一题使用整体反转+局部反转就可以实现反转单词顺序的思想。如图所示：

其实，思路就是 通过 整体倒叙，把两段子串顺序颠倒，两个段子串里的的字符在倒叙一把，负负得正，这样就不影响子串里面字符的顺序了。