本文介绍: 部分数据结构加部分图论

目录

一、trie树

题目描述:

输入格式

输出格式

输入样例:

输出样例:

①、思路

②、代码实现

二、并查集

1、样例

题目描述:

输入格式

输出格式

输入样例:

输出样例:

①、思路

②、代码实现

2、应用并查集

题目描述:

输入格式

输出格式

数据范围

输入样例:

输出样例:

①、思路

②、代码

三、堆排序

题目描述:

输入格式

输出格式

数据范围

输入样例:

输出样例:

①、思路

②、代码

四、模拟哈希表

1、离散化

题目描述:

输入格式

输出格式

数据范围

输入样例:

输出样例:

①、思路

②、代码

2、模拟散列表

题目描述:

输入格式

输出格式

数据范围

输入样例:

输出样例:

①、思路

1、拉链法

2、开放寻址法

五、图论

Ⅰ、树与图的遍历

①、深度优先遍历

②、广度优先遍历

Ⅱ、拓扑排序(有向图)

六、最短路径(图论)

Ⅲ、dijkstra算法

①、dijkstraⅠ(朴素算法)

②、dijkstraⅡ(优先队列优化)

Ⅳ、bellman – ford算法


一、trie树

题目描述:

维护一个字符串集合,支持两种操作:

  1. I x 向集合中插入一个字符串 x;
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作,所有输入的字符串总长度不超过 105105,字符串仅包含小写英文字母。

输入格式

第一行包含整数 N,表示操作数。

接下来 N 行,每行包含一个操作指令,指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x 在集合中出现的次数。

每个结果占一行。

输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1

①、思路

trie树就是可以查询字符串出现次数的一种结构,我们使用数组实现。idx用来区分每个结点,使得每个节点的值不相同,cnt表示每个字符串的末尾,从而记录没个字符串出现过几次,son[i][j]表示i结点指向j结点,同时其值就是j结点本身的值,p用来遍历过程中的结点路径。

②、代码实现

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

char st[N];
int cnt[N], idx, son[N][27];

void insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p] ++;
}


int query(char *str)
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在,即该字符串不存在
        p = son[p][u]; 
    }
    return cnt[p];  //返回字符串出现的次数
}


int main()
{
    int n;scanf("%d", &n);
    while( n -- )
    {
        char op[2];
        scanf("%s %s", &op, &st);
        if(op[0] == 'I') insert(st);
        else printf("%dn", query(st));
    }
    return 0;
}

二、并查集

1、样例

题目描述:

一共有 n 个数,编号是 1∼n1∼,最开始每个数各自在一个集合中。

现在要进行 m个操作,操作共有两种:

  1. M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
  2. Q a b,询问编号为 a和 b的两个数是否在同一个集合中;
输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b,都要输出一个结果,如果 a和 b 在同一集合内,则输出 Yes,否则输出 No

每个结果占一行。

输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes

①、思路

核心代码

int find(int n)
{
    if(p[n] != n) p[n] = find(p[n]);
    return p[n];
}

原理时p[ i ]就表示i的祖先,只有祖先才是i = p[i]。

初始化时,每个人都是自己的祖先,也就是一开始相互独立。

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

我们模拟一下案例,

M 1,2时,p[find(a)] = find(b)    =》  p[a] = b,p[b] = b。

Q1,2时,find(a) 第一步,p[a] = b   != a,因此继续找,find(p[a])。最后p[b] = b。返回b。

find(b) 直接返回b。最后相同,所以输出Yes。

②、代码实现

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N];//p[]表示每个数的祖宗节点。

int find(int n)
{
    if(p[n] != n) p[n] = find(p[n]);
    return p[n];
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0; i<n; i++) p[i] = i;
    
    while( m -- )
    {
        char arr[2];
        scanf("%s", arr);
        int a, b;cin>>a>>b;
        if(arr[0] == 'M') p[find(a)] = find(b);
        else {
            if(find(a) == find(b)){
                printf("Yesn");
            }
            else printf("Non");
        }
    }
    
    return 0;
}

