常见数据结构（八）
常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
最近在刷力扣的时候，有一道题：14. 最长公共前缀， 可以用 python3 的特殊 api 来求解，像是用 zip 函数，将可迭代对象对应的元素打包成一个个元组，然后返回元组组成的列表。我们就可以根据元组的长度来判断是否前缀是否相同。
比如
zip(['flower', 'flow', 'flight'])返回的结果是[('f', 'f', 'f'),('l', 'l', 'l'),('o', 'o', 'i'),('w', 'w', 'g')]
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
ans = zip(*strs) # List[Tuple]
s = ''
for i in ans:
if len(set(i)) == 1:
s += i[0]
else:
break # 后面能匹配上也不要了
return s但是看很多题解都是使用 trie 树来求解的，这里就来仔细的学习了解一下。 参考 labuladong 网站文章： 前缀树算法模板秒杀五道算法题
一、前缀和
真的是，前面的回溯算法还没有看，这有来一个前缀和的算法，难受。
原文章地址：小而美的算法技巧：前缀和数组
简单理解，就是用前面已经算好的前缀加上当前元素的值作为当前元素的前缀和，比如 nums = [2,3,5,1],
preSum = [2, ....]， 只算出来第一个值，这个时候要算第二个值的话，就可以用 preSum[i-1] + nums[i]来计算。
class NumArray {
private int[] preSum;
public NumArray(int[] nums) {
preSum = new int[nums.length+1];
for(int i=1;i<preSum.length;i++){
preSum[i] = preSum[i-1] + nums[i-1]; // 为啥是i-1， 因为是从i开始的，方便计算总和
}
}
public int sumRange(int left, int right) {
return preSum[right+1] - preSum[left]; // 为什么是right+1?因为要取到right这个值， 为什么不去到left？因为要留下left对应的值
}
}20240318 更新
今天力扣的每日一题是关于前缀和的，正好来更新一下自己关于前缀和的知识储备。
还是上面说的那一道题。如果我们用常规的方法的话，我们需要再 sumRange 里面定义一个循环来求 nums[left] 到 nums[right]之间的和。
前缀和正好就是求数组某一段的和。我们来仔细阅读一下上面的解题代码。
private int[] preSum;
public NumArray(int[] nums) {
preSum = new int[nums.length+1];
}定义一个 perSum 的数组，用来存放每个位置的前缀和，perSum 的长度比 num 的长度长一位，用来存放 0.
for(int i=1;i<preSum.length;i++){
preSum[i] = preSum[i-1] + nums[i-1];
}理解 perSum[0] = 0 是 base case，后面的 perSum[i] 就根据前面的 perSum[i-1] 和 nums[i-1] 来计算， 这里很好理解，就是根据前面一个 perSum 和 perSum[i]对应的 nums 来计算，因为 perSum 和 nums 有一个下标偏移。
public int sumRange(int left, int right) {
return preSum[right+1] - preSum[left];
}最后取[left, right]之间的和下标为什么取 right+1, 左边为什么不加一？
这里的 left 和 right 是相对于 nums 来说的，我们要在 perSum 里面计算，他们两个有一个下标的偏移，所以这里 right 要取 right+1。
left 的话，因为也是闭区间，left 下标的值也是要取到，如果是 left+1 的话，就把 left 也减掉了。
LCR 010. 和为 K 的子数组
给定一个整数数组和一个整数 k，请找到该数组中和为 k 的连续子数组的个数
子数组是数组中元素的连续非空序列。
前缀和+哈希解决。
维护列表的前缀和数组 pre，我们只需要在 pre 里面找到 pre[i]-k 的值有多少个，就是最后返回的结果。
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length, ans = 0;
int[] pre = new int[n+1];
for(int i = 1;i<pre.length;i++){
pre[i] = pre[i-1] + nums[i-1];
}
HashMap<Integer, Integer> mp = new HashMap<>();
mp.put(0, 1);
for(int i = 1;i<pre.length;i++){
int dif = pre[i] - k;
// 看mp里面有几个dif
ans += mp.getOrDefault(dif, 0);
// 更新mp中pre[i]的个数 pre[i]有几个 pre[i]-k就有几个
mp.put(pre[i], mp.getOrDefault(pre[i], 0)+1);
}
return ans;
}
}二、单调栈
今天了解到一个新的有用的解题数据结构，单调栈， 下面来具体学习一下。
设计到的相关题目：
下一个更高温度出现在几天后？ [1,1,0,0]
下一个更高温度是多少度？[60, 70, 0, 0]
三、并差集
Disjoint Set 并查集
图中是否有环
压缩轮径
find
Union
547. 省份数量
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFind uf = new UnionFind(n);
for(int i =0;i<n;i++){
for(int j = i;j<n;j++){
if(isConnected[i][j] == 1){
uf.union(i, j);
}
}
}
return uf.size;
}
}
class UnionFind{
int[] roots;
int size;// 连通图的个数
public UnionFind(int n){
roots = new int[n];
size = n;
for(int i =0;i<n;i++){
roots[i] = i;
}
}
public int find(int i){
if(i == roots[i]){
return i;
}
roots[i] = find(roots[i]);
return roots[i];
}
public void union(int x, int y){
int xroot = find(x);
int yroot = find(y);
if ( xroot == yroot){
return;
}
roots[yroot] = xroot;
size--;
}
}