每日算法练习

  各位小伙伴们大家好，今天给大家带来几道算法题。

题目一

算法分析

  首先，我们应该知道什么是完全二叉树：若一颗二叉树深度为n，那么前n-1层是满二叉树，只有最后一层不确定。

  给定我们一棵完全二叉树，我们查看其根的右节点的深度，若其深度仅比根的深度小1，那么说明以根的左节点为根的子树是一颗满二叉树，其数量为L=pow（2，n-1）-1。我们要求的节点数量就是L+1（根）+以根的右节点为根的完全二叉树节点数量。如果根的右节点的深度比根的深度小2，那么以根的右子树为根的完全二叉树是一颗满二叉树，其数量为R=pow（2，n-2）-1。我们要求的节点数量就是R+1+以根的左节点为根的完全二叉树节点数量。这是一个很明显的递归，递归出口分为几种情况：只有根，返回1。根只有一个节点，返回2。根为空，返回0。

  我们求树的深度时，只要其左子树不为空一直往左走即可。

代码展示

#include<iostream>
#include<cmath>
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;cin>>x;if(x==-1){head=NULL;}	else{head->data=x;head->left=create();head->right=create();}return head;
}
//打印检验 
void printinfo(struct node* head){if(head){printinfo(head->left);cout<<head->data<<" ";printinfo(head->right);}
}
//获得树的深度 
int getheight(struct node *head){struct node *p=head;int count=0;while(p){p=p->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 size=getheight(head);int height=getheight(head->right);if(height+1==size){return pow(2,size-1)+getsize(head->right);}else{return pow(2,size-2)+getsize(head->left);}
}
int main(){struct node *head=create();printinfo(head);cout<<endl;int height=getheight(head);cout<<height<<endl;int size=getsize(head);cout<<size;
}

题目二

算法分析 

 我们首先应该知道子序列可以不连续。关于子序列的问题我们都使用动态规划的思想。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 i=0;i<n;i++){dp[i]=0;}dp[0]=1;int max;for(int i=1;i<n;i++){max=0;for(int j=0;j<i;j++){if(arr[j]<arr[i]){if(max<dp[j]){max=dp[j];}}}dp[i]=max+1;}max=-1;for(int i=0;i<n;i++){if(max<dp[i]){max=dp[i];}}return max;
}

 这是最经典的解法，代码时间复杂度为n^2 。下面我给大家带来一种时间复杂度为nlogn的算法。

算法优化

  整体思路不变，我们要做的是减少查找开销，也就是第二层循环。如果我们将dp数组变的有序，是不是就可以使用二分查找了呢？

  为此，我们引进数组end，end【i】代表递增子序列长度为i+1结尾位置的数字大小。具体思想如下：此时新来了一个数字x，从end数组中找第一个大于x的数字，我们用x取代它即可（递增子序列数字越小说明其扩充的可能性越大）。若没有比它大的数字，我们从end数组中开辟一个新的位置，并且赋值为x（x不能取代任何位置只能新增）。这样最终答案就是i+1了。

  其中查找数组中第一个比x大的元素时，我们使用二分查找仅需要logn水平，综合整个代码就是n*logn的。

//寻找有序数组中第一个比x大的元素没有返回-1 
int find(int *arr,int n,int x){int left=0,right=n-1,res=-1;int mid;while(left<=right){mid=(left+right)/2;if(arr[mid]<=x){left=mid+1;}else{res=mid;right=mid-1;}}return res;
}
int getmax2(int *arr,int n){int end[n],x,count=0;for(int i=0;i<n;i++){if(i==0){end[count++]=arr[i];continue;}x=find(end,count,arr[i]);if(x==-1){end[count++]=arr[i];}else{end[x]=arr[i];}}return count;
}

题目三 

算法分析 

  这道题设计一个知识点：我们求一个数是否可以整除3，可以将其各位相加得到新和再去整除3。即：假设判断123456能否取余3，我们可以根据1+2+3+4+5+6=21能否取余3判断。并且这个知识点是可逆的，我们判断1+2+3+4+5+6也可以判断1+2+3+4+56判断。

  这样这道题就很简单了。输入一个n，那么这个数代表1234.....n。我们可以根据1+2+3+4+...+n来判断，直接使用等差数列求和公式求出和即可。

代码展示

#include<iostream>
using namespace std;
int main(){int n;cin>>n;int sum=(1+n)*n/2;string str=sum%3==0?"可以整除":"不能整除"; cout<<str;
}

题目四

