从零开始的算法之路（字符串篇）
算法的学习之路上，字符串肯定是必不可少的，今天就来总结一下字符串的入门教程，以及关于一些对字符串的操作（算是补档吧，昨天总结了忘保存了qaq
算法题1:倒转字符串
题目：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
解题方法1 双指针法
def reverseString(s):
"""
Do not return anything, modify s in-place instead.
"""
left=0
right=len(s)-1
for i in range(len(s)):
s[left],s[right]=s[right],s[left]
left=left+1
right=right-1
if(right<=left):
break
return(s)
s = ["1","2","3"]
print(reverseString(s))
写的有点垃圾了，毕竟代码这一方面算刚入门。。。
下面让AI给了一个逻辑更清晰的代码：
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
# Swap the characters
s[left], s[right] = s[right], s[left]
# Move the pointers
left += 1
right -= 1
# Example 1
s1 = ["h", "e", "l", "l", "o"]
reverseString(s1)
print(s1) # Output: ["o", "l", "l", "e", "h"]
# Example 2
s2 = ["H", "a", "n", "n", "a", "h"]
reverseString(s2)
print(s2) # Output: ["h", "a", "n", "n", "a", "H"]
不过双指针这种方法大家肯定不是第一想到的，通常我们首先能想到的是reverse这个简单的方法，俗话说的好，造轮子和用轮子的人同样厉害（）上面的双指针就是造轮子，下面分享个用轮子
解题方法二 一把梭
def reverseString(s):
return list(reversed(s))
s = ["1", "2", "3"]
print(reverseString(s))
这串代码主要注意的是return的值是list(reversed(s))而不能直接return reversed(s):
下面来精讲一些这个的知识点：
穿插知识点：reversed(s) 和 list(reversed(s)) 的区别
reversed(s) 和 list(reversed(s)) 的区别在于它们的返回类型和行为。以下是详细的解释：
- reversed(s) 的返回值：
reversed(s) 是 Python 内置函数，它返回一个 反向迭代器对象（list_reverseiterator），而不是一个列表。这个迭代器对象是惰性的，只有在需要时才会生成值。
特点：
它是一个迭代器，不会立即生成所有元素。
它不会修改原列表，而是提供一种反向访问原列表的方式。
它节省内存，因为不会一次性生成所有元素。
示例：
s = [1, 2, 3, 4]
reversed_iterator = reversed(s)
print(reversed_iterator) # 输出: <list_reverseiterator object at 0x...>
如果你直接尝试打印 reversed_iterator，你会看到一个迭代器对象，而不是反转后的列表。
- list(reversed(s)) 的返回值：
list(reversed(s)) 会将 reversed(s) 返回的迭代器对象转换为一个列表。
特点：
它会立即生成所有元素，并将它们存储在一个新的列表中。
它是一个具体的列表对象，可以直接使用。
示例：
s = [1, 2, 3, 4]
reversed_list = list(reversed(s))
print(reversed_list) # 输出: [4, 3, 2, 1]
这里 reversed_list 是一个具体的列表，可以直接打印或操作。
- 为什么不能直接返回 reversed(s)？
如果你直接返回 reversed(s)，调用者会得到一个迭代器对象，而不是一个列表。这可能会导致以下问题：
无法直接使用：迭代器对象不能像列表一样直接索引或打印。
一次性使用：迭代器对象只能遍历一次，遍历完后就会耗尽，无法重复使用。
示例：
def reverseString(s):
return reversed(s) # 返回迭代器对象
s = [1, 2, 3, 4]
result = reverseString(s)
print(result) # 输出: <list_reverseiterator object at 0x...>
print(list(result)) # 输出: [4, 3, 2, 1] (第一次遍历)
print(list(result)) # 输出: [] (第二次遍历，迭代器已耗尽)
如果你希望函数返回一个具体的列表，而不是迭代器对象，就必须使用 list(reversed(s))。
- 如何选择使用 reversed(s) 还是 list(reversed(s))？
如果你只需要遍历反转后的元素一次，并且希望节省内存，可以直接使用 reversed(s)。
如果你需要一个具体的列表（例如需要多次访问或修改），则应该使用 list(reversed(s))。
其他方法
实际上，如果记不住reverse的方法，可以不用这么麻烦，毕竟：
def reverseString(s):
return s[::-1] # 返回反转后的列表
按照顺序的倒叙也是不二之选
算法题二：整数反转
题目
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
解题方法
首先看到这个题，不难想到的是利用余数进行反转，如果是负数可以取绝对值然后余数处理后再取相反数，也要注意是否溢出
下面给出脚本：
def reverse(x):
# 处理负数
is_negative = x < 0
x = abs(x) # 取绝对值方便处理
n = 0
while x > 0:
t = x % 10 # 取最后一位
n = n * 10 + t # 构建反转后的整数
x //= 10 # 去掉最后一位
# 处理负数
if is_negative:
n = -n
# 检查是否溢出
if n < -2**31 or n > 2**31 - 1:
return 0
return n
# 测试
x = 123
print(reverse(x)) # 输出: 321
x = -123
print(reverse(x)) # 输出: -321
x = 1534236469
print(reverse(x)) # 输出: 0 (因为反转后超出 32 位有符号整数范围)
算法题三： 验证回文串
题目：如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
解题方法1 字典对比法
直接上我这烂透了的脚本：
def isPalindrome(s):
s=s.lower()
diction='qwertyuiopasdfghjklzxcvbnm0123456789'
k=''
for i in s:
if i in diction:
k=str(k)+str(i)
print(k)
kk=''.join(reversed(k))
if k == kk:
return True
else:
return False
补充知识点：倒转字符串
这个算入门版吧，下面讲讲几个倒转字符串的方法吧：
- 使用切片
s = "hello"
reversed_s = s[::-1]
print(reversed_s) # 输出: "olleh"
- 使用 reversed() 函数
s = "hello"
reversed_s = ''.join(reversed(s))
print(reversed_s) # 输出: "olleh"
- 使用循环
s = "hello"
reversed_s = ''
for char in s:
reversed_s = char + reversed_s
print(reversed_s) # 输出: "olleh"
- 使用 reduce 函数（需要导入 functools 模块）
from functools import reduce
s = "hello"
reversed_s = reduce(lambda acc, char: char + acc, s, "")
print(reversed_s) # 输出: "olleh"
5.使用递归
复制
def reverse_string(s):
if len(s) == 0:
return s
else:
return reverse_string(s[1:]) + s[0]
s = "hello"
reversed_s = reverse_string(s)
print(reversed_s) # 输出: "olleh"
最简洁和常用的方法是使用切片 [::-1]，它直接且高效。其他方法在某些特定场景下可能有用，但通常切片是最推荐的方式。
解题方法2 双指针
这个双指针也是很重要的一个方法，他容易想到且操作简单。双指针是一种常见的判断回文的方法，通过从字符串的两端向中间遍历，比较字符是否相等。
def isPalindrome(s):
s = s.lower() # 转换为小写
left, right = 0, len(s) - 1 # 初始化左右指针 一定注意初始值
while left < right:
# 跳过非字母数字字符 可以直接使用 isalnum() 方法来判断字符是否为字母或数字，而不需要手动定义 diction
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
# 比较字符
if s[left] != s[right]:
return False
# 移动指针
left += 1
right -= 1
return True
# 测试用例
s = '0P'
print(isPalindrome(s)) # 输出: False
不废话了，直接上题来学习吧，毕竟学习知识（计科）大部分都是刷题开始的
算法四 字符串中的第一个唯一字符
题目描述：
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
(s只包含小写字母)
思路：
遍历+位运算（xor）
writeup1 XOR
因为上次学的找只出现一次的数组元素想到的解法，可是用到字符串上的时候发现了一些更多的知识点和需要改进的地方，先奉上脚本吧：
def firstUniqChar(s: str) -> int:
seen = 0
repeated = 0
for char in s:
mask = 1 << (ord(char) - ord('a'))
if seen & mask:
repeated |= mask
else:
seen |= mask
for i, char in enumerate(s):
mask = 1 << (ord(char) - ord('a'))
if not (repeated & mask):
return i
return -1
一些注意点：
1.题目说明s是全小写字母，如果不是可能实现不了(如果字符串包含 Unicode 字符（不仅仅是小写字母），异或运算无法高效处理。)，例如：s XOR S = 0不满足，所以这个算法有局限性
2.时间复杂度太高，足足O(n²)
writeup 2 两次遍历
这个应该是比较容易想到且容易实现的方法
一次统计字母数量，一次统计返回第一个1的
脚本如下：
def firstUniqChar(s: str) -> int:
# 使用字典记录每个字符的出现次数
char_count = {}
# 第一次遍历，统计字符出现次数
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
# 第二次遍历，找到第一个出现次数为1的字符
for i, char in enumerate(s):
if char_count[char] == 1:
return i
# 如果没有找到，返回-1
return -1
注意：python的enumerate函数功能：enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
这个方法的时间复杂度是 O(n)，其中 n 是字符串的长度。
算法五 有效的字母异位词
题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
思路：上一个题目的简化版？
writeup1 比较字典
这个思路应该是比较容易想到的
代码：
def isAnagram(s,t):
char_count={}
char_count2={}
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
for char in t:
if char in char_count2:
char_count2[char]+=1
else:
char_count2[char]=1
if char_count == char_count2:
return True
else:
return False
'''实例
s = "anagram"
t = "nagaram"
print(isAnagram(s,t))
'''
使用了两个哈希表（char_count 和 char_count2）分别统计字符串 s 和 t 中每个字符的出现次数，然后比较这两个哈希表是否相等。如果相等，则说明 t 是 s 的字母异位词。
缺点：空间复杂度较高：使用了两个哈希表，空间复杂度为 O(k)，其中 k 是字符集的大小
writeup2 sorted
显然，sorted直接秒了
def isAnagram(s: str, t: str) -> bool:
return sorted(s) == sorted(t)
时间复杂度：O(n log n)，其中 n 是字符串的长度（排序的时间复杂度）。
空间复杂度：O(n)，排序需要额外的空间。
sorted()函数
关于sorted()函数的知识点
sorted() 函数对所有可迭代的对象进行排序操作。
-
sort 与 sorted 区别：
sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。
list 的 sort 方法返回的是对已经存在的列表进行操作，无返回值，而内建函数 sorted 方法返回的是一个新的 list，而不是在原来的基础上进行的操作。 -
语法
sorted 语法：
sorted(iterable, cmp=None, key=None, reverse=False)
参数说明：
iterable -- 可迭代对象。
cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。
sorted()完成后会返回重新排序的列表。
writeup3 数组
直接给脚本，应该都能理解
def isAnagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for char in s:
count[ord(char) - ord('a')] += 1
for char in t:
count[ord(char) - ord('a')] -= 1
for val in count:
if val != 0:
return False
return True
数组法的优点是空间复杂度很低，只有26。时间复杂度：O(n)，其中 n 是字符串的长度。
算法六：实现 strStr()
题目：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
解题方法一 index()一把梭
看到题目后的第一反应是一把梭（）
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle in haystack:
return haystack.index(needle)
else:
return -1
当然，如果你不想使用 index()，可以通过 enumerate() 遍历序列，手动查找第一次出现的下标：
for index, value in enumerate(x):
if value == i:
print(f"元素 {i} 第一次出现的下标是: {index}")
break
else:
print(f"元素 {i} 不在序列中")
解题方法二 暴力破解
def strStr(haystack: str, needle: str) -> int:
# 如果 needle 是空字符串，返回 0
if not needle:
return 0
# 获取 haystack 和 needle 的长度
len_haystack = len(haystack)
len_needle = len(needle)
# 遍历 haystack
for i in range(len_haystack - len_needle + 1):
# 检查从 i 开始的子串是否与 needle 匹配
if haystack[i:i + len_needle] == needle:
return i
# 如果没有找到匹配项，返回 -1
return -1
