day8| 344.反转字符串；541.反转字符串II；剑指offer 05.替换空格；151.翻转字符串里的单词；剑指offer 58.左旋转字符串

344.反转字符串

题目简述：

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

解题思路：

没什么好说的，直接双指针

代码如下：

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

        while(left<right):
            s[left],s[right]=s[right],s[left]
            left+=1
            right-=1
        
        return s

541.反转字符串II

题目简述：

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

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

思路：

老实说，一开始没怎么看懂题目。后来理解了，意思是从左到右从1数到2k，这样算一个循环，然后反转前k个字符，之后数数又从1开始，即遍历到第2k+1个字符从1开始数，不是说回过头去遍历第一个字符。

1. 首先把字符串转为列表

2. 利用for循环遍历，每次走2k步，也即0，2k，4k......这样取值

3. 对下标为[0,2k-1],[2k,4k-1]......的分片列表进行反转

4. 利用join函数整合成为字符串

代码如下：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        t = list(s)
        for i in range(0, len(t), 2 * k):
            t[i: i + k] = reversed(t[i: i + k])
        return "".join(t)

剑指Offer 05.替换空格

题目简述：

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

思路：

1. 创建一个空列表。

2. 遍历s，遇到字符，往空列表中append该字符；遇到空格，append %20即可

3. 利用join函数输出

代码实现：

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for c in s:
            if c == ' ': res.append("%20")
            else: res.append(c)
        return "".join(res)

151.翻转字符串里的单词

思路：

1. 去除字符串开头和结尾的空白字符

2. 去掉字符串间多余的空白字符

3. 翻转整个字符串

4. 逐个翻转各个单词

代码如下：

class Solution:
    def trim_spaces(self, s: str) -> list:
        left, right = 0, len(s) - 1
        # 去掉字符串开头的空白字符
        while left <= right and s[left] == ' ':
            left += 1
        
        # 去掉字符串末尾的空白字符
        while left <= right and s[right] == ' ':
            right -= 1
        
        # 将字符串间多余的空白字符去除
        output = []
        while left <= right:
            if s[left] != ' ':
                output.append(s[left])
            elif output[-1] != ' ':
                output.append(s[left])
            left += 1
        
        return output
            
    def reverse(self, l: list, left: int, right: int) -> None:
        while left < right:
            l[left], l[right] = l[right], l[left]
            left, right = left + 1, right - 1
            
    def reverse_each_word(self, l: list) -> None:
        n = len(l)
        start = end = 0
        
        while start < n:
            # 循环至单词的末尾
            while end < n and l[end] != ' ':
                end += 1
            # 翻转单词
            self.reverse(l, start, end - 1)
            # 更新start，去找下一个单词
            start = end + 1
            end += 1
                
    def reverseWords(self, s: str) -> str:
        l = self.trim_spaces(s)
        
        # 翻转字符串
        self.reverse(l, 0, len(l) - 1)
        
        # 翻转每个单词
        self.reverse_each_word(l)
        
        return ''.join(l)

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

思路1：

1. 创建空res

2. 使用切片

3. 传入res

代码如下：

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

思路2：

列表遍历拼接

代码如下：

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = []
        for i in range(n, len(s)):
            res.append(s[i])
        for i in range(n):
            res.append(s[i])
        return ''.join(res)

思路3：

字符串遍历拼接

代码如下：

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = ""
        for i in range(n, len(s)):
            res += s[i]
        for i in range(n):
            res += s[i]
        return res

列表用append，字符串用+。