[数据结构与算法]PAT 2018年浙大复试机试

1 PAT 甲级 1144 The Missing Number

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int vec[N];
int main() {
    int n; cin>>n;
    for(int i=0; i<n; ++i) {
        cin>>vec[i];
    }
    for(int i=0; i<n; ++i) {
        if(vec[i]<=0 ||vec[i]>n){
            vec[i] = n+1;
        }
    }
    for(int i=0; i<n; ++i) {
        int hash_key = abs(vec[i]);
        if(hash_key != n+1) {
            if(vec[hash_key-1] > 0){
                vec[hash_key-1] *= -1;
            }
        }
    }
    int ans = n+1;
    for(int i=0; i<n; ++i) {
        if(vec[i]>0) {
            ans = i+1;
            break;
        }
    }
    cout<<ans<<"\n";
}

2 PAT 甲级 1145 Hashing - Average Search Time

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4+10;
int m_size, n, m;

bool IsPrime(int n) {
    if(n<=3) {
        return n>1;
    }
    int x = sqrt(n)+0.5;
    for(int i=2; i<=x; ++i) {
        if(n%i == 0) return false;
    }
    return true;
}

void AdjustToPrime(int &n){
    while(!IsPrime(n)) ++n;
}

int table[N];
void InitHashTable(){
    memset(table, -1, sizeof(table));
}
void Insert(int val) {
    int pos = val%m_size;
    for(int step = 0; step <= m_size; ++step) {
        pos = (val + step * step)%m_size;
        if(table[pos]==-1){
            table[pos] = val;
            return;
        }
    }
    printf("%d cannot be inserted.\n", val);
}

int Find(int val) {
    int cnt = 0;
    int pos = val%m_size;
    for(int step = 0; step <= m_size; ++step) {
        cnt += 1;
        pos = (val + step * step)%m_size;
        if(table[pos]==val || table[pos] == -1){
            break;
        }
    }
    return cnt;
}

int main() {
    cin>>m_size>>n>>m;
    AdjustToPrime(m_size);
    InitHashTable();
    while(n--){
        int key;
        cin>>key;
        Insert(key);
    }
    int tot_cnt = 0;
    for(int i=0; i<m; ++i){
        int key;
        cin>>key;
        tot_cnt += Find(key);
    }
    printf("%.1f\n", tot_cnt*1.0/m);
}

3 PAT 甲级 1146 Topological Order

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
set<int> to[N];
int in_degree[N];

int n, m;

bool JudgeHelper(vector<int> &seq, int begin) {
    if(begin == seq.size()) return true;
    int now = seq[begin];
    if(in_degree[now]!=0) return false;
    for(auto next: to[now]) {
        in_degree[next]--;
    }
    bool ans = JudgeHelper(seq, begin+1);
    for(auto next: to[now]) {
        in_degree[next]++;
    }
    return ans;
}

bool Judge(vector<int> &seq) {
    return JudgeHelper(seq, 0);
}

int main() {
    cin>>n>>m;
    for(int i=0; i<m; ++i) {
        int x, y; cin>>x>>y;
        to[x].insert(y);
        in_degree[y]++;
    }
    int k; cin>>k;
    vector<int> ans;
    for(int i=0; i<k; ++i) {
        vector<int> seq(n);
        for(int i=0; i<n; ++i) cin>>seq[i];
        if(!Judge(seq)){
            ans.push_back(i);
        }
    }
    for(int i=0; i<ans.size(); ++i){
        if(i!=0) cout<<" ";
        cout<<ans[i];
    }
}

4 PAT 甲级 1147 Heaps

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int m, n;
int tree[N];

int lchild(int pos) {
    int child = 2*pos + 1;
    return child>=n ? -1: child;
}

int rchild(int pos) {
    int child = 2*pos + 2;
    return child>=n ? -1: child;
}

void PostOrder(int idx, vector<int>& vec) {
    if(idx == -1) return;
    PostOrder(lchild(idx), vec);
    PostOrder(rchild(idx), vec);
    vec.push_back(tree[idx]);
}

bool IsMaxHeap(int idx) {
    if(lchild(idx) == -1) return true;
    if(rchild(idx) == -1) {
        return tree[idx]>=tree[lchild(idx)] && IsMaxHeap(lchild(idx));
    }
    return tree[idx]>=tree[lchild(idx)] &&
           tree[idx]>=tree[rchild(idx)] &&
           IsMaxHeap(lchild(idx)) &&
           IsMaxHeap(rchild(idx));
}

bool IsMinHeap(int idx) {
    if(lchild(idx) == -1) return true;
    if(rchild(idx) == -1) {
        return tree[idx]<=tree[lchild(idx)] && IsMinHeap(lchild(idx));
    }
    return tree[idx]<=tree[lchild(idx)] &&
           tree[idx]<=tree[rchild(idx)] &&
           IsMinHeap(lchild(idx)) &&
           IsMinHeap(rchild(idx));
}

int main() {
    cin>>m>>n;
    for(int i=0; i<m; ++i){
        for(int j=0; j<n; ++j) {
            cin>>tree[j];
        }
        if(IsMaxHeap(0)) printf("Max Heap\n");
        else if(IsMinHeap(0)) printf("Min Heap\n");
        else printf("Not Heap\n");
        vector<int> path;
        PostOrder(0, path);
        for(int i=0; i<path.size(); ++i) {
            if(i!=0) printf(" ");
            printf("%d", path[i]);
        }
        printf("\n");
    }
}