跟随carl代码随想录刷题
语言：python

344. 简单反转字符串

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

题目分析

图片来自代码随想录

️交换两个位置的值：s[i], s[j] = s[j], s[i]

完整代码如下

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

541. 简单反转字符串 II

题目：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
.
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

题目分析

与344反转字符串很相似
反转字符串时，可以用切片实现整体替换：[::-1]、s[i:i+k] = reversesubstring(s[i:i+k])

完整代码如下

class Solution:
    def reverseStr(self, s: str, k: int) -> str:

        def reverse_substring(text):
            i = 0
            j = len(text)-1
            while i<j:
                text[i], text[j] = text[j], text[i]
                i += 1
                j -= 1
            return text

        res = list(s)
        
        for i in range(0, len(s), 2*k):  # start:end:step
            res[i:i+k] = reverse_substring(res[i:i+k])  # 用切片进行整体替换
        
        return ''.join(res)

切片yyds

巧用切片

class Solution:
    def reverseStr(self, s: str, k: int) -> str:

        p = 0
        while p<len(s):
            p1 = p+k
            s = s[:p] + s[p:p1][::-1] + s[p1:]
            p += 2*k
        return s

剑指 Offer 05. 替换空格

题目：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

题目分析

数组填充类问题，可以：

1. 预先给数组扩容至填充后的大小
2. 使用双指针法从后往前操作

这样做的好处是：

1. 不用申请新的数组
2. 从后往前填充元素，避免了从前往后填充元素导致每次添加元素都要将添加元素之后的所有元素向后移动。

• 注意：

  • 切片是左闭右开的：[a, b]是不包含b的。如果想包含b，需要写成[a, b+1]

  • 统计字符串中的空格数：s.count(' ')

  • 扩容数组：

    • res = list(s)
    • res.extend([' '] * counter * 2)

  • 返回值''.join(res)

完整代码如下

class Solution:
    def replaceSpace(self, s: str) -> str:
        # 统计空格数`.count()`
        counter = s.count(' ')
        
        # 字符串转数组，另存为res
        res = list(s)

        # 扩容res（扩容的部分填充为空格` `，空格数为 counter*2）
        res.extend([' '] * counter*2) 

        # 初始化双指针的位置
        # 左指针位于原始字符串结尾，右指针位于扩充后的字符串的结尾
        left = len(s)-1
        right = len(res)-1
        while left >= 0:
            if res[left] == ' ':
                res[right-2:right+1] = '%20'  # 左闭右开，所以有边界为`right+1`
                right -= 3
            else:
                res[right] = res[left]
                right -= 1
            left -= 1
        return ''.join(res) 

151. 中等颠倒字符串中的单词

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

题目分析

1. 删除字符串开头空格
2. 删除字符串结尾空格
3. 删除字符串中间多余空格
4. 单词位置取反，而单词本身不变（如单词为hello world）
   • 可以s[::-1]把字符串本身翻转（如：dlrow olleh）
   • 然后把每个单词分别翻转（如：world hello）

1、暴力代码

以空格' '为分隔符，把单词拆解开，然后再倒着存储，单词之间以' '分隔：' '.join(res[::-1])

class Solution:
    def reverseWords(self, s: str) -> str:
        s_list = [i for i in s.split(" ") if len(i) > 0]
        return " ".join(s_list[::-1])

2、双指针代码

class Solution:
    def reverseWords(self, s: str) -> str:
        def trim_head_tail_space(text):
            p = 0
            while p<len(text) and text[p] == ' ':
                    p += 1
            return text[p:]

        # 修剪开头的空格
        s = trim_head_tail_space(s)
        # 修剪结尾的空格
        s = trim_head_tail_space(s[::-1])[::-1]

        # 对中间的单词进行翻转，同时删除多余空格
        slow = 0
        fast = 0
        s = s[::-1]
        while fast<len(s):
            if s[fast] == ' ':
                if s[fast]==s[fast+1]:
                    s = s[:fast] + s[fast+1:]
                    continue
                else:
                    s = s[:slow] + s[slow:fast][::-1] + s[fast:]
                    slow = fast + 1
                    fast = fast + 2
            else:
                fast += 1
        return s[:slow] + s[slow:][::-1]  # 这一步进行最后一个单词的翻转与返回

剑指 Offer 58 - II. 简单左旋转字符串

题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

题目分析

举例说明

1. 整体翻转
   • 原：abcdefg
   • 整体翻转：gfedcba
2. 局部翻转
   • 局部翻转：cdefg + ab

注意：字符串、元组都是不可变量，不能直接通过修改下标的方式进行更改。
方法：先转化成listres = list(s)，然后进行修改，最后转回字符串''.join(res)

完整代码如下

方法1：整体翻转+局部翻转

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        # 整体反转
        res = list(s[::-1])

        # 局部反转
        res[:len(res)-n] = res[:len(res)-n][::-1]
        res[len(res)-n:] = res[len(res)-n:][::-1]

        return ''.join(res)

方法2：切片

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]  # 顺序不要反

方法3：局部翻转+整体翻转

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = list(s)

        # 局部翻转
        res[:n] = res[:n][::-1]
        res[n:] = res[n:][::-1]

        # 整体翻转
        res = res[::-1]

        return ''.join(res)