2、应用并查集

题目描述:

给定一个包含 n 个点(编号为 1∼n1∼)的无向图,初始时图中没有边。

现在要进行 m 个操作,操作共有三种:

  1. C a b,在点 a和点b之间连一条边,a 和 b 可能相等;
  2. Q1 a b,询问点 a 和点 b 是否在同一个连通块中,a 和 b 可能相等;
  3. Q2 a,询问点 a 所在连通块中点的数量;
输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 C a bQ1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b,如果 a 和 b 在同一个连通块中,则输出 Yes,否则输出 No

对于每个询问指令 Q2 a,输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例:
Yes
2
3

①、思路

本题是个图类问题,但是我们可以用并查集思路求解,我们设定一个sz数组,存储每个块中的结点数量。同时让每个在块内的结点直接指向最高的祖先。便可以求得节点数量。

②、代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
#include<string>
int p[N], sz[N];//p[]表示每个数的祖宗节点。

int find(int n)
{
    if(p[n] != n) return p[n] = find(p[n]); 
    return p[n];
}

void merge(int a, int b)
{
    int x = find(a);
    int y = find(b);
    p[x] = y;
    sz[y] += sz[x];
}

bool ask(int a, int b)
{
    return find(a) == find(b);
}

int main()
{
    int n,m; cin>>n>>m;
    for(int i = 0; i<n; i++){
        p[i] = i;
        sz[i] = 1;
    }
    while( m -- )
    {
        int a, b; 
        string str;
        cin>>str;
        if(str == "C"){
             scanf("%d %d", &a, &b);
             if(!ask(a, b)) merge(a, b);
        }
        else if(str == "Q1"){
            scanf("%d %d", &a, &b);
            ask(a, b) ? printf("Yesn") : printf("Non");
        }
        else {
            scanf("%d", &a);
            printf("%dn", sz[find(a)]);
        }
        
    }
    
    return 0;
}

三、堆排序

题目描述:

输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

输出格式

共一行,包含 m 个整数,表示整数数列中前 m 小的数。

数据范围

1≤m≤n≤1e5
1≤数列中元素≤1e9

输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3

①、思路

堆排序,本身就是一种数组,但是排序的时候就是,一种模拟树状结构,通过比较,选出该部分最小的数,并放到最前面,反复进行。从而达到排序的效果。每次将最小数打印之后,再将最后面的数放到最前面然后继续排序。

②、代码

#include<iostream>
using namespace std;
#include<algorithm>
const int N = 1e5 + 10;
int arr[N], sz;

void down(int u)
{
    int t = u;
    if(2 * u <= sz && arr[t] > arr[2 * u]) t = 2 * u;
    if(2 * u + 1 <= sz && arr[t] > arr[2 * u + 1]) t = 2 * u + 1;
    
    if(t != u)
    {
        swap(arr[t], arr[u]);
        down(t);
    }
}

int main()
{
    int n, m;cin>>n>>m;
    sz = n;
    for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);
    for(int i = n / 2; i > 0; i--) down(i);
    while( m -- )
    {
        cout<<arr[1]<<" ";
        arr[1] = arr[sz -- ];
        down(1);
    }
    
    return 0;
}

四、模拟哈希表

1、离散化

题目描述:

假定有一个无限长的数轴,数轴上每个坐标上的数都是 00。

现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。

接下来,进行 m次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r]之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行,每行包含两个整数 x 和 c。

再接下来 m 行,每行包含两个整数 l 和 r。

输出格式

共 m 行,每行输出一个询问中所求的区间内数字和。

数据范围

−1e9≤x≤1e9
1≤n,m≤1e5
−1e9≤l≤r≤1e9
−10000≤c≤10000

输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5

①、思路

离散化,就是对于特别大范围的数进行优化的一种操作,将他们都对应到小的范围,从而实现求解。本题就是将所有坐标都存起来,然后将重复坐标全部去除,再利用二分方法,求出对应的离散化坐标。然后利用前缀和进行求解。

