PAT算法笔记

作者: Elis0913 | 来源:发表于2020-02-07 21:33 被阅读0次

PAT算法笔记
2020-02-06
PAT-B 1045 快速排序（Ｃ语言）
【算法笔记】前言
最近的数据学习计划
自定义View-第十步：PathMeasure
算法
PAT排序整理-知识点(来自算法笔记)
Android自定义View 1-1 接上：画自定义图形
血泪教训 in PAT-A | 算法无关的PAT tricks

*****************************************
//优先队列定义
priority_queue<int,vector<int>,greater<int>> q;
*****************************************
//并查集
int father[maxn];
int findFather(int x){
    int demo=x;//记录当前的x
    while(x!=father[x])//第一遍扫描
        x=father[x];
    while(demo!=father[demo]){//第二遍把所有结点指向根节点
        int a=demo;//记录当前demo
        demo=father[demo];//下一层
        father[a]=x;//回溯
    }
    return x;
}
int findfather(int x){
    if(x==father[x]) return x;
    else{
        int v=findfather(father[x]);
        father[x]=v;
        return v;
    }
}
void Union(int a,int b){
    int x=findFather(a);
    int y=findFather(b);
    if(x!=y)
    father[y]=x;
}
*****************************************
//AVL
#include <iostream>
using namespace std;
struct node {
    int val;
    struct node *left, *right;
};
node *rotateLeft(node *root) {
    node *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}
node *rotateRight(node *root) {
    node *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}
node *rotateLeftRight(node *root) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}
node *rotateRightLeft(node *root) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}
int getHeight(node *root) {
    if(root == NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node *insert(node *root, int val) {
    if(root == NULL) {
        root = new node();
        root->val = val;
        root->left = root->right = NULL;
    } else if(val < root->val) {
        root->left = insert(root->left, val);
        if(getHeight(root->left) - getHeight(root->right) == 2)
            root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
    } else {
        root->right = insert(root->right, val);
        if(getHeight(root->left) - getHeight(root->right) == -2)
            root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
    }
    return root;
}
int main() {
    int n, val;
    scanf("%d", &n);
    node *root = NULL;
    for(int i = 0; i < n; i++) {
        scanf("%d", &val);
        root = insert(root, val);
    }
    printf("%d", root->val);
    return 0;
}
*****************************************
//二叉树
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<time.h>
#include<sstream>
#define ll long long
using namespace std;
int pre[100],in[100],post[100];
struct node {
    int data;
    int layer;
    node* l;
    node* r;
};
node* root=NULL;
//生成新节点
node* newNode(int v) {
    node* Node=new node;
    Node->data=v;
    Node->l=Node->r=NULL;
    return Node;
}
//二叉树的替换
void replace(node* root,int x,int newdata) {
    if(root==NULL)
        return;
    if(root->data==x)
        root->data=newdata;
    replace(root->l,x,newdata);
    replace(root->r,x,newdata);
}
//二叉树的插入
void insert(node* &root,int x) {
 if(root==NULL) {
        root=newNode(x);
        return ;
    }
    if(1) {
        insert(root->l,x);
    } else
        insert(root->r,x);
}
node* Create(int data[],int n) {
    node* root = NULL;
    for(int i=0; i<n; i++) {
        insert(root,data[i]);
    }
    return root;
}
void preorder(node* root) {
    if(root==NULL) {
        return ;
    }
    printf("%d",root->data);
    preorder(root->l);
    preorder(root->r);
}
void inorder(node* root) {
    if(root==NULL) {
        return ;
    }
    inorder(root->l);
    printf("%d",root->data);
    inorder(root->r);
}
void pastorder(node* root) {
    if(root==NULL) {
        return ;
    }
    pastorder(root->l);
    pastorder(root->r);
    printf("%d",root->data);
}
void layerorder(node* root) {
    queue<node*> q;
    root->layer=1;
    q.push(root);
    while(!q.empty()) {
        node* now=q.front();
        q.pop();
        printf("%d",now->data);
        if(now->l!=NULL||!q.empty()||now->r!=NULL)
            cout<<" ";

        if(now->l!=NULL) {
            now->l->layer=now->layer+1;
            q.push(now->l);
        }
        if(now->r!=NULL) {
            now->r->layer=now->layer+1;
            q.push(now->r);
        }
    }
}
void layerO(node* root){
    if(root==NULL) return;
    cout<<root->data;
    
}
node* tree(int pl,int pr,int inl,int inr){
    if(pl>pr)
    return NULL;
    node *root=new node;
    root->data=post[pr];
    int k;
    for(k =inl;k<inr;k++){
        if(in[k]==post[pr])
        break;
    }
    root->l=tree(pl,pl+k-inl-1,inl,k-1);
    root->r=tree(pl+k-inl,pr-1,k+1,inr);
    return root;
}

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>post[i];
    for(int i=0;i<n;i++) cin>>in[i];
    node* root=tree(0,n-1,0,n-1);
    layerorder(root);
}


*****************************************
//BFS
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<time.h>
#include<sstream>
#define ll long long
using namespace std;
const int maxn=100;
struct node{
    int x,y;
}Node;
int n,m;
int matrix[maxn][maxn];
bool inq[maxn][maxn]={false};
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};

