【Python 数据结构 8.串】

---

先成为自己的山，再去找心中的海

—— 25.3.5

一、串的基本概念

1.串的概念

串，又叫字符串，是由一系列字符组成的数据结构，用于表示文本或字符序列。在编程中，字串，符串通常用双引号括起来，如"Hello,World！"

而实际在内存中存储的时候，字符串最后还会有一个 ‘\0’ 的字符（’\0’的ASCII的值为 0），它代表了这个串的结尾

2.获取串的长度

串的长度是指字符串中包含的字符个数。每个语言都有内置方法来获取字符串的长度( 注意： 字符串长度是不包含最后一一个 ’ \0 ’ 的)

3.串的拷贝

有时需要创建一个字符串的副本，而不修改原始字符串。一般可通过 遍历串 的方式实现串的拷贝。

4.串的比较

串的比较是指比较两个串是否相等，一般可以采用遍历的方式逐个比较，当然一些语言提供了内置比较函数

5.串的拼接

将两个串拼接在一起，一般是申请一块新的内存，新的内存的大小是两个需要拼接的字符串的长度之和加一，然后第一个串的字符挨个赋值到新的内存，再将第二个串的字符挨个赋值到新的内存，最后加上一个 ‘ \0 ’ ，就实现完毕了。

6.串的索引

可以使用索引来访问字符串中的特定字符。索引从 0 开始，表示第一个字符的位置，依次递增，可以使用 [] 并传入索引值来获取字符

二、Python中串的使用

1.串的定义

直接用 " " 或 ’ ' 定义串

# 空串的定义
s = ''
s = ""

2.串的拼接

用 + 将两个字符串拼接在一起

# 串的拼接
s = s + "hello"
print(s)

3.获取串的长度

用

len()

函数获取长度

len()： 返回对象的长度或元素的数量

# 获取串的长度
print(len(s))

4.获取子串位置

获取子串第一次出现的位置，如果没有出现，则返回 -1

find()： Python 中用于在字符串中查找子串的内置方法。它的作用是返回子串在字符串中首次出现的索引位置，如果子串不存在，则返回 -1。 find() 函数区分大小写，并且可以通过指定起始和结束位置来限制查找范围。

# 获取子串第一次出现的位置，子串在字符串中没有出现，则返回 -1
idx = s.find("hello")
print(idx)

5.获取字符串的索引

索引从 0 开始，到 长度 - 1 结束

# 获取字符串的索引
print(s[0])
print(s[1])
print(s[2])

6.字符串的切片

# 从第二个字符，间隔两个位置，取到倒数第三个字符前的字符。
# "hello world" h:0, e:1, l:2, l:3, o:4, ' ':5, w:6, o:7, r:8, l:9, d:10
#               h:-11, e:-10, l:-9, l:-8, o:-7, ' ':-6, w:-5, o:-4, r:-3, l:-2, d:-1
# el o
print(s[1:-3:2])

7.字符串反转

# 字符串反转
print("反转：",s[::-1])

8.字符串的比较

# 字符串的比较
s = "hello world"
print(s == "hello world")

9.字符串的赋值

# 字符串的赋值
s = "hello China"
print(s)

三、实战

1.

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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 <= s.length <= 105
• s[i] 都是 码表中的可打印字符

方法一、库函数

思路与算法

​ 原地反转 ​： list.reverse() 是Python列表的内置方法，能够直接修改原列表，将元素顺序完全倒置。例如：列表 ['h','e','l','l','o'] 调用 reverse() 后变为 ['o','l','l','e','h'] ，且不返回新列表，完全符合题目“原地修改”的要求。​

​​ 时间复杂度 ： O(n) ，需要遍历列表一半长度的元素进行对称交换。

空间复杂度 ： O(1) ，仅通过指针操作交换元素，不占用额外空间。

列表.reverse()： Python 中用于反转列表元素顺序的内置方法。它直接在原列表上进行操作，不会返回新的列表，而是直接修改原列表的顺序。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()
        

方法二、双指针

思路与算法

双指针策略 ：设置两个指针 l 和 r ，分别指向字符串列表的头部（初始为0）和尾部（初始为 len(s)-1 ）​

对称交换

：每次循环交换 l

和 r

位置的字符，随后 l

右移、 r

左移，直到 l >= r

时终止循环。​

原地操作

：直接在输入的列表 s

上修改，不占用额外空间，符合题目要求。

算法步骤

​ 初始化指针 ： l = 0 ， r = len(s) - 1 。​

循环交换 ：当 l < r 时，交换 s[l] 和 s[r] 的字符。 l 递增1， r 递减1，缩小指针范围。

终止条件 ：当 l >= r 时，所有对称位置的字符已完成交换，整个列表完成反转。

len()： 返回对象的长度或元素的数量

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

方法三、直接使用列表切片操作

切片操作（ s[::-1] ）​​

切片会 创建 新列表，需额外 O(n) 空间，不符合题目“原地修改”的要求

2.

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。

方法一、标记法

思路与算法

​ 初始化变量 ： n 是字符串 s 的长度。 preIsBlank 是一个布尔变量，用于记录前一个字符是否是空格。初始值为 False sum 用于记录段数，初始值为 0 。