算法分析 

  这是一道贪心算法题目：怎么贪呢？如果i位置需要路灯，并且我们发现i+1位置也需要路灯，那我们就放在i+1位置。除此之外还有其它抉择：如果i位置是x，不能放路灯（规定），i++。如果i位置是、并且i+1位置是x，那么需要i位置放路灯，i=i+2。还有一种情况就是i和i+1都是、我们贪心一下，i=i+3。大家也要注意越界。当i位置是、并且i+1越界，那么需要i位置放路灯。

代码展示

#include<iostream>
using namespace std;
int getlight(string s){int count=0,i=0;while(i<s.length()){if(s[i]=='x'){i++;continue;}else{count++;if(i+1==s.length()){cout<<"结尾放路灯"<<endl;break;}else if(s[i+1]=='x'){cout<<"我是.我的后面是x"<<endl;i=i+2;}else if(s[i+1]=='.'){cout<<"我是.我的后面是."<<endl;i=i+3;}}}return count;
}
int main(){string s="x.x...x..x.x...x";int size=getlight(s);cout<<size;
}

题目五 

算法分析

   首先大家要知道为什么没有重复节点，若有重复节点，那么后序遍历结果不唯一。一般关于二叉树的题目，我们都使用递归的方法。

  我们知道了先序和中序遍历结果，那么先序的第一个元素就是后序的最后一个元素，我们可以直接填好。然后在中序结果中查找此元素，就可以将先序、中序、后序数组分为左右两部分。然后对左数组进行递归，对右数组进行递归即可。

代码展示

#include<iostream>
using namespace std;
int find(int *arr,int start,int end,int x){for(int i=start;i<=end;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(start1>end1||start2>end2||start3>end3){return;}if(start1==end1){pos[end3]=pre[start1];return;}pos[end3]=pre[start1];int x=find(in,start2,end2,pre[start1]);getpos(pre,in,pos,start1+1,start1+x-start2,start2,x-1,start3,start3+x-1-start2);//递归左 getpos(pre,in,pos,start1+x+1-start2,end1,x+1,end2,start3+x-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 i=0;i<7;i++){cout<<pos[i]<<" ";}
}

  大家注意左右数组的划分，这是重点！！并且我们求左数组长度时：找到了中序遍历中左数组结束位置，注意减去中序遍历开始位置 ！！大家不要误认为0！！

题目六

算法分析

  根据题目我们就可以知道这是一道前缀树问题，创建好前缀树只需要深搜遍历打印即可。

代码展示

  这是前缀树的通用模板。运用到改题目时：只需要在node节点添加一个data数据记录元素即可。最后深搜打印结果即可。

  对于深搜不了解的小伙伴们，查看我之前的文章：图（邻接矩阵）知识大杂烩！！（邻接矩阵结构，深搜，广搜，prim算法，kruskal算法，Dijkstra算法，拓扑排序）（学会一文让你彻底搞懂！！）-CSDN博客

#include<iostream>
#include<unordered_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->pass=0;n->end=0;for(int i=0;i<26;i++){n->next[i]=nullptr;}return n;
}
void insert(Node root,string str){Node node=root;int path;for(int i=0;i<str.length();i++){node->pass++;path=str[i]-'a';if(node->next[path]==nullptr){node->next[path]=create();}node=node->next[path];}node->pass++;//最后一个没有加 node->end++;
}
//寻找str出现多少次 
int possearch(Node root,string str){Node node=root;int path;for(int i=0;i<str.length();i++){path=str[i]-'a';if(node->next[path]==nullptr){return 0;}node=node->next[path];}return node->end; 
}
//寻找以str字符串作为前缀的字符串次数 
int presearch(Node root,string str){Node node=root;int path;for(int i=0;i<str.length();i++){path=str[i]-'a';if(node->next[path]==nullptr){return 0;}node=node->next[path];}return node->pass;
}
void deletenode(Node root,string str){if(!possearch(root,str)){cout<<"不存在该字符串无法删除"<<endl;return;}int path;Node node=root;node->pass--;for(int i=0;i<str.length();i++){path=str[i]-'a';if(node->next[path]->pass==1){node->next[path]=nullptr;return;}node=node->next[path]; node->pass--;}node->end--;
}
int main(){Node root=create();string str="abc";insert(root,str);str=str+"d";insert(root,str);deletenode(root,"abc");int findendsize=presearch(root,"abc");cout<<findendsize;
}

  本期算法分享到此结束！大家多多点赞支持！！