621题题意没读明白？
第一题、647.回文子串（中等）
方法一、中心拓展
计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：
枚举出所有的子串，然后再判断这些子串是否是回文；
枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。
class Solution:
def countSubstrings(self, s: str) -> int:
# 获取字符串s的长度
n = len(s)
# 初始化回文子串的计数器
ans = 0
# 遍历可能的中心点，中心点有2 * n - 1个
# 每个中心点表示一个可能的回文子串的中心
for i in range(0, 2 * n - 1):
# 左指针，向下取整i/2，表示当前回文中心的左侧
l = i // 2
# 右指针，(i//2 + i%2)，表示当前回文中心的右侧
r = i // 2 + i % 2
# 当左右指针没有超出字符串范围且左右字符相等时，扩展回文子串
while l >= 0 and r < n and s[l] == s[r]:
# 向外扩展，左指针向左移动，右指针向右移动
l -= 1
r += 1
# 回文子串计数器加1
ans += 1
# 返回回文子串的总数
return ans
时间复杂度：O(n^2 )。
空间复杂度：O(1)。
方法二、Manacher 算法（此思路作了解）
class Solution:
def countSubstrings(self, s: str) -> int:
# 获取字符串s的长度
n = len(s)
# 初始化t字符串，准备进行Manacher算法的预处理
t = "$#"
# 遍历字符串s中的每个字符c
for c in s:
# 在t中加入字符c，并在每个字符间加入分隔符#
t += c
t += '#'
# 更新n为预处理后的字符串t的长度
n = len(t)
# 在t末尾添加一个不同字符，避免越界
t += '!'
# 初始化回文半径数组f
f = [0] * n
# 初始化最远回文右边界rMax及其对应的中心iMax
iMax, rMax, ans = 0, 0, 0
# 遍历字符串t，从1开始到n-1（不包含首尾特殊字符）
for i in range(1, n):
# 初始化f[i]
if i <= rMax:
f[i] = min(rMax - i + 1, f[2 * iMax - i])
else:
f[i] = 1
# 中心拓展，扩展当前的回文半径f[i]
while t[i + f[i]] == t[i - f[i]]:
f[i] += 1
# 动态维护iMax和rMax
if i + f[i] - 1 > rMax:
iMax = i
rMax = i + f[i] - 1
# 统计答案：每个位置的贡献为(f[i] // 2)上取整
ans += f[i] // 2
# 返回回文子串的总数
return ans
时间复杂度：O(n)。即 Manacher 算法的时间复杂度，由于最大回文右端点 rm 只会增加而不会减少，故中心拓展进行的次数最多为 O(n)，此外只会遍历字符串一次，故总复杂度为 O(n)。
空间复杂度：O(n)。
第二题、76.最小覆盖子串（困难）
方法一、滑动窗口
本问题要求返回字符串 s 中包含字符串 t 的全部字符的最小窗口。称包含 t 的全部字母的窗口为「可行」窗口。
可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，就收缩窗口直到得到最小窗口。
如何判断当前的窗口包含所有 t 所需的字符呢？可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。
注意：这里 t 中可能出现重复的字符，所以要记录字符的个数。
from collections import defaultdict
class Solution:
def __init__(self):
# 初始化两个字典，ori存储目标字符及其数量，cnt存储当前窗口内的字符及其数量
self.ori = defaultdict(int)
self.cnt = defaultdict(int)
def check(self) -> bool:
"""
检查当前窗口内的字符数量是否满足目标字符数量要求。
"""
# 遍历目标字符字典ori中的每个字符和对应数量
for c in self.ori:
# 如果当前窗口内的字符数量小于目标字符数量，则返回False
if self.cnt[c] < self.ori[c]:
return False
return True
def minWindow(self, s: str, t: str) -> str:
# 初始化目标字符字典ori，记录t中每个字符的数量
for c in t:
self.ori[c] += 1
# 初始化双指针，l为左指针，r为右指针，初始位置为-1表示窗口为空
l, r = 0, -1
# 初始化最小窗口长度为无穷大，答案的左右边界为-1
len_min = float('inf')
ansL, ansR = -1, -1
# 开始滑动窗口
while r < len(s) - 1:
# 右指针右移一位，包含新的字符
r += 1
# 如果右指针指向的字符在目标字符字典ori中，更新当前窗口内字符数量
if s[r] in self.ori:
self.cnt[s[r]] += 1
# 检查当前窗口是否包含所有目标字符
while self.check() and l <= r:
# 如果当前窗口长度小于之前找到的最小长度，更新最小长度和答案边界
if r - l + 1 < len_min:
len_min = r - l + 1
ansL = l
ansR = r
# 左指针右移，移出左侧字符
if s[l] in self.ori:
self.cnt[s[l]] -= 1
l += 1
# 如果未找到满足条件的窗口，返回空字符串，否则返回最小窗口子串
return "" if ansL == -1 else s[ansL:ansL + len_min]
疑问：defaultdict是什么？
defaultdict 是 Python 的 collections 模块中的一个类，它是 dict（字典）的子类。与普通的字典不同，defaultdict 在访问不存在的键时不会引发 KeyError 异常，而是会根据提供的默认工厂函数自动为这个键创建一个默认值。
defaultdict 的语法是：
from collections import defaultdict
# 创建一个默认值为整数0的字典
d = defaultdict(int)
# 创建一个默认值为空列表的字典
d = defaultdict(list)
# 创建一个默认值为空字符串的字典
d = defaultdict(str)
当访问的键不存在时，defaultdict 会调用传入的默认工厂函数来生成一个默认值。这个默认值会被赋给这个键，并且字典会更新包含这个键值对。
from collections import defaultdict
# 创建一个默认值为0的字典
count = defaultdict(int)
# 当访问的键不存在时，默认值为0
count['a'] += 1
print(count['a']) # 输出: 1
# 如果访问一个不存在的键，直接返回默认值0
print(count['b']) # 输出: 0
# 创建一个默认值为空列表的字典
grouped_items = defaultdict(list)
# 向不存在的键添加元素时，会自动创建一个空列表
grouped_items['fruits'].append('apple')
print(grouped_items['fruits']) # 输出: ['apple']
# 访问一个不存在的键，返回一个空列表
print(grouped_items['vegetables']) # 输出: []
疑问：默认工厂函数是什么？
默认工厂函数（default factory function）是 defaultdict 用来生成默认值的函数。当访问一个 defaultdict 中不存在的键时，defaultdict 会调用这个默认工厂函数来生成一个默认值，并将其与该键关联。
在创建 defaultdict 时，需要传入一个可调用对象（函数）作为默认工厂函数。这个函数不需要参数，并且它的返回值就是 defaultdict 在访问不存在的键时所用的默认值。
from collections import defaultdict
# 默认工厂函数是 int
# 当访问的键不存在时，int() 返回 0
d = defaultdict(int)
print(d['a']) # 输出: 0
# 默认工厂函数是 list
# 当访问的键不存在时，list() 返回一个空列表
d = defaultdict(list)
print(d['a']) # 输出: []
# 默认工厂函数是 str
# 当访问的键不存在时，str() 返回一个空字符串
d = defaultdict(str)
print(d['a']) # 输出: ''
# 使用 lambda 函数作为默认工厂函数
# lambda: 42 返回 42
d = defaultdict(lambda: 42)
print(d['a']) # 输出: 42
常见的默认工厂函数：
-
int: 默认工厂函数是int时，defaultdict会为不存在的键生成0作为默认值。这在计数问题中很有用。 -
list: 默认工厂函数是list时，defaultdict会为不存在的键生成一个空列表[]作为默认值。这在需要将多个值聚合到一个键中的时候非常有用。 -
set: 默认工厂函数是set时，defaultdict会为不存在的键生成一个空集合set()作为默认值。 -
str: 默认工厂函数是str时，defaultdict会为不存在的键生成一个空字符串''作为默认值。 -
自定义函数或
lambda函数: 可以使用任何函数或lambda表达式作为默认工厂函数，这使得defaultdict非常灵活。
第三题、208.实现Trie（前缀树）
方法一、字典树
Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：
指向子节点的指针数组 children。对于本题而言，数组长度为 26，即小写英文字母的数量。此时 children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。
布尔字段 isEnd，表示该节点是否为字符串的结尾。
插入字符串：
从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
查找前缀：
从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。
class Trie:
def __init__(self):
# 初始化Trie（字典树）的根节点
# 用一个长度为26的数组来存储26个英文字母的子节点
self.children = [None] * 26
# 标记是否是一个单词的结尾
self.isEnd = False
def searchPrefix(self, prefix: str) -> "Trie":
# 查找给定前缀的节点
node = self # 从根节点开始
for ch in prefix:
# 将字符转换为数组索引
ch = ord(ch) - ord("a")
if not node.children[ch]: # 如果没有相应的子节点，前缀不存在
return None
node = node.children[ch] # 继续深入子节点
return node # 返回最后一个节点
def insert(self, word: str) -> None:
# 插入一个单词到Trie中
node = self # 从根节点开始
for ch in word:
# 将字符转换为数组索引
ch = ord(ch) - ord("a")
if not node.children[ch]: # 如果没有相应的子节点，则创建一个新节点
node.children[ch] = Trie()
node = node.children[ch] # 继续深入子节点
node.isEnd = True # 设置单词的结束标记
def search(self, word: str) -> bool:
# 在Trie中搜索一个完整的单词
node = self.searchPrefix(word) # 查找单词对应的前缀节点
# 如果前缀存在且是单词的结尾，则单词存在于Trie中
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
# 检查Trie中是否存在给定前缀
return self.searchPrefix(prefix) is not None # 前缀存在则返回True，否则返回False
第四题、130.被围绕的区域
本题给定的矩阵中有三种元素：
字母 X；
被字母 X 包围的字母 O；
没有被字母 X 包围的字母 O。
本题要求将所有被字母 X 包围的字母 O都变为字母 X 。
题目解释中提到：任何边界上的 O 都不会被填充为 X。 可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。可以利用这个性质判断 O 是否在边界上，具体地说：
对于每一个边界上的 O，以它为起点，标记所有与它直接或间接相连的字母 O；
最后遍历这个矩阵，对于每一个字母：
如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，将其还原为字母 O；
如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，将其修改为字母 X。
方法一、深度优先搜索
class Solution:
def solve(self, board: List[List[str]]) -> None:
# 如果棋盘为空，则直接返回
if not board:
return
# 获取棋盘的行数和列数
n, m = len(board), len(board[0])
def dfs(x, y):
# 深度优先搜索（DFS）函数，用于标记与边界相连的'O'区域
# 如果当前坐标超出边界或不是'O'，则直接返回
if not 0 <= x < n or not 0 <= y < m or board[x][y] != 'O':
return
# 将当前的'O'标记为'A'，表示已访问且是与边界相连的'O'
board[x][y] = "A"
# 递归搜索上下左右四个方向
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
# 从棋盘的四条边开始，进行DFS，将所有与边界相连的'O'标记为'A'
for i in range(n):
dfs(i, 0) # 左边界
dfs(i, m - 1) # 右边界
for i in range(m):
dfs(0, i) # 上边界
dfs(n - 1, i) # 下边界
# 遍历整个棋盘，将所有的'A'还原为'O'，而将其他的'O'（未与边界相连的）转换为'X'
for i in range(n):
for j in range(m):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。
方法二、广度优先搜索
class Solution:
def solve(self, board: List[List[str]]) -> None:
# 如果棋盘为空，则直接返回
if not board:
return
# 获取棋盘的行数和列数
n, m = len(board), len(board[0])
# 使用双端队列（deque）来进行广度优先搜索（BFS）
que = collections.deque()
# 将与边界相连的'O'添加到队列中，并标记为'A'
for i in range(n):
if board[i][0] == "O":
que.append((i, 0))
board[i][0] = "A" # 标记已访问的'O'为'A'
if board[i][m - 1] == "O":
que.append((i, m - 1))
board[i][m - 1] = "A"
for i in range(m):
if board[0][i] == "O":
que.append((0, i))
board[0][i] = "A"
if board[n - 1][i] == "O":
que.append((n - 1, i))
board[n - 1][i] = "A"
# 使用BFS扩展所有从边界开始的'O'区域
while que:
x, y = que.popleft()
# 遍历当前节点的四个方向
for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
# 如果新位置在边界内且为'O'，将其加入队列并标记为'A'
if 0 <= mx < n and 0 <= my < m and board[mx][my] == "O":
que.append((mx, my))
board[mx][my] = "A"
# 遍历棋盘，将所有'A'还原为'O'，将所有未标记的'O'变为'X'
for i in range(n):
for j in range(m):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。广度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为广度优先搜索的队列的开销。
第五题、36.有效的数独
方法、一次遍历
有效的数独满足以下三个条件：
同一个数字在每一行只能出现一次；
同一个数字在每一列只能出现一次；
同一个数字在每一个小九宫格只能出现一次。
可以使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数。只需要遍历数独一次，在遍历的过程中更新哈希表中的计数，并判断是否满足有效的数独的条件即可。
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = [[0] * 9 for _ in range(9)] # 用于记录每行中每个数字出现的次数
columns = [[0] * 9 for _ in range(9)] # 用于记录每列中每个数字出现的次数
subboxes = [[[0] * 9 for _ in range(3)] for _ in range(3)] # 用于记录每个3x3小数独中每个数字出现的次数
# 遍历整个9x9的数独棋盘
for i in range(9):
for j in range(9):
c = board[i][j] # 获取当前位置的字符
if c != '.': # 如果当前格子不是空的
index = int(c) - 1 # 将字符转换为数字索引（1-9映射到0-8）
# 更新当前数字在行、列和小数独中的出现次数
rows[i][index] += 1
columns[j][index] += 1
subboxes[i // 3][j // 3][index] += 1
# 如果当前数字在任意一个行、列或小数独中出现超过一次，则数独无效
if rows[i][index] > 1 or columns[j][index] > 1 or subboxes[i // 3][j // 3][index] > 1:
return False
# 如果所有检查都通过，则返回True表示数独有效
return True
时间复杂度：O(1)。数独共有 81 个单元格，只需要对每个单元格遍历一次即可。
空间复杂度：O(1)。由于数独的大小固定，因此哈希表的空间也是固定的。
第六题、191.位1的个数
方法一：循环检查二进制位
可以直接循环检查给定整数 n 的二进制位的每一位是否为 1。
具体代码中，当检查第 i 位时，可以让 n 与 2^i 进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。
class Solution:
def hammingWeight(self, n: int) -> int:
# 使用生成器表达式计算n的二进制表示中'1'的个数
ret = sum(1 for i in range(32) if n & (1 << i))
# 返回结果
return ret
时间复杂度：O(k)，其中 k 是 int 型的二进制位数，k=32。需要检查 n 的二进制位的每一位，一共需要检查 32 位。
空间复杂度：O(1)，只需要常数的空间保存若干变量。
方法二、位运算优化
class Solution:
def hammingWeight(self, n: int) -> int:
# 初始化计数器，记录二进制表示中'1'的个数
ret = 0
# 当n不为0时，持续循环
while n:
# n & (n - 1) 操作会将 n 的二进制表示中最低位的 '1' 变为 '0'
n &= n - 1
# 每执行一次上面的操作，ret 自增1，表示找到了一个 '1'
ret += 1
# 返回二进制表示中 '1' 的总个数
return ret
时间复杂度：O(logn)。循环次数等于 n 的二进制位中 1 的个数，最坏情况下 n 的二进制位全部为 1。需要循环 logn 次。
空间复杂度：O(1)，只需要常数的空间保存若干变量。
第七题、231.2的幂
一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1。
因此可以考虑使用位运算，将 n 的二进制表示中最低位的那个 1 提取出来，再判断剩余的数值是否为 0 即可。下面是两种常见的与「二进制表示中最低位」相关的位运算技巧。
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and (n & -n) == n
时间复杂度：O(1)。
空间复杂度：O(1)。
方法二、判断是否为最大 2 的幂的约数
class Solution:
BIG = 2**30
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and Solution.BIG % n == 0
时间复杂度：O(1)。
空间复杂度：O(1)。
第八题、190.颠倒二进制位
方法一、逐位颠倒
将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 rev 中。
代码实现中，每枚举一位就将 n 右移一位，这样当前 n 的最低位就是要枚举的比特位。当 n 为 0 时即可结束循环。
需要注意的是，在某些语言（如 Java）中，没有无符号整数类型，因此对 n 的右移操作应使用逻辑右移。
class Solution:
def reverseBits(self, n: int) -> int:
# 初始化rev为0，用于存储反转后的位
rev = 0
# 遍历32位整数的每一位
for i in range(32):
# 获取n的最低位（最右边一位），并将其左移到反转后的正确位置
rev |= (n & 1) << (31 - i)
# 右移n，丢弃已处理的最低位
n >>= 1
# 返回反转后的结果
return rev
时间复杂度：O(logn)。
空间复杂度：O(1)。
方法二、位运算分治
若要翻转一个二进制串，可以将其均分成左右两部分，对每部分递归执行翻转操作，然后将左半部分拼在右半部分的后面，即完成了翻转。
由于左右两部分的计算方式是相似的，利用位掩码和位移运算，可以自底向上地完成这一分治流程。
对于递归的最底层，需要交换所有奇偶位：
取出所有奇数位和偶数位；
将奇数位移到偶数位上，偶数位移到奇数位上。
类似地，对于倒数第二层，每两位分一组，按组号取出所有奇数组和偶数组，然后将奇数组移到偶数组上，偶数组移到奇数组上。以此类推。
需要注意的是，在某些语言（如 Java）中，没有无符号整数类型，因此对 n 的右移操作应使用逻辑右移。
class Solution:
# 定义掩码常量
M32 = 0xffffffff # 32位全1的掩码，用于确保结果在32位内
M1 = 0x55555555 # 掩码：01010101010101010101010101010101，用于交换相邻的位
M2 = 0x33333333 # 掩码：00110011001100110011001100110011，用于交换每两个位
M4 = 0x0f0f0f0f # 掩码：00001111000011110000111100001111，用于交换每四个位
M8 = 0x00ff00ff # 掩码：00000000111111110000000011111111，用于交换每八个位
def reverseBits(self, n: int) -> int:
# 交换相邻的位
n = ((n & self.M1) << 1) & self.M32 | ((n >> 1) & self.M1)
# 交换每两个位
n = ((n & self.M2) << 2) & self.M32 | ((n >> 2) & self.M2)
# 交换每四个位
n = ((n & self.M4) << 4) & self.M32 | ((n >> 4) & self.M4)
# 交换每八个位
n = ((n & self.M8) << 8) & self.M32 | ((n >> 8) & self.M8)
# 交换每16个位
n = (n << 16) & self.M32 | (n >> 16)
# 返回反转后的结果
return n
时间复杂度：O(1)。
空间复杂度：O(1)。