bool judge(int x,int y){//判断坐标（x,y）是否需要访问
    if(x>=n||x<0||y>=m||y<0) return false;
    if(matrix[x][y]==0||inq[x][y]==true) return false;
    return true;
}
void BFS(int x,int y){
    queue<node> Q;
    Node.x=x,Node.y=y;
    Q.push(Node);
    inq[x][y]=true;
    while(!Q.empty()){
        node top=Q.front();
        Q.pop();
        for(int i=0;i<4;i++){
            int newx=top.x+X[i];
            int newy=top.y+Y[i];
            if(judge(newx,newy)){
                Node.x=newx,Node.y=newy;
                Q.push(Node);
                inq[newx][newy]=true;
            }
        }
    }
}
int main() {
    cin>>n>>m;
    for(int x=0;x<n;x++){
        for(int y=0;y<m;y++)
            cin>>matrix[x][y];
    }
    int ans=0;
    for(int x=0;x<n;x++){
        for(int y=0;y<m;y++){
            if(matrix[x][y]==1&&inq[x][y]==false){
                ans++;
                BFS(x,y);
            }
        }
    }
    cout<<ans;
}
//6  7
//0 1 1 1 0 0 1
//0 0 1 0 0 0 0
//0 0 0 0 1 0 0
//0 0 0 1 1 1 0
//1 1 1 0 1 0 0
//1 1 1 1 0 0 0
*****************************************
//背包客问题
const int maxn=30;
int n,v,maxValue=0;//物品件数n，背包容量v，最大价值maxValue
int w[maxn],c[maxn];//w[i]c[i]为每件物品的重量和价值
//DFS，index为当前处理的物品编号
//sumW和sumC为当前总重量和总价值
void DFS(int index,int sumW,int sumC) {
    if(index==n) {
        return ;//死胡同
    }
    DFS(index+1,sumW,sumC);//不选第index件物品
    if(sumW+w[index]<=v) {//不超过背包容量才能继续
        if(sumC+c[index]>maxValue)//更新maxValue
            maxValue=sumC+c[index];
        DFS(index+1,sumW+w[index],sumC+c[index]);//选第index件物品
    }
}
int main() {
    cin>>n>>v;
    for(int i=0;i<n;i++)    cin>>w[i];
    for(int i=0;i<n;i++)    cin>>c[i];
    DFS(0,0,0);
    cout<<maxValue;
}
*****************************************
//最大公约数gcd
int gcd(int a,int b) {
    if(b==0) return a;
    else
        return  gcd(b,a%b);
}
//最大公倍数lcm
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
*****************************************
//进制转换
#include <iostream>
using namespace std;
//输入A、B，转换为D进制
int main() {
    while(1) {
        int mode;
        printf("\n选择模式\n1：10转n\n2：n转10\n");
        scanf("%d",&mode);
        if(mode==1) {
            int sum,d;
            printf("输入要转化的10进制数和想转换的进制\n");
            scanf("%d%d",&sum,&d);
            int ans[31],num=0;//ans存D进制的每一位
            do {//进制转换
                ans[num++]=sum%d;
                sum/=d;
            } while(sum!=0);
            for(int i=num-1; i>=0; i--) { //从高位往低位输出
                printf("%d",ans[i]);
            }
            printf("\n");
        } else {
            int x,p;
            printf("输入要转换的数字和它的进制\n");
            scanf("%d%d",&x,&p);
            int y=0,product=1;
            while(x!=0) {
                y+=(x%10)*product;
                x/=10;
                product*=p;
            }
            printf("%d\n",y);
        }

    }
}
*****************************************
//int字符串互转
#include <iostream>
using namespace std;
int main() {
    int a;
    char aa[425]="12345678900";
    //注意有&符号!!!
    sscanf(aa,"%lld",&a);//注意有&符号!!!
    sprintf(aa,"%d",a);
    cout<<a;
}
*****************************************
//全排列
#include<iostream>
#include<algorithm>
using namespace std;
//全排列递归算法
void Perm(int list[] , int k ,int m) {
    //list 数组存放排列的数，K表示层,代表第几个数，m表示数组的长度
    if(k==m) {
        //K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
        for(int i=0 ; i<=m ; i++)
            cout<<list[i];
        cout<<endl;
    } else {
        for(int i=k; i<=m; i++) {
            swap(list[i],list[k]);
            Perm(list,k+1,m);
            swap(list[i] , list[k]);
        }
    }

}
int main() {
    int a[]= {1,2,3,4};
    int len=sizeof(a)/sizeof(int);
    Perm(a,0,len-1);
}
//全排列函数用法

