字符串

基础知识

Python不支持单字符类型，也就是没有字符只有字符串，单字符在也是作为一个字符串使用。字符串具有不可变性，即一旦创建，就不能被修改，对字符串的操作通常会返回一个新的字符串，而不是在原始字符串上进行修改。Python的字符串同列表一样，也是序列的一种，可以进行迭代，也可以通过索引访问字符元素。用反斜杠()转义字符串中的特殊字符。

常用语法：
1. str.lower()和str.upper(): 将字符串转换为小写或大写形式。
2. str.capitalize()和str.title(): 将字符串的首字母或每个单词的首字母大写。
3. str.strip(): 去除字符串两端的空格或指定的字符（默认为空格或换行符）。
4. str.split(): 将字符串分割成一个列表，根据指定的分隔符将字符串分割。默认分割所有的空字符，包括空格、换行(\n)、制表符(\t)等。
5. str.join(): 将列表或其他可迭代对象中的字符串元素连接成一个字符串。
6. str.replace(): 将字符串中的指定子串替换为另一个子串。
7. str.find()和str.rfind(): 在字符串中查找指定子串的第一次出现位置或最后一次出现位置。
8. str.count(): 统计字符串中指定子串出现的次数。
9. str.isalpha()、str.isdigit()、str.isalnum(): 检查字符串是否只包含字母、数字或字母和数字的组合。
10. str.splitlines(): 将多行字符串拆分成行的列表。
11. str.format(): 格式化字符串，将占位符替换为指定的值。
12. str.startswith()和str.endswith(): 检查字符串是否以指定的子串开头或结尾。
13. str.islower()、str.isupper()、str.istitle(): 检查字符串是否全部为小写、大写或标题形式（每个单词的首字母大写）。
14. readline(size)从文件读取整行，包括 “\n” 字符。如果指定了一个非负数的参数，则返回指定大小的字节数，包括 “\n” 字符。

ACM模式常用语法：

import sys
n = int(input())  # 一般第一行表示数据的总行数
data = []
while True:  # 知道数据总行数后可以使用for循环
    s = sys.stdin.readline().strip()   # sys.stdin可以用input()代替
    if not s:
        break
    data.append(s)
    print(s, end=' ')   # 输出s并以空格结尾

# 输入： 2 3 6 4 8 9
data = list(map(int, sys.stdin.readline().strip().split()))  # 转换为list

牛客网面试题输入输出的处理（python语言，包括readline()、strip()、split()的使用）

字符串匹配的经典算法：

Knuth-Morris-Pratt算法（KMP）：KMP算法利用了模式串中已匹配的信息来尽量减少不必要的比较。通过构建一个部分匹配表（也称为next数组），可以在不匹配时直接跳过一部分字符，提高匹配效率。

# next数组表示pattern串中前缀后缀最长公共子串长度
def calNext(s2):
    j, i = 0, 1
    next = [0] * len(s2)
    while i < len(s2):
        if s2[j] == s2[i]: 
            next[i] = j + 1
            j += 1
            i += 1
        else:
            if j != 0:
                j = next[j - 1]
            else:
                next[i] = 0
                i += 1
    return next

def KMP(s1, s2, pos = 0):   # pos为开始比较的位置，一般为0
    res = []
    next = calNext(s2)  # [0, 0, 0, 1, 2, 0]
    i, j = pos, 0
    while i < len(s1) and j < len(s2):
        if s1[i] == s2[j]:
            i += 1
            j += 1
        else:
            if j != 0:
                j = next[j - 1]  # 具有公共前缀的pattern字符索引
            else:
                i += 1
        if j == len(s2):  # 匹配到结尾了
            res.append(i - j)  # 返回第一个字母的索引
            j = next[j - 1]
    return res  # 所有匹配的开头索引列表

