做网站花钱吗,如何建一个网站教程,网站正能量免费推广软件,新竹自助建站系统各位小伙伴们大家好#xff0c;今天给大家带来几道算法题。
题目一 算法分析 首先#xff0c;我们应该知道什么是完全二叉树#xff1a;若一颗二叉树深度为n#xff0c;那么前n-1层是满二叉树#xff0c;只有最后一层不确定。 给定我们一棵完全二叉树#xff0c;我们查看… 各位小伙伴们大家好今天给大家带来几道算法题。
题目一 算法分析 首先我们应该知道什么是完全二叉树若一颗二叉树深度为n那么前n-1层是满二叉树只有最后一层不确定。 给定我们一棵完全二叉树我们查看其根的右节点的深度若其深度仅比根的深度小1那么说明以根的左节点为根的子树是一颗满二叉树其数量为Lpow2n-1-1。我们要求的节点数量就是L1根以根的右节点为根的完全二叉树节点数量。如果根的右节点的深度比根的深度小2那么以根的右子树为根的完全二叉树是一颗满二叉树其数量为Rpow2n-2-1。我们要求的节点数量就是R1以根的左节点为根的完全二叉树节点数量。这是一个很明显的递归递归出口分为几种情况只有根返回1。根只有一个节点返回2。根为空返回0。 我们求树的深度时只要其左子树不为空一直往左走即可。
代码展示
#includeiostream
#includecmath
using namespace std;
struct node{int data;struct node* left;struct node* right;
};
//前序创建完全二叉树
struct node* create(){struct node *head(struct node*)malloc(sizeof(struct node));int x;cinx;if(x-1){headNULL;} else{head-datax;head-leftcreate();head-rightcreate();}return head;
}
//打印检验
void printinfo(struct node* head){if(head){printinfo(head-left);couthead-data ;printinfo(head-right);}
}
//获得树的深度
int getheight(struct node *head){struct node *phead;int count0;while(p){pp-left;count;}return count;
}
//获得完全二叉树节点数量
int getsize(struct node* head){if(!head){return 0;}if(!head-left!head-right){return 1;}if(!head-left||!head-right){return 2;}int sizegetheight(head);int heightgetheight(head-right);if(height1size){return pow(2,size-1)getsize(head-right);}else{return pow(2,size-2)getsize(head-left);}
}
int main(){struct node *headcreate();printinfo(head);coutendl;int heightgetheight(head);coutheightendl;int sizegetsize(head);coutsize;
}
题目二 算法分析 我们首先应该知道子序列可以不连续。关于子序列的问题我们都使用动态规划的思想。dp【i】代表以i位置结尾其最长子序列长度。 那么存在公式当arr【j】arr【i】时dp【i】为1否则为dp【j】1。j的范围为0~i-1我们取其中的最大值。
代码展示
int getmax1(int *arr,int n){int dp[n];for(int i0;in;i){dp[i]0;}dp[0]1;int max;for(int i1;in;i){max0;for(int j0;ji;j){if(arr[j]arr[i]){if(maxdp[j]){maxdp[j];}}}dp[i]max1;}max-1;for(int i0;in;i){if(maxdp[i]){maxdp[i];}}return max;
} 这是最经典的解法代码时间复杂度为n^2 。下面我给大家带来一种时间复杂度为nlogn的算法。
算法优化 整体思路不变我们要做的是减少查找开销也就是第二层循环。如果我们将dp数组变的有序是不是就可以使用二分查找了呢 为此我们引进数组endend【i】代表递增子序列长度为i1结尾位置的数字大小。具体思想如下此时新来了一个数字x从end数组中找第一个大于x的数字我们用x取代它即可递增子序列数字越小说明其扩充的可能性越大。若没有比它大的数字我们从end数组中开辟一个新的位置并且赋值为xx不能取代任何位置只能新增。这样最终答案就是i1了。 其中查找数组中第一个比x大的元素时我们使用二分查找仅需要logn水平综合整个代码就是n*logn的。
//寻找有序数组中第一个比x大的元素没有返回-1
int find(int *arr,int n,int x){int left0,rightn-1,res-1;int mid;while(leftright){mid(leftright)/2;if(arr[mid]x){leftmid1;}else{resmid;rightmid-1;}}return res;
}
int getmax2(int *arr,int n){int end[n],x,count0;for(int i0;in;i){if(i0){end[count]arr[i];continue;}xfind(end,count,arr[i]);if(x-1){end[count]arr[i];}else{end[x]arr[i];}}return count;
}
题目三 算法分析 这道题设计一个知识点我们求一个数是否可以整除3可以将其各位相加得到新和再去整除3。即假设判断123456能否取余3我们可以根据12345621能否取余3判断。并且这个知识点是可逆的我们判断123456也可以判断123456判断。 这样这道题就很简单了。输入一个n那么这个数代表1234.....n。我们可以根据1234...n来判断直接使用等差数列求和公式求出和即可。
代码展示
#includeiostream
using namespace std;
int main(){int n;cinn;int sum(1n)*n/2;string strsum%30?可以整除:不能整除; coutstr;
}
题目四 算法分析 这是一道贪心算法题目怎么贪呢如果i位置需要路灯并且我们发现i1位置也需要路灯那我们就放在i1位置。除此之外还有其它抉择如果i位置是x不能放路灯规定i。如果i位置是、并且i1位置是x那么需要i位置放路灯ii2。还有一种情况就是i和i1都是、我们贪心一下ii3。大家也要注意越界。当i位置是、并且i1越界那么需要i位置放路灯。
代码展示
#includeiostream
using namespace std;
int getlight(string s){int count0,i0;while(is.length()){if(s[i]x){i;continue;}else{count;if(i1s.length()){cout结尾放路灯endl;break;}else if(s[i1]x){cout我是.我的后面是xendl;ii2;}else if(s[i1].){cout我是.我的后面是.endl;ii3;}}}return count;
}
int main(){string sx.x...x..x.x...x;int sizegetlight(s);coutsize;
}
题目五 算法分析 首先大家要知道为什么没有重复节点若有重复节点那么后序遍历结果不唯一。一般关于二叉树的题目我们都使用递归的方法。 我们知道了先序和中序遍历结果那么先序的第一个元素就是后序的最后一个元素我们可以直接填好。然后在中序结果中查找此元素就可以将先序、中序、后序数组分为左右两部分。然后对左数组进行递归对右数组进行递归即可。
代码展示
#includeiostream
using namespace std;
int find(int *arr,int start,int end,int x){for(int istart;iend;i){if(arr[i]x){return i;}}
}
void getpos(int *pre,int *in,int *pos,int start1,int end1,int start2,int end2,int start3,int end3){if(start1end1||start2end2||start3end3){return;}if(start1end1){pos[end3]pre[start1];return;}pos[end3]pre[start1];int xfind(in,start2,end2,pre[start1]);getpos(pre,in,pos,start11,start1x-start2,start2,x-1,start3,start3x-1-start2);//递归左 getpos(pre,in,pos,start1x1-start2,end1,x1,end2,start3x-start2,end3-1);//递归右
}
int main(){int pre[7]{1,2,4,5,3,6,7};int in[7]{4,2,5,1,6,3,7};int pos[7];getpos(pre,in,pos,0,6,0,6,0,6);for(int i0;i7;i){coutpos[i] ;}
} 大家注意左右数组的划分这是重点并且我们求左数组长度时找到了中序遍历中左数组结束位置注意减去中序遍历开始位置 大家不要误认为0
题目六 算法分析 根据题目我们就可以知道这是一道前缀树问题创建好前缀树只需要深搜遍历打印即可。
代码展示 这是前缀树的通用模板。运用到改题目时只需要在node节点添加一个data数据记录元素即可。最后深搜打印结果即可。 对于深搜不了解的小伙伴们查看我之前的文章图邻接矩阵知识大杂烩邻接矩阵结构深搜广搜prim算法kruskal算法Dijkstra算法拓扑排序学会一文让你彻底搞懂-CSDN博客
#includeiostream
#includeunordered_set
using namespace std;
struct node{int pass;int end;struct node* next[26];
};
typedef struct node* Node;
Node create(){Node n(Node)malloc(sizeof(struct node));n-pass0;n-end0;for(int i0;i26;i){n-next[i]nullptr;}return n;
}
void insert(Node root,string str){Node noderoot;int path;for(int i0;istr.length();i){node-pass;pathstr[i]-a;if(node-next[path]nullptr){node-next[path]create();}nodenode-next[path];}node-pass;//最后一个没有加 node-end;
}
//寻找str出现多少次
int possearch(Node root,string str){Node noderoot;int path;for(int i0;istr.length();i){pathstr[i]-a;if(node-next[path]nullptr){return 0;}nodenode-next[path];}return node-end;
}
//寻找以str字符串作为前缀的字符串次数
int presearch(Node root,string str){Node noderoot;int path;for(int i0;istr.length();i){pathstr[i]-a;if(node-next[path]nullptr){return 0;}nodenode-next[path];}return node-pass;
}
void deletenode(Node root,string str){if(!possearch(root,str)){cout不存在该字符串无法删除endl;return;}int path;Node noderoot;node-pass--;for(int i0;istr.length();i){pathstr[i]-a;if(node-next[path]-pass1){node-next[path]nullptr;return;}nodenode-next[path]; node-pass--;}node-end--;
}
int main(){Node rootcreate();string strabc;insert(root,str);strstrd;insert(root,str);deletenode(root,abc);int findendsizepresearch(root,abc);coutfindendsize;
} 本期算法分享到此结束大家多多点赞支持
