PAT總結(jié)

PAT中常用的STL容器

順序容器

vector

#include<vector>
using namespace std;
vector<DataType> v;
v.push_back(Data);    //尾部添加元素
int size = v.size(); //元素個數(shù)
bool isEmpty = v.empty(); //是否為空
v.pop_back(); //刪除末尾元素
v.clear(); //清空元素
//遍歷
int length = v1.size();
for(int i=0;i<length;i++)
{
    cout<<v[i];
}

queue

#include<queue>
queue<Datatype> q;
q.push(Data); //入隊
q.pop(); //?隊首出隊
q.front(); //隊首元素
q.back(); //隊尾元素
q.empty(); //判斷隊列是否為空
q.size(); //隊列元素個數(shù)

priority_queue

#include <iostream>
#include <queue>
using namespace std;
struct cmp{
    bool operator()(int a,int b){
    return a>b;
    }
};
/**************************************
?struct Node{
    int a
};
bool operator<(Node a,Node b){
    return a>b;
}
**************************************/
int main(){
    priority_queue<int,vector<int>,cmp> q;
    //priority_queue<int,vector<int>,greater<int> > q;
    for(int i=0;i<10;i++){
        q.push(i);
    }
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
    cout<<endl;
    for(int i=9;i>=0;i--){
        q.push(i);
    }
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
    return 0;
}

stack

#include<stack>
stack<Datatype> s;
s.push(Data); //入棧
s.pop(); //出棧
?s.top(); //訪問棧頂元素
s.empty(); //判斷棧是否為空
s.size(); //棧元素個數(shù)

關(guān)聯(lián)容器

map

#include<map>
//1.定義和初始化
map<int,string> map1;                  //空map

//2.常用操作方法
map1[3] = "Saniya";                    //添加元素
map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素
//map1.insert(pair<int,string>(1,"Siqinsini"));
map1.insert(make_pair<int,string>(4,"V5"));
string str = map1[3];                  //根據(jù)key取得value，key不能修改
map<int,string>::iterator iter_map = map1.begin();//取得迭代器首地址
int key = iter_map->first;             //取得key
string value = iter_map->second;       //取得value
map1.erase(iter_map);                  //刪除迭代器數(shù)據(jù)
map1.erase(3);                         //根據(jù)key刪除value
map1.size();                       //元素個數(shù)
map1.empty();                       //判斷空
map1.clear();                      //清空所有元素

//3.遍歷
for(map<int,string>::iterator iter = map1.begin();iter!=map1.end();iter++)
{
    int keyk = iter->first;
    string valuev = iter->second;
}

set

#include<map>
using namespace std;
set<int> s;
s.insert; //插入元素
s.erase(); //根據(jù)健值插入元素
s.clear(); //刪除所有元素
s.empty(); //是否為空
s.find(); //返回指向查找元素位置的迭代器，找不到則返回s.end()
s.size(); //元素個數(shù)
//???遍歷
set<string>::iterator iter=set_str.begin();  
while(iter!=set_str.end())  
{  
    cout<<*iter<<endl;  
    ++iter;  
}  

PAT常用算法

排序

STL函數(shù)

bool cmp(){}
sort(begin,end,cmp);

冒泡排序

void BubbleSort(int A[], int n)
{
    for (int j = 0; j < n - 1; j++)         // 每次最大元素就像氣泡一樣"浮"到數(shù)組的最后
    {
        for (int i = 0; i < n - 1 - j; i++) // 依次比較相鄰的兩個元素,使較大的那個向后移
        {
            if (A[i] > A[i + 1])            // 如果條件改成A[i] >= A[i + 1],則變?yōu)椴环€(wěn)定的排序算法
            {
                swap(A[i], a[i+1]);
            }
        }
    }
}

插入排序

void InsertionSort(int A[], int n)
{
    for (int i = 1; i < n; i++)         // 類似抓撲克牌排序
    {
        int get = A[i];                 // 右手抓到一張撲克牌
        int j = i;                  // 拿在左手上的牌總是排序好的
        while (j >0 && A[j-1] > get)    // 將抓到的牌與手牌從右向左進行比較
        {
            A[j] = A[j-1];            // 如果該手牌比抓到的牌大，就將其右移
            j--;
        }
        A[j] = get; // 直到該手牌比抓到的牌小(或二者相等)，將抓到的牌插入到該手牌右邊(相等元素的相對次序未變，所以插入排序是穩(wěn)定的)
    }
}

