基础数据结构模板(持续更新)

基础数据结构模板(持续更新),第1张

class="superseo">算法

文章目录
      • 算法
        • 数据结构
          • 并查集
          • 树状数组
        • 基础算法模板
          • 快排
          • 二分
          • 高精度加法
          • 差分
          • 位运算
          • 双指针
        • 动态规划
          • LIS
        • 数论
          • 质数
        • 图论
          • 树与图的储存
          • 树的遍历
          • 拓扑排序
        • Leetcode
          • 反转链表
          • 环形链表

数据结构 并查集
//朴素并查集
//存储每个点的祖宗节点
int p[N];
//返回x的祖宗节点
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初试化
for(int i=1;i<=n;i++) p[i]=i;
//合并两个集合
p[find(a)]=find(b);



//维护size的并查集
//p[]存储每个点的祖宗节点,size[]存储集合大小只有祖宗节点有意义
int p[N],size[N];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初始化
for(int i=1;i<=n;i++){
    p[i]=i;
    size[i]=1;
}
//合并两个集合
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);
	


//维护到祖宗节点的并查集


树状数组
int tr[N];

void lowbit(int x){
    return x&-x;
}
void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]+=c;
    }	
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(x)){
        res+=tr[i];
    }
    return res;
}
//初始化
memset(tr,0,sizeof(tr));
for(int i=1;i<=n;i++){
    add(i,num[i]);
}
基础算法模板 快排
void quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(ix);
        if(i
二分
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
//上升序列 返回第一个>=x的迭代器
lower_bound(nums.begin(),nums.end(),x);
//上升序列 返回第一个>x的迭代器
upper_bound(nums.begin(),nums.end(),x);

//下降序列 返回第一个<=x的迭代器
lower_bound(nums.begin(),nums.end(),x,greater());
//下降序列 返回第一个());
高精度加法 差分 位运算
int lowbit(int x) return x&-x;
//n的第k位数字
n >> k & 1
双指针 动态规划 LIS

朴素

f[i]:所有以a[i]结尾的上升子序列

属性:最长

状态计算: f[i]=max(f[i-1]+1,…f[1]+1,1)

#include
#include

using namespace std;

const int N=1010;
int a[N],f[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;ja[j]){
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,f[i]);
    }
    cout<
数论 质数

试除法

bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}

试除法分解质因数

void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            int s=0;
            while(x%i==0){
                x=x/i;
                s++;
            }
            cout<1){
        cout<
图论 树与图的储存
(1)邻接矩阵 g[a][b]=1  a->b
(2)邻接表
//h[k] 存储每个节点的头节点指针
int h[N],e[N],ne[N],idx;
//添加a->b
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
idx=0;
memset(h,-1,sizeof(h));
树的遍历
//深度优先遍历
int dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}
queue q;
void bfs(int u){
    q.push(u);
    st[u]=true;
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i!=-1;i=me[i]){
            int j=e[i];
            if(!st[j]) q.push(j);
        }
    }
}
拓扑排序
//拓扑排序
int d[N];
bool topsort(){
    int q[N];
    int hh=,tt-1;
    for(int i=0;i
Leetcode 反转链表
ListNode* reverseList(ListNode* head){
    ListNode* pre;
    ListNode* curr=head;
    while(curr){
        ListNode* ne=curr->next;
        curr->next=pre;
        pre=curr;
        curr=ne;
    }
    return pre;
}
环形链表
bool hasCycle(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return false;
        }
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(slow!=fast){
            if(fast==NULL||fast->next==NULL){
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/1499305.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-25
下一篇 2022-06-25

随机推荐

发表评论

登录后才能评论

评论列表(0条)