②、代码

#include<iostream>
#include<vector>
using namespace std;
#include<algorithm>
const int N = 300010;
int a[N],s[N];
int n,m;
vector<int> alls;
vector<pair<int,int>> add,query;

int find(int x)
{
    int l = 0;int r = alls.size()-1;
    while(l<r)
    {
        int mid = l+r>>1;
        if(alls[mid]>=x) r = mid;
        else
        l = mid+1;
    }
    return r+1;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++)
    {
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);
    }
    
    for(int i = 0;i<m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    //去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    //处理输入
    for(auto item :add)
    {
        int x = find(item.first);
        a[x]+=item.second;
    }

    //构建前缀和数组
    for(int i = 1;i<=alls.size();i++) s[i] = s[i-1]+a[i];

    //
    for(auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        printf("%dn",s[r]-s[l-1]);
    }
    
}

2、模拟散列表

题目描述:

维护一个集合,支持如下几种操作:

  1. I x,插入一个整数 x;
  2. Q x,询问整数 x 是否在集合中出现过;

现在要进行 N 次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N,表示操作数量。

接下来 N 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1≤N≤1e5
−109≤x≤1e9

输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No

①、思路

1、拉链法

拉链法,就是利用邻接表存储,其中将目标数字通过取余1e5 + 3。从而求解。

具体代码如下。

代码实现

#include<iostream>
#include<cstring>
using namespace std;
#include<string>
const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x)
{
    int k = (x % N + N) % N;//次数因为c++取余运算可能有负数,因此这样操作。
    for(int i = h[k]; i != -1; i = ne[i]){
        if(e[i] == x) return true;
    }
    return false;
}

int main()
{
    int n; cin>>n;
    memset(h, -1, sizeof(h));
    while(n -- )
    {
        string op; int x;
        cin>>op>>x;
        if(op == "I"){
            insert(x);
        }
        else {
            if(find(x)){
                printf("Yesn");
            }
            else {
                printf("Non");
            }
        }
    }
    return 0;
}

2、开放寻址法

这种方法,就是通过不断遍历,如果遍历到头就返回0重新遍历,然后直到找到目标值,如果为空,说明该位置就是应该被插入值的地方。

代码实现

#include<iostream>
#include<cstring>
using namespace std;


const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3f
int n;

int h[N];

int find(int x) {
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x) {
        t++;
        if (t == N) {
            t = 0;
        }
    }
    return t;  //如果这个位置是空的, 则返回的是他应该存储的位置
}


int main() {
    cin >> n;

    memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3f

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            h[find(x)] = x;
        } else {
            if (h[find(x)] == null) {
                puts("No");
            } else {
                puts("Yes");
            }
        }
    }
    return 0;
}

五、图论

Ⅰ、树与图的遍历

①、深度优先遍历

题目链接:树与图的重心

思路:

本题首先使用邻接表将所有结点都连在一起,然后深度遍历时有两个变量,res和sum,sum表示以当前节点作为重心,其它所有分支的和,res表示分支里面数量最多的分支,

ans作为最终结果,它表示,所有最大连通子路里面的最小值。

代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = N * 2;
int h[N], n, ans = N;
int e[M], ne[M], idx;
bool st[N];

void add(int a, int b)
{
    e[idx] = b;ne[idx] = h[a]; h[a] = idx ++;
}

int dfs(int u)
{
    int res = 0;
    st[u] = true;
    int sum = 1;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    
    res = max(res, n - sum);
    ans = min(res, ans);
    
    return sum;
}

int main()
{
    memset(h, -1, sizeof(h));
    cin>>n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        add(a, b); add(b, a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

②、广度优先遍历

题目链接:图中点的层次

思路:

本题使用邻接表进行存储,然后层序遍历时,使用队列进行遍历,然后d数组用来存储每个点到根节点的距离,最后返回dp[ n ],代表n到1的距离。

代码:

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

int n, m;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int d[N];

void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

int bfs()
{
    memset(d, -1, sizeof(d));
    
    queue<int> q;
    d[1] = 0;
    q.push(1);
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
           int j = e[i];
           if(d[j] == -1)
           {
               d[j] = d[t] + 1;
               q.push(j);
           }
        }
    }
    return d[n];
}