希爾排序

#include <stdio.h>  

// 分類 -------------- 內(nèi)部比較排序
// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
// 最差時間復(fù)雜度 ---- 根據(jù)步長序列的不同而不同。已知最好的為O(n(logn)^2)
// 最優(yōu)時間復(fù)雜度 ---- O(n)
// 平均時間復(fù)雜度 ---- 根據(jù)步長序列的不同而不同。
// 所需輔助空間 ------ O(1)
// 穩(wěn)定性 ------------ 不穩(wěn)定

void ShellSort(int A[], int n)
{
    int h = 0;
    while (h <= n)                          // 生成初始增量
    {
        h = 3 * h + 1;
    }
    while (h >= 1)
    {
        for (int i = h; i < n; i++)
        {
            int j = i - h;
            int get = A[i];
            while (j >= 0 && A[j] > get)
            {
                A[j + h] = A[j];
                j = j - h;
            }
            A[j + h] = get;
        }
        h = (h - 1) / 3;                    // 遞減增量
    }
}

歸并排序

void Merge(int A[], int left, int mid, int right)// 合并兩個已排好序的數(shù)組A[left...mid]和A[mid+1...right]
{
    int len = right - left + 1;
    int *temp = new int[len];       // 輔助空間O(n)
    int index = 0;
    int i = left;                   // 前一數(shù)組的起始元素
    int j = mid + 1;                // 后一數(shù)組的起始元素
    while (i <= mid && j <= right)
    {
        temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];  // 帶等號保證歸并排序的穩(wěn)定性
    }
    while (i <= mid)
    {
        temp[index++] = A[i++];
    }
    while (j <= right)
    {
        temp[index++] = A[j++];
    }
    for (int k = 0; k < len; k++)
    {
        A[left++] = temp[k];
    }
}

void MergeSortRecursion(int A[], int left, int right)    // 遞歸實現(xiàn)的歸并排序(自頂向下)
{
    if (left == right)    // 當待排序的序列長度為1時，遞歸開始回溯，進行merge操作
        return;
    int mid = (left + right) / 2;
    MergeSortRecursion(A, left, mid);
    MergeSortRecursion(A, mid + 1, right);
    Merge(A, left, mid, right);
}

堆排序

// 分類 -------------- 內(nèi)部比較排序
// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
// 最差時間復(fù)雜度 ---- O(nlogn)
// 最優(yōu)時間復(fù)雜度 ---- O(nlogn)
// 平均時間復(fù)雜度 ---- O(nlogn)
// 所需輔助空間 ------ O(1)
// 穩(wěn)定性 ------------ 不穩(wěn)定
priority_queue<int> q;
void HeapSort(int A[], int n)
{
    int heap_size = BuildHeap(A, n);    // 建立一個最大堆
    while (q.size() > 0)    　　　　　　 // 堆（無序區(qū)）元素個數(shù)大于1，未完成排序
    {
        cout<<q.top();
        q.pop();
    }
}

快速排序

#include <stdio.h>
int a[101],n;//定義全局變量，這兩個變量需要在子函數(shù)中使用
void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
       return;
    temp=a[left]; //temp中存的就是基準數(shù)
    i=left;
    j=right;
    while(i!=j)
    {
        //順序很重要，要先從右邊開始找
        while(a[j]>=temp && i<j)
                j--;
        //再找右邊的
        while(a[i]<=temp && i<j)
                i++;
        //交換兩個數(shù)在數(shù)組中的位置
        if(i<j)
        {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
        }
    }
    //最終將基準數(shù)歸位
    a[left]=a[i];
    a[i]=temp;
    quicksort(left,i-1);//繼續(xù)處理左邊的，這里是一個遞歸的過程 
    quicksort(i+1,right);//繼續(xù)處理右邊的 ，這里是一個遞歸的過程 
}

拓撲排序

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

/************************類聲明************************/
class Graph
{
    int V;             // 頂點個數(shù)
    list<int> *adj;    // 鄰接表
    queue<int> q;      // 維護一個入度為0的頂點的集合
    int* indegree;     // 記錄每個頂點的入度
public:
    Graph(int V);                   // 構(gòu)造函數(shù)
    ~Graph();                       // 析構(gòu)函數(shù)
    void addEdge(int v, int w);     // 添加邊
    bool topological_sort();        // 拓撲排序
};

