代码随想录算法训练营Day 8

344. 反转字符串

题目描述

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

示例 1:

输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]

示例 2:

输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

解法

双指针，从首位开始逐个交换。

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

541. 反转字符串 II

题目描述

给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前 k 个字符进行反转。

如果剩余少于 k 个字符，则将剩余的所有全部反转。

示例:

输入: s = "abcdefg", k = 2 输出: "bacdfeg"

解法

找到每个要反转的区域的起始位置和结束位置，然后进行反转。

pythonCopy Code
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        s = list(s)
        n = len(s)
        for i in range(0, n, 2*k):
            left = i
            right = min(i + k - 1, n - 1)
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
        return "".join(s)

剑指 Offer 05. 替换空格

题目描述

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

示例 1：

输入：s = "We are happy." 输出："We%20are%20happy."

解法

先遍历一次字符串，计算出替换后的新字符串长度；再遍历一次字符串，依次将每个字符加入新字符串中，当遇到空格时则加入 "%20"。

pythonCopy Code
class Solution:
    def replaceSpace(self, s: str) -> str:
        count = 0
        for char in s:
            if char == ' ':
                count += 1
        new_length = len(s) + count * 2
        res = [''] * new_length
        index = new_length - 1
        for i in range(len(s)-1, -1, -1):
            if s[i] == ' ':
                res[index-2:index+1] = '%20'
                index -= 3
            else:
                res[index] = s[i]
                index -= 1
        return ''.join(res)

151. 翻转字符串里的单词

题目描述

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue" 输出: "blue is sky the"

解法

先将整个字符串翻转，再分别翻转每个单词。

pythonCopy Code
class Solution:
    def reverseWords(self, s: str) -> str:
        s = list(s)
        n = len(s)
        self.reverse(s, 0, n - 1)
        self.reverseWordsHelper(s)
        return ''.join(s).strip()

    def reverseWordsHelper(self, s: List[str]) -> None:
        n = len(s)
        start, end = 0, 0
        while start < n:
            while start < end or (start < n and s[start] == ' '):
                start += 1
            while end < start or (end < n and s[end] != ' '):
                end += 1
            self.reverse(s, start, end - 1)

    def reverse(self, s: List[str], left: int, right: int) -> None:
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

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

题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

示例 1:

输入: s = "abcdefg", k = 2 输出: "cdefgab"

解法

将原字符串分成两个部分，分别进行翻转，最后再对整个字符串进行翻转。

pythonCopy Code
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        s = list(s)
        self.reverse(s, 0, n - 1)
        self.reverse(s, n, len(s) - 1)
        self.reverse(s, 0, len(s) - 1)
        return ''.join(s)

    def reverse(self, s: List[str], left: int, right: int) -> None:
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

案例和场景

假设你正在开发一个社交软件，用户可以发布动态并在动态中包含一些文字内容。其中的文字内容可能会包含很多空格，因此需要将这些空格替换为 "%20"。

同时，为了更好的展示动态，需要将动态的文字部分进行左旋转，常规的右对齐展示方式会导致很多空白区域占用屏幕。通过左旋转可以让文字更加紧凑，使用户能够看到更多的内容。

在实现这个功能时，我们可以使用本文中介绍的算法来完成字符串的反转和空格的替换，从而得到最终的展示效果。