int permutation[100];
void get_permutation(int n) {
    for(int i=0; i<n; i++) {
        permutation[i]=i+1;
        printf("%d",permutation[i]);
    }
    printf("\n");
    while(next_permutation(permutation,permutation+n)) {
        for(int i=0; i<n; i++)
            printf("%d",permutation[i]);
        printf("\n");
    }
    return;
}
*****************************************
//质数欧拉筛
int prime[100005], total=0;
bool check[100005];
void get_primes(int n){//筛出[1,n]之间的素数
    for (int i = 2; i <= n; ++i) {
        if (!check[i]) prime[total++] = i;
        for (int j = 0; j < total && i * prime[j] <= n; ++j) {
            check[i*prime[j]] = 1;
            if (i % prime[j] == 0) break;//保证每个数被他最小的质因数约去
        }
    }
}
*****************************************
//计算n！中有多少个质因子p
int cal(int n,int p){
    if(n<p) return 0;
    return n/p+cal(n/p,p);
}
*****************************************
//组合数

//(时间慢)
long long res[1010][1010]={0};
ll cal(ll m,ll n){
    if(m==0||n==m) return 1;
    if(res[n][m]!=0) return res[n][m];
    return res[n][m]=cal(m,n-1)+cal(m-1,n-1);
//  return res[n][m]=(cal(m,n-1,p)+cal(m-1,n-1,p))%p;
//  全部改int型
}

//(乘法可能会溢出)
ll cal2(ll m,ll n){
    ll ans=1;
    for(ll i=1;i<=m;i++){
        ans=ans*(n-m+i)/i;
    }
    return ans;
}
*****************************************

PAT算法笔记
2020-02-06
PAT-甲级做题笔记目录 0000 做题 Tips 基本经验1003 Emergency (Dijkstra ...
PAT-B 1045 快速排序（Ｃ语言）
题目链接：PAT (Basic Level) Practice 1045 快速排序著名的快速排序算法里有一个经...
【算法笔记】前言
本书的适用范围：研究生复试上机考试 PAT甲级、乙级考试 CCF的CSP认证（或其它算法）求职面试时的基础算法...
最近的数据学习计划
学习方向 - 代码能力训练（持续少量） pat训练熟悉python编程语句数据结构，算法导论 - 分析工具训练...
自定义View-第十步：PathMeasure
前言根据Gcssloop所学习的自定义View整理与笔记。一. 简单了解PathMeasure ** Pat...
算法
声明：所有文章只作为学习笔记用，转载非原创pat leetcode acmhttps://github.com/M...
PAT排序整理-知识点(来自算法笔记)
知识回顾 1.cmp函数的书写 cmp函数可对基本数据类型、结构体类型、STL容器进行自定义规则排序默认按照从小到...
Android自定义View 1-1 接上：画自定义图形
学习http://hencoder.com/ui-1-1/笔记一、通过drawPath()绘制自定义图形 Pat...
血泪教训 in PAT-A | 算法无关的PAT tricks
让CodeBlocks支持C++11语法转自stackoverflowGo to Toolbar -> Sett...