前缀和
- 简介：前缀和算法是一种常见的数组处理算法，通过预处理出数组的前缀和（Prefix Sum），可以在$O(1)$时间内快速求出任意区间的和。
- 计算方式：对于一个长度为n的数组a，其前缀和数组prefix_sum的第i个元素表示a数组中前i-1个元素的和，计算公式为
prefix_sum[i+1] = prefix_sum[i] + a[i]。初始化prefix_sum=[0]*(len(a)+1)。
- 使用前缀和算法求解区间和：假设要求区间[l,r]的和，可以通过计算
prefix_sum[r+1]-prefix_sum[l]来得到区间和。这是因为prefix_sum[r+1]表示a数组前r个元素的和，prefix_sum[l]`表示a数组前l-1个元素的和，两者相减即可得到区间[l,r]的和。
- 应用场景：处理数组序列问题，如求解子数组的和、平均数、中位数等。也可以用于处理二维矩阵中的子矩阵问题。
- 时间复杂度：预处理时间复杂度为$O(n)$，求解区间和的时间复杂度为$O(1)$，因此总的时间复杂度为$O(n)$。
算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def prefix_search(self, k: int, nums: List[int]) :
pre_sum = [0] * (len(nums) + 1)
for i in range(len(nums)):
pre_sum[i+1] = pre_sum[i] + nums[i]
for i in range(len(nums) + 1):
dict[pre_sum[i]] += 1
target = pre_sum[i] - k
if target in dict:
ans...
|
二维前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
| class MatrixSum:
def __init__(self, matrix):
m, n = len(matrix), len(matrix[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(matrix):
for j, x in enumerate(row):
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x
self.s = s
def query(self, r1, c1, r2, c2):
return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]
|
【图解】二维前缀和
力扣指南
前缀树
前缀树，也称为字典树（Trie）或键树，是一种用于有效存储和检索字符串集合的树形数据结构。前缀树的主要特点是将共同的前缀存储在树的相同深度上，从根节点到每个叶子节点都表示一个字符串。这使得前缀树非常适合用于字符串匹配、前缀匹配和字典查询等应用。
- 基本思想：利用共享的前缀信息，将字符按照从根节点到叶子节点的路径组织起来。根节点表示空字符串，每个非根节点表示一个字符。从根节点到叶子节点的路径上，经过的字符连接起来就是一个完整的字符串
- TrieNode节点本身只存储val字段，并没有一个字段来存储字符，字符是通过子节点在父节点的children数组中的索引确定的。
形象理解就是，Trie 树用「树枝」存储字符串（键），用「节点」存储字符串（键）对应的数据（值）。
算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| class Trie:
def __init__(self):
self.children = [None] * 26
self.isEnd = False
def searchPrefix(self, prefix) -> 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:
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 remove(self, word) -> None:
def searchWordPrefix(self, word) -> str:
node = self
prefix = ''
for ch in word:
idx = ord(ch) - ord('a')
if node.isEnd == True:
return prefix
if node.children[idx] is None:
return None
prefix += ch
node = node.children[idx]
def search(self, word: str) -> bool:
node = self.searchPrefix(word)
return node is not None and node.isEnd
def search(self, word: str) -> bool:
def dfs(i, node):
if i == len(word):
return node.isEnd
if word[i] != '.':
ch = ord(word[i]) - ord('a')
if not node.children[ch]:
return False
return dfs(i + 1, node.children[ch])
else:
for child in node.children:
if child is not None and dfs(i + 1, child):
return True
return False
return dfs(0, self.trie)
def startsWith(self, prefix: str) -> bool:
return self.searchPrefix(prefix) is not None
|
力扣指南
差分数组
差分数组（Difference Array）是一种常用的数据结构和算法，用于高效地处理数组区间的修改操作。差分数组可以将原始数组的部分元素的差值存储在新的数组中，从而实现在常数时间内对原数组区间进行修改和查询。知识点：
- 原理：通过记录相邻元素之间的差值，将原始数组的修改操作转化为对差分数组的修改操作。通过修改差分数组，可以实现在常数时间内对原数组的区间进行增减操作。差分数组的元素值表示原始数组对应位置的增减值。
- 构建：遍历原始数组，计算相邻元素之间的差值，并将差值存储在差分数组中。时间复杂度为
O(N)，其中N是原始数组的长度。
- 区间修改和查询：对原数组的区间
[l, r]进行增加k的操作，只需要在差分数组中修改差分数组的[l]和[r+1]两个位置分别增加k和减去k：diff[l]+ k; diff[r+1]-=k。对原数组的区间进行查询，只需要查询差分数组的前缀和即可得到原数组的区间和。
- 应用：频繁对原始数组的某个区间的元素进行增减。例如区间加减操作、区间查询等。常见的应用包括求解数组区间的前缀和、动态区间修改等。
- 注意：使用差分数组时，需要注意边界条件和数组越界问题。在进行查询操作时，需要注意计算差分数组的前缀和时的下标范围。
算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Difference:
def __init__(self, nums: List[int]):
assert len(nums) > 0
self.diff = [0] * len(nums)
self.diff[0] = nums[0]
for i in range(1, len(nums)):
self.diff[i] = nums[i] - nums[i - 1]
def increment(self, i: int, j: int, val: int) -> None:
self.diff[i] += val
if j + 1 < len(self.diff):
self.diff[j + 1] -= val
def result(self) -> List[int]:
res = [0] * len(self.diff)
res[0] = self.diff[0]
for i in range(1, len(self.diff)):
res[i] = res[i - 1] + self.diff[i]
return res
|
力扣指南
