Java教程
PAT算法模版
本文主要是介绍PAT算法模版，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
算法初步
进制转换
//十进制内任意进制转换
int y=0,product=1; //product在循环中不断乘P，得到1，P，P^2···
while (x!=0)
{
y=y+(x%10)*product; //x%10是为了获取x的个位数
x=x/10;
product=product*p;
}
//任意36进制以内的进制转换(包括负)
string transform(int x,string s,int y)
{
string res="";
long long sum=0;
for(int i=0;i<s.length();i++)
{
if(s[i]=='-') continue; //数据为负的情况
if(s[i]>='0' && s[i]<='9')
sum=sum*x+s[i]-'0'; //从高位开始去转换为十进制
else
sum=sum*x+s[i]-'A'+10;
}
while(sum)
{
char tmp=sum%y;
sum/=y;
if(tmp<=9)
tmp+='0';
else
tmp=tmp-10+'A';
res=tmp+res; //字符串累加一个一个的字符
}
if(res.length()==0) res='0';
if(s[0]=='-') res='-'+res; //数据为负的情况
return res;
}
最大公约数与最小公倍数
//最大公约数
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
最小公倍数：a/d*b d是最大公约数，这样写防止a*b溢出
素数
bool isprime(int n)
{
if(n==1) return false;
for(int i=2;i*i<=n;i++)
if(n%i==0) return false;
return true;
}
大数运算
//直接通过string存储
//rev把数逆向存储，个位在最前面，高位在最后面，方便进位
string rev(string s)
{
reverse(s.begin(),s.end());
return s;
}
//大数比较: 先判断len，如果相等则高位到低位比较，直到出现某一位不等
int compare(string a,string b) //a大、等、小分别返回1、0、-1
{
if(a.size()>b.size()) return 1;
else if(a.size()<b.size()) return -1;
else
{
rev(a);rev(b);
for(int i=a.size()-1;i>=0;i--) //从高位向地位比较
{
if(a[i]-'0'>b[i]-'0') return 1; //只要有一位a大，a就大
else if(a[i]-'0'<b[i]-'0') return -1;
}
return 0;
}
}
//加
string add(string a,string b)
{
rev(a);rev(b);
string c="";
int carry=0; //进位
for(int i=0;i<a.size() || i<b.size();i++) //以较长的为界限
{
int temp=(a[i]-'0')+(b[i]-'0')+carry; //两个位与进位相加
c+=temp%10+'0'; //个位数为该结果
carry=temp/10; //十位数是新的进位
}
if(carry!=0) //如果最后进位不为零，直接赋值给结果的最高位
c+=carry+'0';
return rev(c);
}
哈希
//获取比N大的最近的质数
bool isprime(int n)
{
if(n==1) return false;
for(int i=2;i*i<=n;i++)
if(n%i==0) return false;
return true;
}
while(!isprime(size)) size++;
//平方探测法(简单版)
//将key插入由平方探测的位置，没有则返回“-”
void insert(int key)
{
for(int step=0;step<size;step++)//从0-size-1
{
int index=(key+step*step)%size; //只有正向探测
if(Hash[index]==0)
{
Hash[index]=key;
printf("%d",index);
return;
}
}
printf("-");
}
//平方探测法(标准版): 以增量序列 1^2 , -1^2 , 2^2,- 2^2且q<=TableSize/2
//哈希函数，返回一个位置
int Hash(int Key,int TableSize)
{
return Key%TableSize;
}
//HashTable和Flag都为全局数组
int Find(int Key,int TableSize)
{
int CurrentPos,NewPos;
int CNum=0;
NewPos=CurrentPos=Hash(Key,TableSize); /* 由哈希函数得到初始值 */
//第二个条件可以根据题目需要进行删留。含义是：这个地方被占用了，并且还要与当前值不等，相等就直接返回这个位置
while( Flag[NewPos]=true && HashTable[NewPos]!=Key ) //true代表该位置被占用
{
if(CNum>TableSize/2) return -1;//没有找到位置
if( ++CNum%2 )
{
NewPos=CurrentPos+ (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */
if ( NewPos >= H->TableSize )
NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
}
else
{
NewPos = CurrentPos - CNum*CNum/4; /* 增量为-(CNum/2)^2 */
while( NewPos < 0 ) //注意这里的条件与上面的不一样
NewPos += H->TableSize; /* 调整为合法地址 */
}
}
return NewPos; //返回两种情况：key在哈希表中就返回key的位置，若不在就返回一个满足条件的位置
}
运算符重载
//运算符重载为成员函数时，参数的个数等于运算符的数目减一
#include<iostream>
using namespace std;
struct Complex{
double real,imag;
Complex(double r=0.0,double i=0.0)
{
real=r;
imag=i;
}
Complex operator + (const Complex & c)
{
return Complex(real+c.real,imag+c.imag);
}
};
int main()
{
Complex c(4,4),b(1,1),a;
a=b+c;
cout<<a.real<<","<<a.imag<<endl;
return 0;
}
八皇后
const int Max=1010;
int cnt=0,P(Max);//P数组放的是方案
bool hashTable[Max];
void generateP(int index)
{
if(index==n+1) //递归边界，生成一个合法方案
{
cnt++;//累计方案
return;
}
for(int x=1;x<=n;x++) //第x行
{
if(hashTable[x]==false) //第x行还没有皇后
{
bool flag=true; //flag为true表示当前皇后不会和之前的皇后冲突
for(int pre=1;pre<index;pre++) //遍历之前的皇后
{ //第index列皇后的行号为x，第pre列皇后的行号为P[pre]
if(abs(index-pre)==abs(x-P[pre]))
{
flag=false; //与之前的皇后在一条对角线，冲突
break;
}
}
if(flag) //如果可以，把皇后a放在第x行
{
P[index]=x; //令第index列皇后的行号为x
hashTable[x]=true; //第x行被占用
generateP(index+1); //递归处理第index+1行皇后
hashTable[x]=false; //递归完毕，还原第x行为未占用
}
}
}
}
generateP(1);
分数运算
//分数表示
struct Fraction()
{
int up,down;
};
//分数化简：
//1 分母down为负，那么令分子up和分母down都变相反数
//2 up为0，就令down为1
//3 约分：同时除以最大公约数
Fraction reduction(Fraction result)
{
if(result.down<0)
{
result.up=-result.up;
result.down=-resut.down;
}
if(result.up==0)
result.down=1;
else
{
int d=gcd(abs(result.up),abs(result.down));
result.up/=d;
result.down/=d;
}
return result;
}
//分数加减法
Fraction add(Fraction f1,Fraction f2,)
{
Fraction result;
result.up=f1.up*f2.down+f2.up*f1.down; //减法：将‘+’改为‘减’
result.down=f1.down*f2.down;
return reduction(result); //注意化简
}
//分数乘法
Fraction add(Fraction f1,Fraction f2,)
{
Fraction result;
result.up=f1.up*f2.up
result.down=f1.down*f2.down;
return reduction(result); //注意化简
}
//分数除法
Fraction add(Fraction f1,Fraction f2,)
{
Fraction result;
result.up=f1.up*f2.down
result.down=f1.down*f2.up;
return reduction(result); //注意化简
}
线性结构
链表
//创建链表
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node //建立节点
{
int data;
node* next;
};
node* create(int Array[]) //根据c数组建立一个链表
{
//head不存储任何数据，是空的
node *p,*rear,*head; //head为头节点，rear指向最后的一个节点，方便插入新的节点
head=new node;
head->next=NULL; //初始化头节点
rear=head; //没有数据节点时，rear=head
for(int i=0;i<5;i++)
{
p=new node; //p临时节点，将要存储的数据先存到节点内，再去插入
p->data=Array[i];
p->next=NULL;
rear->next=p; //将新的节点插入链表
rear=p; //保证rear指向最后一个节点
}
return head;
}
int main()
{
int Array[5]={1,2,3,4,5};
node *p=create(Array);
//注意：遍历时一定要重新添加一个指针，不然可能遍历结束后指针指向NULL，导致链表丢失
node *p2=p->next; //跳过头节点，指向第一个数据节点
while(p2!=NULL)
{
cout<<p2->data<<" ";
p2=p2->next; //指向下一个节点
}
return 0;
}
//查找元素
//在以head为头的链表上计数元素x的个数
int search(node* head,int x)
{
int count=0;
node* p=head->next;
while(p!=NULL)
{
if(p->data==x)
count++;
p=p->next;
}
return count;
}
//插入元素
//将x插入以head为头的链表的第pos个位置上
void insert(node* head,int pos,int x)
{
node *p=head;
for(int i=0;i<pos-1;i++)
p=p->next; //找到插入位置的前一个节点
node* newNode=new node; //建立新的节点
newNode->data=x;
newNode->next=p->next; //插入新的节点
p->next=newNode;
}
//删除元素
//删除以head为头的链表中所有数据为x的节点
void del(node* head,int x)
{
node *p=head->next; //p从第一个开始枚举
node *pre=head; //pre始终为p的前驱节点
while(p!=NULL)
{
if(p->data==x)
{
pre->next=p->next;
delete(p);
p=pre->next;
}
else //同时向前
{
pre=p;
p=p->next;
}
}
}
静态链表：链表节点数组，每一个节点都存下一个节点的数组下标(下标为地址)。NULL用-1表示
struct Node{
int data;
int next;
}node[1000];
树
树就是一个有方向的特殊图
对于完全二叉树，数组的顺序访问就是层次遍历
先序遍历的顺序访问就是分别依次访问左右子树
二叉树与遍历
树的五种遍历
-
前序遍历
-
中序遍历
-
后序遍历
-
BDS(层次遍历)
-
DFS
二叉树顺序存储
-
非根结点(序号 i > 1，根结点序号为1)的父结点的序号是i / 2
-
结点(序号为i)的左孩子结点的序号是 2i， (若2 i <= n，否则没有左孩子)
-
结点(序号为i)的右孩子结点的序号是 2i+1， (若2 i +1<= n，否则没有右孩子)
二叉树静态写法
//二叉树链表存储、创建
struct binTree{
int data;
node* left;
node* right;
}
//根据先序创建
binTree* binTreeCreat()
{
binTree* p;
int ch;
scanf("%d",&ch);
if(ch==0) //递归边界
p=NULL;
else
{
p=new binTree;
p->data=ch;
p->left=BinTreeCreatBinTree(); //一直向左边建
p->right=BinTreeCreatBinTree();
}
return p;
}
//二叉树查找、修改
void search(node* root,int x,int newdata)
{
if(root==NULL) return; //空数，递归边界
if(root->data==x) //找到x就修改为newdata
root->data=newdata;
search(root->left,x,newdata);
search(root->right,x,newdata);
}
//先序遍历
void preorder(binTree* root)
{
if(root==NULL) return;
printf("%d\n",root->data);
preorder(root->left);
preorder(root->right);
}
//中序遍历
void inorder(binTree* root)
{
if(root==NULL) return;
inorder(root->left);
printf("%d\n",root->data);
inorder(root->right);
}
//后序遍历
void postorder(binTree* root)
{
if(root==NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d\n",root->data);
}
//层次遍历(并计算每个节点所在层数)
struct binTree{
int data;
int layer;
node* left;
node* right;
}
void layerOrder(node* root)
{
queue<node*> q; //注意队列里面存地址
root->layer=1; //根节点层号为1
q.push(root); //跟节点地址入队
while(!q.empty())
{
node* now=q.front(); //取出首元素
q.pop();
printf("%d ",now->data);
if(now->left!=NULL)
{
now->left->layer=now->layer+1; //左孩子的层号为当前号+1
q.push(now->left);
}
if(now->right!=NULL)
{
now->right->layer=now->layer+1; //右孩子的层号为当前号+1
q.push(now->right);
}
}
}
由两种遍历确定二叉树(必须知道中序遍历)
int pre[maxn],in[maxn],post[maxn];
int maxDepth;
vector<int> ans[maxn];
//有三个功能：1根据前序中序直接求出后序 2每个节点的层析，即层次遍历 3建立一棵树
//前6个参数为前中后序的左右区间，最后一个是求节点的深度，也就是层次遍历。
void creat(int preL,int preR,int inL,int inR,int postL,int postR,int depth)
{
if(preL>preR) return;
maxDepth=max(depth,maxDepth);
ans[depth].push_back(post[postR]);//在相应的层次保存节点
post[postR]=pre[preL];//根据前序中序直接求出后序
int k=inL;
while(k<=inR && pre[preL]!=in[k]) k++;
int num=k-inL;
creat(preL+1,preL+num,inL,k-1,postL,postL+num-1,depth+1);
creat(preL+num+1,preR,k+1,inR,postL+num,postR-1,depth+1);
}
//中序与前序基础版。可衍生与上述类似的功能
void create(int inL, int inR, int postL, int postR)
{
if (postL > postR) return;
int k = inL;//k用来指向中序遍历中的根节点
while (k <= inR && in[k] != post[postR]) k ++;
int num = k - inL;
create(inL, k - 1, postL, postL + num - 1);
create(k + 1, inR, postL + num, postR - 1);
}
完全二叉树
- 使用数组方式存储
- 非根结点(序号 i > 1)的父结点的序号是i / 2
- 结点(序号为i)的左孩子结点的序号是 2i， (若2 i <= n，否则没有左孩子)
- 结点(序号为i)的右孩子结点的序号是 2i+1， (若2 i +1<= n，否则没有右孩子)
并查集
//初始化
//数组实现
int father[N]; //下标是它自己，father[N]是他的父亲
//最开始，每个元素都是一个独立的集合
for(int i=1;i<=n;i++)
{
father[i]=i; //father[i]=-1也可以
}
//查找
int findFather(int x)
{
//使用递归可以把沿路节点的父节点都变成根节点。也就是让更多的节点直接指向根节点，加快速度
return father[x] == x ? x : father[x] = findFather(father[x]);
//这个版本在效率要低一些
//while(x!=father[x]) //如果不是跟节点，继续循环
//x=father[x]; //获得自己的父亲节点
return x;
}
//合并
void Union(int a,int b)
{
int faA=finFather(a); //查找A的根节点
int faB=finFather(b); //查找B的根节点
if(faA!=faB)
father[faA]=faB; //合并
}
二叉查找树(BST)
二叉树的建立的两种方式:
1.给的数据只需按照建立普通二叉树的方式就能建立一个二叉树
2.给的数据是乱序，需要调整建立成一个BST
普通二叉树的方式
//建立
struct Node{
int data;
Node* left;//建树时需要初始化为空
Node* right;
Node(int k):data(k),left(NULL),right(NULL){};
};
node* creat(int data[],int n) //根据一个数组创建BST
{
node* root=NULL;
for(int i=0;i<n;i++)
insert(root,data[i]);
return root;
}
//查找
void search(node* root,int x)
{
if(root==NULL)
{
printf("search failed\n");
return;
}
if(x==root->data)
printf("%d\n",root->data);
else if(x<root->data)
search(root->left,x);
else
search(root->right,x);
}
//插入
void insert(node* &root,int x) //注意需要引用：
{
/*root其实就是它的父节点中root->left(root->right)这个变量的别名
所以new一个新的节点实际上就是给它的父节点新增一个孩子节点*/
if(root=NULL) //空树，说明查找失败，也是插入的位置
{
root=new node(x);
return;
}
if(x==root->data)
return;
else if(x<root->data)
search(root->left,x);
else
search(root->right,x);
}
图
推荐：邻接表+DFS
关于图的题目一定要看看需不需要去判断图的连通性
图的存储
-
邻接矩阵: 一个二维数组。对于无权图，1、0分别代表有无边。有权图无边放0、-1等，有边就放权重。注意：考虑权重为0的情况，此时0不能代表无边
-
邻接表
//无权图
//vector数组下标就是顶点，存的每个值就是终点编号
vector<int> Adj[N];
//无向图两条边:从1到3，从3到1
Adj[1].push_back(3);
Adj[3].push_back(1);
//有向图:只能从1到3
Adj[1].push_back(3);
//有权图
struct GNode{
int v; //边的终点
int w; //b边权
GNode(int _v,int _w):v(_v),w(_w) {};//构造函数
};
Adj.push_back(GNode(3,4))
图的遍历
- vis数组的作用是保证每个节点都只能被访问一次，因为在图中一个节点可能有多条与它相连的节点。而在树中每个节点只有一条通向它的路，所以vis数组可以省略
- 深度优先遍历比广度优先遍历更常用一些，但对于设置了遍历层数上限的题目，广度优先遍历要更加简洁，逻辑也更加清晰
DFS
注意: DFS可能会因为递归太深出现段错误
//邻接矩阵版
const int MAXV=1000; //最大顶点
const int INF=100000000; //INF是一个很大的数
int cnt=0;
int n,G[MAXV][MAXV]; //n为顶点数，MAXV最大顶点数
bool vis[MAXV]={false}; //访问过就vis==true
void DFS(int u,int depth) //depth为深度
{
vis[u]=true; //设置u为访问
cnt++;//这样可以直接统计遍历的个数，看看图是不是连通的
//如果需要对u进行一些操作，可以在这里进行
//下面是对所有从u出发能到达的分支顶点进行枚举
for(int v=0;v<n;v++)
{
//注意：G[u][v]!=INF一定要使用填充函数使数组每个元素为INF
if(vis[v]==false && G[u][v]!=INF) //如果v未被访问，且u可以到达v
DFS(v,depth+1); //访问v，深度+1
}
}
void DFSTrave() //遍历整个图
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
DFS(u,1); //访问u和u所在的连通块，1表示初始未第一层
}
}
//邻接表版
const int MAXV=1000; //最大顶点
const int INF=100000000; //INF是一个很大的数
vector<int> Adj[MAXV];
int n;
bool vis[MAXV]={false}; //访问过就vis==true
void DFS(int u,int depth)
{
vis[u]=true;
for(int i=0;i<Adj[u].size();i++)
{
int v=Adj[u][i];
if(vis[v]==false)
{
DFS(v,depth+1);
}
}
}
void DFSTrave() //遍历整个图
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
DFS(u,1); //访问u和u所在的连通块，1表示初始为第一层
}
}
BFS
树的层次遍历相当于BFS的特殊情况
//邻接矩阵版
const int MAXV=1000; //最大顶点
const int INF=100000000; //INF是一个很大的数
int n,G[MAXV][MAXV]; //n为顶点数，MAXV最大顶点数
bool vis[MAXV]={false}; //访问过就vis==true
void BFS(int u) //遍历u所在的连通块
{
queue<int> q;
q.push(u); //将初始点u入队
vis[u]=true; //标记访问
while(!q.empty())
{
int u=q.front(); //取出首元素
q.pop(); //首元素出队
for(int v=0;v<n;v++)
{ //如果u的邻接点v未曾加入过队列
if(vis[v]==false && G[u][v]!=INF)
{
q.push(v); //将v入队
vis[v]=true; //标记访问
}
}
}
}
void BFSTrave() //遍历整个图
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
BFS(u); //访问u和u所在的连通块，1表示初始未第一层
}
}
//邻接表版
const int MAXV=1000; //最大顶点
const int INF=100000000; //INF是一个很大的数
vector<int> Adj[MAXV];
int n;
bool vis[MAXV]={false}; //访问过就vis==true
void BFS(int u) //遍历u所在的连通块
{
queue<int> q;
q.push(u); //将初始点u入队
vis[u]=true; //标记访问
while(!q.empty())
{
int u=q.front(); //取出首元素
q.pop(); //首元素出队
for(int i=0;i<Adj[u].size();i++) //枚举从u出发能达到的所有顶点
{
int v=Adj[u][i];
if(vis[v]==false)
{
q.push(v); //将v入队
vis[v]=true; //标记访问
}
}
}
}
void BFSTrave() //遍历整个图
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
BFS(u); //访问u和u所在的连通块，1表示初始未第一层
}
}
最短路径
//邻接矩阵版
const int MAXV=1000; //最大顶点
const int INF=100000000; //INF是一个很大的数
int n,G[MAXV][MAXV]; //n为顶点数，MAXV最大顶点数
bool vis[MAXV]={false}; //访问过就vis==true
//思路：每一次找出一个最小的权（包括它自己），然后更新其他点的最小距离。N次就找出N个
void Dijkstra(int s) //s为起点
{
fill(d,d+MAXV,INF) //将d数组赋值为INF
d[s]=0; //起点s到自身的距离为0
for(int i=0;i<n;i++)//收录的次数，也就是节点的总个数
{
int u=-1,MIN=INF; //u使d[u]最小，MIN存放该最小的d[u]
for(int j=0;j<n;j++) //找到未访问的顶点中最小值
{
if(vis[j]==false && d[j]<MIN)
{
u=j;
MIN=d[j];
}
}
//找不到小于INF的d[u],说明剩下的顶点和起点s不连通
if(u==-1) return;
vis[u]=true; //标记u为已访问
for(int v=0;v<n;v++)
{ //如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优
if(vis[v]==false && G[u][v]!=INF && d[u]+G[u][v]<d[v])
{
d[v]=d[u]+G[u][v];
}
}
}
}
//邻接表版
const int MAXV=1000; //最大顶点
const int INF=100000000; //INF是一个很大的数
struct GNode{
int v; //顶点，
int w; //权值
}
//数组d存的是每个点到起始点的最短距离
int n,G[MAXV][MAXV],d[MAXV]; //n为顶点数，MAXV最大顶点数
bool vis[MAXV]={false}; //访问过就vis==true
void Dijkstra(int s) //s为起点
{
fill(d,d+MAXV,INF) //将d数组赋值为INF
d[s]=0; //起点s到自身的距离为0
for(int i=0;i<n;i++)//每次收录一个点，收录n次
{
int u=-1,MIN=INF; //u使d[u]最小，MIN存放该最小的d[u]
for(int j=0;j<n;j++) //找到未访问的顶点中最小值
{
//找最小值就意味着：比起其它通向起点的点，我到起点的距离最短的。不可有我经过其它点后再到起点是最短的
if(vis[j]==false && d[j]<MIN)
{
u=j;
MIN=d[j];
}
}
//找不到小于INF的d[u],说明剩下的顶点和起点s不连通
if(u==-1) return;
vis[u]=true; //标记u为已访问
//只有for下与邻接矩阵写法画不同
for(int j=0;j<Adj[u].size();j++)
{
int v=Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
if(vis[v]==false && d[u]+Adj[u][j].w<d[v])
{ //如果v未访问 && 以u为中介点可以使d[v]更优
d[v]=d[u]+Adj[u][j].w;
path[v]=u;//说明v的上一步是u
}
}
}
}
这篇关于PAT算法模版的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Mybatis官方生成器资料详解与应用教程11-26
-
Mybatis一级缓存资料详解与实战教程11-26
-
Mybatis一级缓存资料详解：新手快速入门11-26
-
SpringBoot3+JDK17搭建后端资料详尽教程11-26
-
Springboot单体架构搭建资料：新手入门教程11-26
-
Springboot单体架构搭建资料详解与实战教程11-26
-
Springboot框架资料：新手入门教程11-26
-
Springboot企业级开发资料入门教程11-26
-
SpringBoot企业级开发资料详解与实战教程11-26
-
Springboot微服务资料：新手入门全攻略11-26
-
SpringBoot微服务资料入门教程11-26
-
Springboot项目开发资料详解与入门指南11-26
-
SpringBoot项目开发资料详解入门教程11-26
-
SpringBoot应用的生产发布资料详解11-26
-
手写消息中间件：从零开始的指南11-26
栏目导航