/************************類定義************************/
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];

    indegree = new int[V];  // 入度全部初始化為0
    for(int i=0; i<V; ++i)
        indegree[i] = 0;
}

Graph::~Graph()
{
    delete [] adj;
    delete [] indegree;
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    ++indegree[w];
}

bool Graph::topological_sort()
{
    for(int i=0; i<V; ++i)
        if(indegree[i] == 0)
            q.push(i);         // 將所有入度為0的頂點入隊

    int count = 0;             // 計數(shù)，記錄當前已經(jīng)輸出的頂點數(shù) 
    while(!q.empty())
    {
        int v = q.front();      // 從隊列中取出一個頂點
        q.pop();

        cout << v << " ";      // 輸出該頂點
        ++count;
        // 將所有v指向的頂點的入度減1，并將入度減為0的頂點入棧
        list<int>::iterator beg = adj[v].begin();
        for( ; beg!=adj[v].end(); ++beg)
            if(!(--indegree[*beg]))
                q.push(*beg);   // 若入度為0，則入棧
    }

    if(count < V)
        return false;           // 沒有輸出全部頂點，有向圖中有回路
    else
        return true;            // 拓撲排序成功
}

最短路徑

Dijkstra

const int inf = 99999999;
const int size = 100;
vector<int> pre[size];
int dis[size];
int e[size][size];
int root = 0;
bool visit[size];
fill(e[0],e[0]+size*size,inf);
fill(dis,dis+size,inf);
visit[root] = true;
dis[root] = 0;
void Dijkstra(){
    for(int i=0;i<size;i++){
        int u=-1,minn=inf;
        for(int j=0;j<size;j++){
            if(!visit[j] && dis[j]<minn){
                minn = dis[j];
                u = j;
            }
        }
        if(u=-1) return;
        visit[u] = true;
        for(int v=0;v<size;v++){
            if(!visit[v]&&e[u][v]!=inf){
                if(e[u][v]+dis[u]<dis[v]){
                    dis[v] = dis[u]+e[u][v];
                    pre[v].clear();
                    pre[v].push_back();
                }else if(e[u][v]+dis[u]==dis[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}

Floyd算法

typedef struct
{
    char vertex[VertexNum];                                //頂點表
    int edges[VertexNum][VertexNum];                       //鄰接矩陣,可看做邊表
    int n,e;                                               //圖中當前的頂點數(shù)和邊數(shù)
}MGraph;

void Floyd(MGraph g)
{
 　　int A[MAXV][MAXV];
 　　int path[MAXV][MAXV];
 　　int i,j,k,n=g.n;
 　　for(i=0;i<n;i++){
    　　for(j=0;j<n;j++)
    　　{
             A[i][j]=g.edges[i][j];
         　　 path[i][j]=-1;
     　 }
    }
 　　for(k=0;k<n;k++){
      　　for(i=0;i<n;i++){
         　　for(j=0;j<n;j++){
             　　if(A[i][j]>(A[i][k]+A[k][j])){
                   　　A[i][j]=A[i][k]+A[k][j];
                   　　path[i][j]=k;
              　}
            }
        }
    }
}

圖和樹的遍歷

DFS

vector<int> tree[size];
vector<int> temppath,path;
void dfs(int root){
    if(tree[root].size()==0){
        temppath.push_back(root);
        path = temppath;
        temp.pop_back();
        return;
    }
    temppath.push_back(root);
    for(int i=0;i<tree[root].size();i++){
        dfs(tree[root][i]);
    }
    temppath.pop_back();
}

BFS

queue<int> q;
vector<int> tree[size];
bool visit[size];
void bfs(){
    q.push_back(root);
    visit[root] = true;
    int first=0,last=1,depth=0,cnt=1;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        first++;
        for(int i=0;i<tree[temp].size();i++){
            if(!visit[tree[temp][i]]){
                q.push(tree[temp][i]);
                visit[tree[temp][i]] = true;
                cnt++;
            }
        }
        if(first==last){
            last = cnt;
            dep++;
        }
    }
}

樹的前中后序遍歷

已知后序與中序輸出前序

#include <cstdio>
using namespace std;
int post[size];
int in[size];
void pre(int root, int start, int end) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    printf("%d ", post[root]);
    pre(root - 1 - end + i, start, i - 1);
    pre(root - 1, i + 1, end);
}

int main() {
    pre(size, 0, size);
    return 0;
}

已知后序與中序輸出層序

#include <cstdio>
#include <vector>
using namespace std;
vector<int> post, in, level(100000, -1);
void pre(int root, int start, int end, int index) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    level[index] = post[root];
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}

前序后序轉(zhuǎn)中序

#include <cstdio>
#include <vector>
using namespace std;
vector<int> ans;
int *pre, *post, unique = 1;
int findFromPre (int x, int l, int r) {
    for (int i = l; i <= r; i++) {
        if (x == pre[i]) {
            return i;
        }
    }
    return -1;
}
void setIn (int prel, int prer, int postl, int postr) {
    if (prel == prer) {
        ans.push_back(pre[prel]);
        return;
    }
    if (pre[prel] == post[postr]) {
        int x = findFromPre(post[postr - 1], prel + 1, prer);
        if (x - prel > 1) {
            setIn(prel + 1, x - 1, postl, postl + x - prel - 2);
            ans.push_back(post[postr]);
            setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
        } else {
            unique = 0;
            ans.push_back(post[postr]);
            setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
        }
    }
}

AVL樹

struct Node{
    int val;
    struct Node *left,*right;
};
struct Node* leftRotate(struct Node *tree) {
    struct Node *temp = tree->right;
    tree->right = temp->left;
    temp->left = tree;
    return temp;
}
struct Node* rightRotate(struct Node *tree) {
    struct Node *temp = tree->left;
    tree->left = temp->right;
    temp->right = tree;
    return temp;
}
int getHeight(struct Node *tree) {
    if (tree == NULL) {
        return 0;
    } else {
        int l = getHeight(tree->left);
        int r = getHeight(tree->right);
        return l > r ? l + 1 : r + 1;
    }
}
struct Node* leftRightRotate(struct Node *tree) {
    tree->left = leftRotate(tree->left);
    tree = rightRotate(tree);
    return tree;
}
struct Node* rightLeftRotate(struct Node *tree) {
    tree->right = rightRotate(tree->right);
    tree = leftRotate(tree);
    return tree;
}
struct Node* insert(struct Node *tree, int val) {
    if (tree == NULL) {
        tree = new struct Node();
        tree->val = val;
        return tree;
    }
    if (tree->val > val) {
        tree->left = insert(tree->left, val);
        int l = getHeight(tree->left);
        int r = getHeight(tree->right);
        if (l - r >= 2) {
            if (val < tree->left->val) {
                tree = rightRotate(tree);
            } else {
                tree = leftRightRotate(tree);
            }
        }
    } else {
        tree->right = insert(tree->right, val);
        int l = getHeight(tree->left);
        int r = getHeight(tree->right);
        if (r - l >= 2) {
            if (val > tree->right->val) {
                tree = leftRotate(tree);
            } else {
                tree = rightLeftRotate(tree);
            }
        }
    }
    return tree;
}

并查集

int father[10010];
int visit[10010];
int find(int a){
    while(a!=father[a]){
        father[a] = father[father[a]];
        a = father[a];
    }
    return a;
}
void Union(int a,int b){
    int fa = find(a);
    int fb = find(b);
    if(fa!=fb){
        father[fa] = fb;
    }
}

樹狀數(shù)組

#define lowbit(i)((i)&(-i))
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}

背包問題

01背包問題

int w[10010], dp[10010], v[10010];
bool choice[10010][10010];
int cmp1(int a, int b){return a > b;}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        cin>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            if(dp[j]<=dp[j-w[i]]+v[i]){
                dp[j] = dp[j-w[i]]+v[i];
            }
        }
    }
    return 0;
}

完全背包

將01背包內(nèi)循環(huán)的逆序改為順序

數(shù)學(xué)問題

gcd

int gcd(int a, int b){ return b == 0 ? a : gcd(b,a%b); }

lcm

int lcm(ina ,int b){return a*b/gcd(a,b);}

素數(shù)表的建立

bool prime[size] = {true};
for(int i=0;i*i<size;i++){
    for(int j=0;j*i<size;j++){
        prime[j*i] = false;
    }
}

字符串處理

string a = "123456";
int b = stoi(a); //convert int to string
string c = to_string(b); //convert string to int
sscanf(a,"%d",b); //從字符串a(chǎn)讀進int類型的數(shù)據(jù)并放入b
sprintf(c,"%05d",b); //將b按格式化寫入c