int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++){
        int a, b;cin>>a>>b;
        add(a, b);
    }
    
    cout<<bfs()<<endl;
    return 0;
}

Ⅱ、拓扑排序(有向图)

题目链接:拓扑排序

思路:

我们使用数组模拟一个队列q,然后我们将入度为0的点放在队列里,同时删除这个点对应的边,最后依次输出q这个数组,就可以了。

代码:

#include<iostream>
using namespace std;
#include<cstring>
const int N = 1e5 + 10;
int e[N], ne[N], h[N],idx;
int n, m;
int q[N], hh = 0, tt = -1;
int  d[N];//保存每个点的入度

void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

void topsort()
{
    for(int i = 1; i <= n; i++){
        if(d[i] == 0)
        q[++tt] = i;
    }
    
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j] == 0)
            {
                q[++tt] = j;
            }
            
        }
    }
    
    if(tt == n - 1)
    {
        for(int i = 0; i<n; i++) cout<<q[i]<<" ";
    }
    else puts("-1");
    
}

int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof(h));
    while( m -- )
    {
        int x, y;cin>>x>>y;
        d[y] ++;
        add(x, y);
    }
    topsort();
    return 0;
}

六、最短路径(图论)

Ⅲ、dijkstra算法

①、dijkstraⅠ(朴素算法)

题目链接:disktra求最短路Ⅰ

思路:

本题使用dijkstra的思路是,每个最短路径都取离起点距离最小的,然后用t更新节点坐标,遍历过的用true标记,表示已经遍历过了。最后返回dist[ n ]表示n到1的最短路径。

代码:

#include<iostream>
using namespace std;
#include<cstring>
const int N = 510;
int n, m;
int g[N][N], dist[N];//g表示x到y的权重,dist[N]表示点N对第一个点的最短距离。
bool st[N];

int Dijkstra()
{
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 0; i<n; i++){
        int t = -1;
        
        for(int j = 1; j <= n; j++){
            if(!st[j] && (t == -1 || dist[t] > dist[j])){
                t = j;
            }
        }
        st[t] = true;
        
        for(int j = 1; j <= n; j++){
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    
      if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    memset(g, 0x3f3f3f3f, sizeof(g));
    cin>>n>>m;
    while( m -- )
    {
        int x, y, z;
        cin>>x>>y>>z;
        g[x][y] = min(g[x][y], z);
    }
    
    cout<<Dijkstra()<<endl;
    return 0;
}

②、dijkstraⅡ(优先队列优化)

题目链接:disktra求最短路Ⅱ

思路:

本题稀疏表,因此使用邻接表存储,同时,遍历与上面基本相同,但是在基础上新加了优先队列的优化,优先队列自动排序,然后就可以降低时间复杂度到o(m log n)。

代码:

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int e[N], ne[N], h[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++;
}

int dijkstra()
{
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    
    while(heap.size())
    {
        PII k = heap.top();
        heap.pop();
        int ver = k.second; int distance = k.first;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof(h));
    while( m -- )
    {
        int x, y, z;
        cin>>x>>y>>z;
        add(x, y, z);
    }
    
    cout<<dijkstra()<<endl;
    return 0;
}

Ⅳ、bellman – ford算法

题目链接:bellman-ford算法

思路:

两层for循环,第一层是最多k次,然后循环k,之后的遍历每条边,更新最小值,然后我们的back数组是用来保存上一层的状态,防止回权部分有重边。每条边,我们使用一个结构体存储。

代码:

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可

int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -2;
    else return dist[n];

}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -2) puts("impossible");
    else cout << res;

    return 0;
}

原文地址:https://blog.csdn.net/su_xu_chao/article/details/135927293

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_63717.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注