# 灵神版本kmp
def kmp(text: str, pattern: str) -> List[int]:
    m = len(pattern)
    pi = [0] * m
    c = 0
    for i in range(1, m):
        v = pattern[i]
        while c and pattern[c] != v:
            c = pi[c - 1]
        if pattern[c] == v:
            c += 1
        pi[i] = c

    res = []
    c = 0
    for i, v in enumerate(text):
        while c and pattern[c] != v:
            c = pi[c - 1]
        if pattern[c] == v:
            c += 1
        if c == len(pattern):
            res.append(i - m + 1)
            c = pi[c - 1]
    return res
 
s1 = "abxabcabcaby"  # txt串
s2 = "abcaby"  # pattern串
print(KMP(s1, s2))	# 6

Rabin-Karp 算法是一种基于哈希函数的字符串匹配算法。它通过对主串和模式串分别计算哈希值，并比较哈希值来判断是否匹配。在匹配时，还需要处理哈希值冲突的情况。
- 核心逻辑：把一个字符串对象转化成了一个数字，就是你设计的一个哈希算法，生成的数字就可以认为是字符串的哈希值。在滑动窗口中快速计算窗口中元素的哈希值，叫做滑动哈希技巧。我们不要每次都去一个字符一个字符地比较子串和模式串，而是维护一个滑动窗口，运用滑动哈希算法一边滑动一边计算窗口中字符串的哈希值，拿这个哈希值去和模式串的哈希值比较，这样就可以避免截取子串，从而把匹配算法降低为 O(N)。
Boyer-Moore算法（BM）：BM算法是一种高效的字符串匹配算法，它利用了模式串的信息来跳过多个字符。通过构建好后缀表和坏字符表，可以根据模式串与主串中的字符不匹配的位置进行跳跃，提高匹配速度。

参考博客：

KMP详解

油管最火KMP算法讲解，阿三哥的源代码！

滑动窗口算法延伸：RABIN KARP 字符匹配算法

力扣指南

字符串
题目	技巧	难度
✅151. 反转字符串中的单词	str.split()默认为连续空格分割	🌟🌟
✅43. 字符串相乘	模拟乘法	🌟🌟
✅227. 基本计算器 II		🌟🌟
✅224. 基本计算器		🌟🌟🌟

数组

nums和nums[:]区别：用nums只是将nums指向那个副本，而nums在内存中原来地址的值没有变化，用nums[:]就会将内存中地址对应的值改变。gelthin-解释为何要用 nums1[:]
reduce函数用法：求nums数组的和 sum = reduce(lambda x, y: x+y, nums)
for j in zip(*grid)可以取出二维数组grid中的列元素（tuple类型）。*grid 会将 grid 中的每个列表作为单独的参数传递给 zip() 函数。zip(*grid) 就会返回一个迭代器，每个元素都是一个元组，包含来自 grid 中每个列表的相应位置的元素。相当于将 grid 矩阵转置（将行变为列，将列变为行）。
itertools.accumulate(list, initial=0)：结果为首项为0的list前缀和数组
itertools.pairwise(list/str)：每次取出相邻的一对元素

有序集合

添加/插入/删除单个元素复杂度为$O(log(n))$；添加k个可迭代对象复杂度为$O(k*log(n))$

from sortedcontainers import SortedList
sl = SortedList([2,1,4,3])  # 初始化
sl.add(6)                   # 添加元素
sl.update([3, 6, 4])        # 添加可迭代对象
sl.clear()                  # 删除全部元素
sl.discard(value)           # 删除value，没有该值则不做操作
sl.remove(value)            # 删除value，没有该值则报错ValueError
sl.pop(index=-1)            # 弹出index元素，默认最后一个元素
idx = sl.bisect_left(value) # 返回value插入的索引idx
sl.count(value)             # 返回value的元素数量
sl.index(value)             # 返回value的最小索引，没有该值则报错ValseError

力扣指南

数组
题目	技巧	难度
✅48. 旋转图像	对角转换	🌟🌟
✅54. 螺旋矩阵	设置边界模拟	🌟🌟
✅59. 螺旋矩阵 II	同上	🌟🌟
✅391. 完美矩形		🌟🌟🌟