遍历字符串 ：对于字符串中的每个字符 s[i] ，检查它是否是空格。如果当前字符是空格：如果前一个字符不是空格（即 preIsBlank == False ），则说明遇到了一个新的段，因此 sum 增加 1，将 preIsBlank 设置为 True ，表示当前字符是空格。如果当前字符不是空格：将 preIsBlank 设置为 False ，表示当前字符不是空格。

返回结果 ：最终返回 sum ，即字符串中的段数。

len()： 返回对象的长度或元素的数量

range()： Python 中的一个内置函数，用于生成一个整数序列。它通常用于 for 循环中，以便迭代一系列的数字。 range() 函数可以接收一个、两个或三个参数，以不同方式生成整数序列

class Solution:
    def countSegments(self, s: str) -> int:
        n = len(s)
        preIsBlank = False
        sum = 0
        for i in range(n):
            if s[i] == " ":
                if preIsBlank == False:
                    sum += 1
                preIsBlank = True
            else: 
                preIsBlank = False
        return sum
                 

方法二、split函数分割

思路与算法

字符串分割 ：使用 split() 方法将字符串 s 按照空白字符（如空格、制表符、换行符等）分割成多个片段。 split() 方法默认以空白字符为分隔符，并自动忽略连续的空白字符。例如， "Hello, world!" 会被分割为 ['Hello,', 'world!'] 。​

片段计数 ：通过 len() 函数统计分割后列表的长度，即为单词（片段）的数量。例如， ['Hello,', 'world!'] 的长度为 2 。

split()： Python中用于字符串处理的一个重要方法，其主要作用是根据指定的分隔符将字符串分割成多个子字符串，并将这些子字符串存储在一个列表中返回。

len()： 返回对象的长度或元素的数量

class Solution:
    def countSegments(self, s: str) -> int:
        return len(s.split())

3.

给你一个偶数长度的字符串 s 。将其拆分成长度相同的两半，前一半为 a ，后一半为 b 。

两个字符串 相似 的前提是它们都含有相同数目的元音（ 'a' ， 'e' ， 'i' ， 'o' ， 'u' ， 'A' ， 'E' ， 'I' ， 'O' ， 'U' ）。注意， s 可能同时含有大写和小写字母。

如果 a

和 b 相似，返回 true ；否则，返回 false 。

示例 1：

输入：s = "book"
输出：true
解释：a = "bo" 且 b = "ok" 。a 中有 1 个元音，b 也有 1 个元音。所以，a 和 b 相似。

示例 2：

输入：s = "textbook"
输出：false
解释：a = "text" 且 b = "book" 。a 中有 1 个元音，b 中有 2 个元音。因此，a 和 b 不相似。
注意，元音 o 在 b 中出现两次，记为 2 个。

方法一、分别遍历字符串的前后部分

算法和思路

长度检查 ：首先检查字符串的长度是否为偶数。如果不是偶数，直接返回 False ，因为无法将字符串平分成两半。

​ 统计元音字母 ：遍历字符串的前半部分，统计元音字母的数量，并将结果累加到 count 中。遍历字符串的后半部分，统计元音字母的数量，并从 count 中减去。

判断结果 ：如果 count 最终为 0 ，说明前后两半的元音字母数量相同，返回 True ；否则返回 False 。

len()： 返回对象的长度或元素的数量

range()：

Python 中的一个内置函数，用于生成一个整数序列。它通常用于 for 循环中，以便迭代一系列的数字。 range() 函数可以接收一个、两个或三个参数，以不同方式生成整数序列

class Solution:
    def isYuanYin(self, s):
        return s in ('a','e','i','o','u','A','E','I','O','U')

    def halvesAreAlike(self, s: str) -> bool:
        n = len(s)
        if n % 2 == 1:
            return False
        count = 0
        for i in range(n // 2):
            if self.isYuanYin(s[i]):
                count += 1
            
        for i in range(n // 2, n):
            if self.isYuanYin(s[i]):
                count -= 1
        return count == 0

方法二、一行代码

sum()： 用于计算可迭代对象（如列表、元组、集合等）中所有元素的和。它还可以接受一个可选的起始值，表示求和的初始值。

set()： 用于创建一个集合。集合是一个无序且不重复的元素集，常用于去重、成员测试和集合运算（如并集、交集、差集等）。

len()： 返回对象的长度或元素的数量

列表推导式： Python中一种简洁且高效的语法，用于从一个可迭代对象（如列表、元组、字符串等）中快速生成新的列表。 语法： [expression for item in iterable if condition]

• expression 是对 item 执行的操作或表达式，生成新列表中的元素。
• item 是从 iterable 中遍历的每一个元素。
• iterable 是可迭代对象（如列表、元组、字符串等）。
• if condition 是可选的条件判断，只有满足条件的 item 才会被处理。

class Solution:

    def halvesAreAlike(self, s: str) -> bool:
        return sum(i in set('aeiouAEIOU') for i in s[:len(s)//2]) == sum(j in set('aeiouAEIOU')  for j in s[len(s)//2:])