PAT (Advanced Level) 1144~1147：1145Hash二次探查 1146拓扑排序 1147堆

时间：2023-03-31 19:42:20
1144 The Missing Number（20 分）

题意：给定N个数的序列，输出不在序列中的最小的正整数。

分析：

1、给定的N个数可能为正，可能为负，可能重复。

2、由于N≤10​5​​,所以，当N个数互不重复，且都为正的情况下，所输出的数最大，为10​5​​+1。

3、将序列中的数标注后，枚举1~10​5​​+1，遇到的第一个未标注的数即为答案。

4、注意标注序列中的数时，大于10​5​​+1的数没必要标注（因为给定的数在int范围内），否则会下标越界。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<iostream>

using namespace std;

const int MAXN = 100000 + 10;

int a[MAXN];

bool vis[MAXN];

int main(){

    int N;

    while(scanf("%d", &N) == 1){

        memset(vis, false, sizeof vis);

        for(int i = 0; i < N; ++i){

            scanf("%d", &a[i]);

            if(a[i] > 0 && a[i] < MAXN) vis[a[i]] = true;

        }

        for(int i = 1; i < MAXN; ++i){

            if(!vis[i]){

                printf("%d", i);

                break;

            }

        }

    }

    return 0;

}

1145 Hashing - Average Search Time（25 分）

题意：给定N个数，插入到长度为MSize的哈希表中，计算查找M个数的平均查找时间。

分析：

1、哈希函数：H(key)=key%MSize

2、题目中要求通过二次探查法解决冲突，且只考虑正增量。

（1）二次探查法的探查序列为Hi=(H(key)+i)%MSize,i取值依次为1*1，-1*1，2*2，-2*2，3*3，-3*3，...，(MSize-1)*(MSize-1),-(MSize-1)*(MSize-1)

（2）由于只考虑正增量，所以i取值为1*1，2*2，3*3，...，(MSize-1)*(MSize-1)
（3）对于i依次取值来解决冲突，如果所有的取值都冲突，则插入失败。
3、查询某数时所执行的操作与插入操作相同，如果查询到的位置为空，则表示该数字不在Hash表中；如果遍历所有的i都未找到，则查询总数加1。
#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

using namespace std;

const int MAXN = 10000 + 10;

int MSize, N, M;

int Hash[MAXN];

bool judge_prime(int x){

    if(x <= 1) return false;

    for(int i = 2; i <= (int)(sqrt(x + 0.5)) + 1; ++i){

        if(x % i == 0) return false;

    }

    return true;

}

int main(){

    while(scanf("%d%d%d", &MSize, &N, &M) == 3){

        memset(Hash, -1, sizeof Hash);

        while(!judge_prime(MSize)) ++MSize;

        int key;

        while(N--){

            scanf("%d", &key);

            int Hkey = key % MSize;

            bool ok = false;

            if(Hash[Hkey] == -1){

                Hash[Hkey] = key;

                ok = true;

            }

            else{

                for(int i = 1; i <= MSize - 1; ++i){

                    int tmp = (Hkey + i * i) % MSize;

                    if(Hash[tmp] == -1){

                        Hash[tmp] = key;

                        ok = true;

                        break;

                    }

                }

            }

            if(!ok) printf("%d cannot be inserted.\n", key);

        }

        int x;

        int sum = 0;

        for(int i = 0; i < M; ++i){

            scanf("%d", &x);

            int Hkey = x % MSize;

            bool ok = false;

            for(int j = 0; j < MSize; ++j){

                int tmp = (Hkey + j * j) % MSize;

                ++sum;

                if(Hash[tmp] == -1 || Hash[tmp] == x){

                    ok = true;

                    break;

                }

            }

            if(!ok) ++sum;

        }

        printf("%.1lf\n", sum * 1.0 / M);

    }

    return 0;

}

1146 Topological Order（25 分）

题意：给定一个有向图，判断所给的K个选项中哪个不是该图的拓扑排序。

分析：

1、遍历所给的拓扑序，边遍历边将该点所指向的点入度-1。

2、在进行上述操作的前提下，如果遍历到的每个点入度都为0，则该序列一定是拓扑序。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<vector>

using namespace std;

const int MAXN = 1000 + 10;

vector<int> G[MAXN];

int indegree[MAXN];

int tmpindegree[MAXN];

vector<int> ans;