哈希

特点：快速的数据存取：哈希表通过哈希函数将关键字映射到索引位置，因此可以在常数时间复杂度内存取数据，具有快速的存取速度;高效的查找和插入操作：通过哈希函数计算索引位置，可以快速定位数据的存储位置，从而实现高效的查找和插入操作。
哈希函数：哈希函数将关键字映射到索引位置，确保关键字的均匀分布。好的哈希函数应该尽可能减少冲突，即不同的关键字映射到相同的索引位置。
冲突解决：冲突是指不同的关键字经过哈希函数计算后映射到了相同的索引位置。
- 链地址法（Chaining）：在每个哈希桶（哈希表的每个索引位置）上维护一个链表或其他数据结构，将哈希冲突的元素都存储在同一个桶中。当发生冲突时，新元素会被添加到桶中的链表末尾。链地址法可以解决大部分的哈希冲突，并且适用于大多数情况下的哈希表实现。但是在链表过长时，查找的效率可能会降低。
- 开放定址法（Open Addressing）：在开放定址法中，发生冲突时会尝试在哈希表中的其他位置寻找空槽来存储元素，而不是通过链表进行链接。开放定址法有几种常见的策略，如线性探测（Linear Probing）、二次探测（Quadratic Probing）、双重哈希（Double Hashing）等。这些策略决定了当冲突发生时如何寻找下一个空槽。开放定址法的优点是避免了链表的额外存储开销，但是当哈希表填充度较高时，可能会导致连续的冲突，进而降低查找效率。
- 再哈希法（Rehashing）：使用不同的哈希函数来处理冲突。当发生冲突时，再哈希法会应用另一个哈希函数，重新计算一个新的索引位置，并将元素存储到新的位置上。再哈希法可以在发生冲突时提供更好的分散性，从而减少冲突的发生。然而，选择合适的再哈希函数并不容易，因为它需要满足良好的分布性和计算效率。
- 其他方法：如建立公共溢出区（Public Overflow Area）。
常用API：
- dict.get(key, 0)：获取指定key的value，如果没有这个返回0
- 关于set的API：union() 取并集，intersection() 取交集，difference() 取差集等。

set是一种无序的不重复的哈希集合。特殊的「有序集合/映射」：红黑树（一种平衡二叉搜索树），特性是自动维护其中元素的顺序，操作效率是 O(logN)。

力扣指南

哈希
题目	技巧	难度
✅1. 两数之和		🌟

链表

简介：链表是一种数据结构，由一系列节点组成，每个节点包含两部分，一个是数据，另一个是指向下一个节点的指针。
链表实现：在Python中，链表可以使用类和对象来实现。每个节点用一个类表示，节点之间的关系用指针来实现。
复杂度：一般递归法和迭代解法的时间复杂度都是 $O(N)$，但是迭代解法的空间复杂度是 $O(1)$，⽽递归解法需要堆栈，空间复杂度是 $O(N)$
优点：相比于数组，链表的优点是可以在任意位置插入和删除元素，不需要进行大量的数据搬移操作。
缺点：访问节点时需要遍历整个链表，访问效率较低。
分类：
- 单向链表是一种链表，每个节点都只包含指向下一个节点的指针。链表的头节点指向第一个节点，最后一个节点的指针指向空值（null），表示链表结束。单向链表的访问只能从头节点开始，依次向后遍历，不能反向遍历。
- 单向循环链表：每个节点都只包含指向下一个节点的指针，最后一个节点的指针指向第一个节点，形成一个环形结构。和单向链表类似，单向循环链表也只能从头节点开始遍历，不能反向遍历。
- 双向链表：每个节点都包含指向前一个节点和后一个节点的指针。双向链表的访问可以从头节点或尾节点开始，可以向前或向后遍历。
- 双向循环链表：每个节点都包含指向前一个节点和后一个节点的指针，最后一个节点的指针指向头节点，形成一个环形结构。双向循环链表的访问可以从头节点或尾节点开始，可以向前或向后遍历，也可以在任意位置插入和删除节点。

