启发式|前缀和

lc2424

单指针

用一个布尔数组标记已上传的视频，每次上传后更新当前连续上传前缀的最大长度，直接返回这个长度即可

class LUPrefix {
public:
int n;
bool * visited;
int ID;

LUPrefix(int n) {
this->n = n;
visited = new bool[n + 1];
for (int i = 0; i < n + 1; i ++){
visited[i] = false;
}
ID = 0;
}

void upload(int video) {
visited[video] = true;
while (ID + 1 <= n && visited[ID + 1] == true)
ID ++;
}

int longest() {
return ID;
}
};

按秩合并是启发式合并在并查集里的具体实现

按秩合并的“秩”（通常是树的高度或节点数）是启发式合并选择合并方向的核心依据，本质是通过让小树合并到大树下，避免并查集退化成链表，保证操作的时间复杂度接近常数

class DSU {

private:

vector<int> parent;

vector<int> rank;

public:

DSU(int n) {

parent.resize(n);

rank.resize(n, 1);

for (int i = 0; i < n; i++) parent[i] = i;

}

int find(int x) {

if (parent[x] != x) parent[x] = find(parent[x]);

return parent[x];

}

void unite(int x, int y) {

int fx = find(x), fy = find(y);

if (fx == fy) return;

if (rank[fx] < rank[fy]) parent[fx] = fy;

else {

parent[fy] = fx;

if (rank[fx] == rank[fy]) rank[fx]++;

}

}

};

lc1292

二维前缀和

预处理: sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];

求解: int t = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];

二维前缀和快速计算矩阵内正方形子矩阵的和，遍历所有可能的正方形，找出不超过阈值的最大边长

class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold)
{
vector<vector<int>> sum;
int m = mat.size(), n = mat[0].size();
sum.resize(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
}
}
int mx=0;
for(int r1=0;r1<m;r1++)
{
for(int c1=0;c1<n;c1++)
{
for(int k=mx+1; r1+k<=m && c1+k<=n; k++)
{
int r2 = r1 + k, c2 = c1 + k;
int t = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
if(t <= threshold)
mx = k;
else
break;
}
}
}
return mx;
}
};