vector<int> v;

int N, M;

void init(){

    for(int i = 1; i <= N; ++i) G[i].clear();

    memset(indegree, 0, sizeof indegree);

    ans.clear();

}

bool judge(){//判断是否为拓扑序列

    int len = v.size();

    for(int i = 0; i < len; ++i){

        int cur = v[i];

        if(!tmpindegree[cur]){

            int l = G[cur].size();

            for(int j = 0; j < l; ++j){

                --tmpindegree[G[cur][j]];

            }

        }

        else return false;

    }

    return true;

}

int main(){

    while(scanf("%d%d", &N, &M) == 2){

        init();

        int st, ed;

        for(int i = 0; i < M; ++i){

            scanf("%d%d", &st, &ed);

            G[st].push_back(ed);

            ++indegree[ed];

        }

        int K, x;

        scanf("%d", &K);

        for(int i = 0; i < K; ++i){

            memcpy(tmpindegree, indegree, sizeof indegree);

            v.clear();

            for(int j = 0; j < N; ++j){

                scanf("%d", &x);

                v.push_back(x);

            }

            if(!judge()) ans.push_back(i);

        }

        int len = ans.size();

        for(int i = 0; i < len; ++i){

            if(i) printf(" ");

            printf("%d", ans[i]);

        }

        printf("\n");

    }

    return 0;

}

1147 Heaps（30 分）

题意：给定一个完全二叉树的层次遍历序列，问该二叉树是否为堆结构，并进一步判断是大顶堆还是小顶堆，最后输出该二叉树的后序遍历序列。

分析：

1、由于给定的N (1<N≤1000)个点数字各不相同，且大小都在int范围内，首先对N个点进行坐标离散化。

2、利用queue边读取边判断该二叉树是否为堆结构，同时记录每个点的左右子结点。

3、进行后序遍历。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

using namespace std;

const int MAXN = 100000 + 10;

int lchild[MAXN], rchild[MAXN];

map<int, int> mp1;

map<int, int> mp2;

queue<int> q;

vector<int> ans;

int root;

int cnt;

void init(){

    memset(lchild, 0, sizeof lchild);

    memset(rchild, 0, sizeof rchild);

    mp1.clear();

    mp2.clear();

    while(!q.empty()) q.pop();

    ans.clear();

}

void get_id(int x){//坐标离散化

    ++cnt;

    mp1[x] = cnt;

    mp2[cnt] = x;

}

int judge(int type_l, int type_r){

    if(type_l == 1 && type_r != 2){

        return 1;//Min Heap

    }

    else if(type_l == 2 && type_r != 1){

        return 2;//Max Heap

    }

    else{

        return 3;

    }

}

void print_postorder(int x){

    if(lchild[x]) print_postorder(lchild[x]);

    if(rchild[x]) print_postorder(rchild[x]);

    ans.push_back(mp2[x]);

}

int main(){

    int M, N;

    while(scanf("%d%d", &M, &N) == 2){

        while(M--){

            init();

            cnt = 0;

            int x;

            scanf("%d", &x);

            q.push(x);

            get_id(x);

            root = mp1[x];

            int type = 0;

            bool ok = true;

            while(!q.empty()){

                int top = q.front();

                q.pop();

                int type_l = 0;

                int type_r = 0;

                if(cnt < N){

                    scanf("%d", &x);

                    get_id(x);

                    lchild[mp1[top]] = mp1[x];

                    q.push(x);

                    if(top < x) type_l = 1;

                    else type_l = 2;

                }

                if(cnt < N){

                    scanf("%d", &x);

                    get_id(x);

                    rchild[mp1[top]] = mp1[x];

                    q.push(x);

                    if(top < x) type_r = 1;

                    else type_r = 2;

                }

                if(type == 0) type = judge(type_l, type_r);

                else{

                    int tmptype = judge(type_l, type_r);

                    if(tmptype != type || type == 3) ok = false;

                }

                if(cnt == N) break;

            }

            if(!ok) printf("Not Heap\n");

            else{

                if(type == 1) printf("Min Heap\n");

                else printf("Max Heap\n");

            }

            print_postorder(root);

            int len = ans.size();

            for(int i = 0; i < len; ++i){

                if(i) printf(" ");

                printf("%d", ans[i]);

            }

            printf("\n");

        }

    }

    return 0;

}

相关文章