当你需要创造一条新链表的时候，可以使用虚拟头结点dummy简化边界情况的处理。

数据结构的存储⽅式只有两种：数组（顺序存储）和链表（链式存储）。二者的优缺点：

数组是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，相对节约存储空间。但正因为连续存储，内存空间必须⼀次性分配够，所以说数组如果要扩容，需要重新分配⼀块更⼤的空间，再把数据全部复制过去，时间复杂度 O(N)；在数组中间进⾏插⼊和删除，每次必须搬移后⾯的所有数据以保持连续，时间复杂度 O(N)。
链表元素不连续，靠指针指向下⼀个元素的位置，所以不存在数组的扩容问题；如果知道某⼀元素的前驱和后驱，操作指针即可删除该元素或者插⼊新元素，时间复杂度 O(1)。但是正因为存储空间不连续，⽆法根据⼀个索引算出对应元素的地址，所以不能随机访问；⽽且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

代码实现

class Node:
    def __init__(self, data=None, next=None, prev=None):
        self.data = data
        self.next = next
        # self.prev = prev  # 循环链表需要添加前向指针

class LinkedList:
    def __init__(self):
        self.head = None

    # 添加节点到链表尾部
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        # new_node.prev = last_node  # 循环链表

    # 插入节点到指定位置
    def insert(self, index, data):
        if index == 0:
            new_node = Node(data)
            new_node.next = self.head
            # self.head.prev = new_node
            self.head = new_node
            return
        new_node = Node(data)
        cur_node = self.head
        cur_index = 0
        while cur_node and cur_index < index - 1:
            cur_node = cur_node.next
            cur_index += 1
        if cur_node is None:
            raise Exception("Index out of range")
        new_node.next = cur_node.next
        # cur_node.next.prev = new_node
        cur_node.next = new_node
        # new_node.prev = cur_node

    # 删除指定位置的节点
    def delete(self, index):
        if self.head is None:
            raise Exception("List is empty")
        if index == 0:
            self.head = self.head.next
            return
        cur_node = self.head
        cur_index = 0
        while cur_node and cur_index < index - 1:
            cur_node = cur_node.next
            cur_index += 1
        if cur_node is None or cur_node.next is None:
            raise Exception("Index out of range")
        cur_node.next = cur_node.next.next

    # 获取指定位置的节点
    def get(self, index):
        if self.head is None:
            raise Exception("List is empty")
        cur_node = self.head
        cur_index = 0
        while cur_node and cur_index < index:
            cur_node = cur_node.next
            cur_index += 1
        if cur_node is None:
            raise Exception("Index out of range")
        return cur_node.data

    # 返回链表大小
    def size(self):
        cur_node = self.head
        size = 0
        while cur_node:
            size += 1
            cur_node = cur_node.next
        return size

    # 打印链表
    def __str__(self):
        cur_node = self.head
        linked_list = []
        while cur_node:
            linked_list.append(str(cur_node.data))
            cur_node = cur_node.next
        return "->".join(linked_list)

    # 清空链表
    def clear(self):
        self.head = None


# 创建链表并添加节点
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print(linked_list)  # 1->2->3->4

# 在指定位置插入节点
linked_list.insert(2, 5)
print(linked_list)  # 1->2->5->3->4

# 删除指定位置的节点
linked_list.delete(1)
print(linked_list)  # 1->5->3->4

# 获取指定位置的节点
print(linked_list.get(2))  # 3

# 返回链表大小
print(linked_list.size())  # 4

力扣指南

链表
题目	技巧	难度
✅83. 删除排序链表中的重复元素		🌟
❌✅92. 反转链表 II	迭代法还没做	🌟🌟
✅206. 反转链表	迭代和递归，双指针画个图	🌟
✅23. 合并 K 个升序链表	优先队列 / 归并排序	🌟🌟🌟
✅25. K 个一组翻转链表	迭代+递归	🌟🌟🌟
✅234. 回文链表		🌟