每日算法练习
大家好，今天给大家带来一些算法题，无他，只是想让大家认识一些题型，当以后遇到后会有头绪，能够使用优秀的算法。
题目一
一颗二叉树有n个节点，求最多有多少种二叉树形状。
题目分析
如果二叉树有0个节点，那么只有一种情况—空树；如果只有1个节点，那么只有一种情况—只有根节点；如果有两个节点，根节点占一个，我们先认为左侧节点有0个，那么右侧节点有一个，一种情况，当左侧节点有1个节点时，右侧无节点，也只有一种情况，两种情况相加共两种情况。这样我们就可以分析出解题思路：如果二叉树有n个节点，我们分别讨论二叉树左侧有0个，1个......n-1个节点时二叉树的数量，最后相加得到最终答案，每一次均为f(i)*f(n-i-1)。
代码分析
1.递归
int nodecount(int n){
if(n==0||n==1){
return 1;
}
int count=0;
for(int left=0;left<=n-1;left++){//减去一个根节点
count=count+nodecount(left)*nodecount(n-left-1);
}
return count;
}2.动态规划
int nodecount2(int n){
//n为有多少结点
int dp[n+1];
for(int i=0;i<n+1;i++){
dp[i]=0;
}
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++){//总共结点数目
for(int left=0;left<=i-1;left++){//左侧结点数目
dp[i]=dp[i]+dp[left]*dp[i-left-1];
}
}
return dp[n];
}题目二
给你一个字符串仅有‘(’和‘)’构成，判断括号是否匹配，如果不匹配需要补充多少括号。
题目分析
我想很多小伙伴拿到这道题目时，第一时间想到的是用栈解决。当然可以，不过有更简单的方法，只需要两个计数器count和ans即可。
我们从左到右遍历整个字符串，当遇见左括号时count++，遇到右括号时count--。如果字符串需要右括号才能达到匹配目的时，那么最后count为一个大于0的数，count的数量就是需要的右括号数量。当遍历时发现count==-1时，说明字符串肯定不匹配，需要补充左括号，此时我们令count再次等于0，然后ans++。最终ans记录的就是需要补充左括号的数量。ans+count的值就是我们需要的补充的括号数量。
代码分析
#include<iostream>
using namespace std;
void theminmatch(string str){
int count=0,ans=0;
for(int i=0;i<str.length();i++){
if(str[i]=='('){
count++;
}else{
count--;
}
if(count<0){
ans++;
count=0;
}
}
//括号匹配
if(!count&&!ans){
cout<<"无需添加"<<endl;
}
if(count){
cout<<"需要添加"<<count<<"个右括号"<<endl;
}
if(ans){
cout<<"需要添加"<<ans<<"个左括号"<<endl;
}
}
int main(){
string str="(((())()()()())";
theminmatch(str);
}题目三
有两个集合，我们想进行操作：将一个集合的元素移动到另一个集合中，并且达到让这两个集合的平均值均增大。求最多操作次数。
题目分析
首先，这两个集合应该不为空，否则无平均值这一概念。其次，当我们移动元素X到某集合时，若集合中包含X，那么该集合平均值不会发生变化（集合中相同元素当作一个元素），这是由集合性质决定的。
集合A平均值为ave1，集合B平均值为ave2。那么该如何移动呢？我们分情况讨论。
情况1：ave1=ave2：
我们从A移动元素X到B，若X<ave1，那么移动后ave1变大，ave2变小，不符合情况。X>ave1，那么移动后ave1变小，ave2变大，不符合情况。如果X=ave1，那么移动后ave和ave2均不变，不满足情况。因此ave1=ave2时，移动次数为0.
情况2：ave1<ave2（小移大）：
我们从A移动元素X到B，若X>ave1，移动后ave1减小，不符合情况。若X=ave1，移动后ave1不变，不符合情况。若X<ave1，移动后ave2变小，不符合情况。因此小集合向大集合移动时也不满足情况。
情况3：ave1>ave2（大移小）：
我们从A移动元素X到B，若X>ave1，移动后ave1减小，不符合情况。若X<ave2，移动后ave2减小不符合情况。若X=ave1或X=ave2，移动后肯定存在某个集合平均值不变，不符合情况。当X界于ave2和ave1时，移动后两个元素集合平均值均增大，满足情况。
此时我们知道何时才能移动，那么如果集合中有多个满足情况的元素呢？我们该优先移动小元素还是大元素呢？分析题目：移动次数最多！！肯定是优先移动小元素，因为移动小元素后ave1增长最大，ave2增加最小，二者差值最大，可能移动的次数最多。那如何保证我们先拿到小元素呢？对平均值大集合进行排序即可。
代码分析
#include<iostream>
#include<algorithm>
using namespace std;
int Sum(int *arr,int n){
int sum=0;
for(int i=0;i<n;i++){
sum=sum+arr[i];
}
return sum;
}
int *copy(int *arr,int n){
int *copy=new int[n];
for(int i=0;i<n;i++){
copy[i]=arr[i];
}
return copy;
}
bool notcontains(int *arr,int n,int x){
for(int i=0;i<n;i++){
if(arr[i]==x){
return 0;
}
}
return 1;
}
int main(){
int arr1[4]={1,5,2,7};
int arr2[5]={3,4,1,6,8};
int *min,*max,length,ans=0,l,cnt1,cnt2;
int sum1=Sum(arr1,4);
int sum2=Sum(arr2,5);
double average1=sum1*1.0/4;
double average2=sum2*1.0/5;
double minave,maxave;
if(average1==average2){
cout<<"0"<<endl;
return 0;
}
if(average1>average2){
max=copy(arr1,4);
min=copy(arr2,5);
sort(max,max+4);//对平均值大的数组进行排序
cnt1=length=4;
cnt2=l=5;
minave=average2;
maxave=average1;
}
else{
min=copy(arr1,4);
max=copy(arr2,5);
sort(max,max+5);
cnt1=length=5;
cnt2=l=4;
maxave=average2;
minave=average1;
}
//只能从大集合拿元素放到小集合才能满足两个集合平均值均变大 average1<x<average2
// 满足两个集合均不为空 移动到i集合时i集合不能有该元素 （集合两个相同元素相当于一个，平均值不变）
for(int i=0;i<length;i++){
if(max[i]>minave&&max[i]<maxave&¬contains(min,l,max[i])&&cnt1!=1){
//若有多个元素满足条件选小的
//这样可以保证大数组平均值加的多 小数组平均值加的少 保证最大magic次数
//这也是为什么对大数组进行排序的原因
ans++;
sum1=sum1-max[i];
sum2=sum2+max[i];
minave=(sum1*1.0)/(length-ans);//更新平均值
maxave=(sum2*1.0)/(l+ans);
cnt1--;
}
}
cout<<"最大挪动次数为"<<ans;
}有些小细节需要大家注意，算平均值时注意用double数据，思路比较简单，就是细节较多，大家多多注意。
题目四
给定一个字符串，只有左括号和右括号，字符串可能匹配也可能不匹配，求匹配的最长字串。
题目分析
首先我们应该区分子串和子序列，子串是连续的，子序列可以不连续。
我们这样考虑：dp【i】代表以i位置元素结尾所匹配的最大长度。当arr【i】为左括号时，dp【i】肯定为0。当arr【i】为右括号时，i前方dp【i-1】长度肯定已经匹配，此时我们需要看cur=i-dp【i-1】-1位置的元素，如果为右括号，那么dp【i】肯定为0。为什么呢？因为以cur位置元素结尾的最大匹配长度为0，如果不是0的话，那么dp【i-1】的值会变大，跟实际不符发生矛盾，因此cur位置为右括号时dp【i】=0。如果cur位置为左括号时，那么dp【i】长度至少为dp【i-1】+。此时我们需要看cur-1位置的dp值，最后dp【i】=dp【i】+dp【cur-1】。
代码分析
#include<iostream>
using namespace std;
int getmax(string s,int n){
int dp[n];//以i位置结尾的最大匹配串
for(int i=0;i<n;i++){
dp[i]=0;
}
dp[0]=0;
int cur;
for(int i=1;i<=n-1;i++){
if(s[i]=='('){
dp[i]=0;
continue;//以左括号结尾肯定不匹配
}
dp[i]=dp[i]+dp[i-1];//*****)此时状态
cur=i-dp[i-1]-1;//检查*前一位
if(cur<0){
dp[i]=0;//如果没有肯定跟最后的右括号无法对应为0
continue;
}
if(s[cur]==')'){
dp[i]=0;//如果*前一位为），那么肯定不会存在（（####）*****）
//因为如果cur有匹配的话 i-1位置匹配长度会更长矛盾
continue;
}
dp[i]=dp[i]+2;//如果cur为左括号（*****）在原来基础上加2（首尾）
//最后加上cur-1位置的dp值只需一次，因为该处记录了此处为结尾的最大匹配值
if(cur-1<0){
continue;
}
dp[i]=dp[i]+dp[cur-1];
}
int max=-1;
for(int i=0;i<n;i++){
cout<<dp[i]<<" ";
if(max<dp[i]){
max=dp[i];
}
}
cout<<endl;
return max;//返回最大值
}
int main(){
string str="(())(())";
int max=getmax(str,str.length());
cout<<max;
}大家注意是否有越界的可能，小细节不能忽略。
题目五
给定一个二维数组，保证其行列均按照从小到大的顺序，但整体无序。求二维数组中是否存在元素X。
题目分析
很重要的一个条件就是行列有序！我们如果从数组右上角开始的话，比较当前位置元素和X大小关系，如果相等则返回。如果该元素小于X，那么行下标加一，列下标不变。如果该元素大于X，那么行下标不变，列下标减一。如果最后越界，说明不存在。没有越界说明存在。
我们这样操作每次移动一行或一列，为O（m+n）的算法，而普通的遍历为O（m*n）。
代码分析
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int arr[n][m];//数组每一行和每一列均是从小到大有序，但整体不有序
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>arr[i][j];
}
}
//查找数组中是否存在元素X
int x;
cout<<"输入想查找的元素"<<endl;
cin>>x;
int curx=0,cury=m-1,flag=0;
while(arr[curx][cury]!=x){
if(arr[curx][cury]>x){
cury=cury-1;
}
else if(arr[curx][cury]<x){
curx=curx+1;
}
if(curx<0||curx>n-1||cury<0||cury>m-1){
flag=1;
break;
}
}
if(!flag){
cout<<"元素所在位置为："<<curx+1<<" "<<cury+1<<endl;
}
else{
cout<<"不存在该元素"<<endl;
}
} 题目六
给定一个二维数组，元素只有0和1，且保证每一行：0在左侧，1在右侧（可以全0或全1）。求行中最多1的数量。
题目分析
我们还是从右上角开始，一直向左走记录1的数量，当遇见0后向下走，对每一行均进行这种操作，最后count的值就是1的最大数量。
代码分析
#include<iostream>
using namespace std;
//数组只有0，1，且每一行1均在右侧，0均在左侧（可以全1或全0）
//求行中最多1的数量
int main(){
int n,m;
cin>>n>>m;
int arr[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>arr[i][j];
}
}
int curx=0,cury=m-1,count=0;
while(curx<=n-1){
while(cury>=0&&arr[curx][cury]==1){
cury--;
count++;
}
curx++;
}
cout<<count;
}要注意一直向左走时的越界问题。
本次算法练习到此结束，希望大家多多点赞支持。