本文主要是介绍LeetCode 第177场周赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.日期之间隔几天
【思路】计算两个日期和1970-1-1之间相隔的天数,然后相减即可。需要注意闰年闰月的判断。
int getday(int *d1){int month[12]={31,28,31,30,31,30,31,31,30,31,30,31};int day1=0,i;for(i=1970;i<d1[0];i++){if(i%400==0||(i%100!=0&&i%4==0)){day1+=366;}else{day1+=365;}}for(i=1;i<d1[1];i++){day1+=month[i-1];if(i==2){if(d1[0]%400==0||(d1[0]%4==0&&d1[0]%100!=0)){day1++;}}}day1+=d1[2];return day1;
}
int* getdate(char * date){int i,len,top=0;int *num=(int*)malloc(sizeof(int)*3);// memset(num,0,sizeof(num));num[0]=0;num[1]=0;num[2]=0;len=strlen(date);for(i=0;i<len;i++){if(date[i]=='-'){top++;continue;}num[top]=num[top]*10+date[i]-'0';}return num;
}
int daysBetweenDates(char * date1, char * date2){int day1=0,day2=0;int *d1=(int*)malloc(sizeof(int)*3),*d2=(int*)malloc(sizeof(int)*3);d1=getdate(date1);d2=getdate(date2);day1=getday(d1);day2=getday(d2);return abs(day2-day1);
}
2.验证二叉树:
【思路】给了两个数组leftchild和rightchild,这两个数组中存了n个节点的子节点情况。其中,leftchild[i]和rightchild[i]代表了节点i的两个子节点,如果是-1,代表空节点。首先需要判断每个子节点是否存在多个父节点,如果存在,那么直接返回false。最后在所有节点都不存在多个父节点的情况下,判断除了根节点外 都有一个父节点。
bool validateBinaryTreeNodes(int n, int* leftChild, int leftChildSize, int* rightChild, int rightChildSize){int father[100000];int i,j;memset(father,-1,sizeof(father));
//判断当前节点i的子节点存在的情况下,是否有多个父节点,若有,直接返回false;否则,更新当前子节点的父节点为ifor(i=0;i<leftChildSize;i++){if(leftChild[i]!=-1&&father[leftChild[i]]==-1){father[leftChild[i]]=i;}else if(leftChild[i]!=-1&&father[leftChild[i]]!=-1){return false;}}for(i=0;i<rightChildSize;i++){if(rightChild[i]!=-1&&father[rightChild[i]]==-1){father[rightChild[i]]=i;}else if(rightChild[i]!=-1&&father[rightChild[i]]!=-1){return false;}}int sum=0;for(i=0;i<n;i++){//判断除了根节点之外,是否都有父节点if(father[i]==-1){sum++;}}return sum==1;
}
3.最接近的因数
【思路】寻找乘积为num+1或者num+2中相距最小的一组。
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* closestDivisors(int num, int* returnSize){int i,j;int *number=(int*)malloc(sizeof(int)*2);number[0]=-num;number[1]=num+100;for(j=1;j<=2;j++){for(i=1;i*i<=num+j;i++){if((num+j)%i==0){if(abs((num+j)/i-i)<abs(number[1]- number[0])){number[1]=(num+j)/i;number[0]=i;}}}}*returnSize=2;return number;
}
4.形成三的最大倍数
【思路】将所有数对3取余数;可能存在三种情况,余数为0,1,2.我们分别用d0,d1,d2来存相应的数。
如果我们发现各位数字相加sum%3==0,那么这些数字组合的数一定可以被3整除;
如果sum%3==1,要么从d1中删除一个数,要么从d2中删除两个数;
如果sum%3==2,要么从d2中删除一个数,要么从d1中删除两个数。
以确保最后组成的数值最大。
int cmp(const void*a,const void*b)
{return *(int*)b-*(int*)a;
}char *remove2(int *digits, int digitsSize,int key1,int key2,int sum){//移除两个数int flag=0;int tmp=0;char *rst=(char*)malloc(sizeof(char)*(digitsSize+1));if((sum-key1-key2)==0){if((digitsSize-2)==0){rst[0]='\0';}else{rst[0]='0';rst[1]='\0';}return rst;}for(int i=0;i<digitsSize;i++){if(digits[i]==key2&&flag==0){flag=1;continue;}if(digits[i]==key1&&flag==1){flag=2;continue;}rst[tmp++]=digits[i]+'0';}rst[tmp]='\0';return rst;
}
char *remove1(int *digits, int digitsSize,int key,int sum){//移除一个数int flag=0; int tmp=0;char *rst=(char*)malloc(sizeof(char)*(digitsSize+1));if((sum-key)==0){if((digitsSize-1)==0){rst[0]='\0';}else{rst[0]='0';rst[1]='\0';}return rst;}for(int i=0;i<digitsSize;i++){if(digits[i]==key&&flag==0){flag=1;continue;}rst[tmp++]=digits[i]+'0';}rst[tmp]='\0';return rst;
}
char * largestMultipleOfThree(int* digits, int digitsSize){int i,tmp=0;int sum=0,top[3]={0};char *rst=(char*)malloc(sizeof(char)*(digitsSize+1));int* d0=(int*)malloc(sizeof(int)*(digitsSize+1));int* d1=(int*)malloc(sizeof(int)*(digitsSize+1));int* d2=(int*)malloc(sizeof(int)*(digitsSize+1));rst[0]='\0';if(digitsSize==0)return rst;qsort(digits,digitsSize,sizeof(int),cmp);//从小到大排序,对3取余数后,余数为i则存入di中for(i=digitsSize-1;i>=0;i--){sum+=digits[i];rst[tmp++]=digits[digitsSize-i-1]+'0';if(digits[i]%3==0){d0[top[0]++]=digits[i];}else if(digits[i]%3==1){d1[top[1]++]=digits[i];}else{d2[top[2]++]=digits[i];}}rst[tmp]='\0';if(sum==0){rst[0]='0';rst[1]='\0';return rst;}if(sum%3==1){if(top[1]!=0){rst=remove1(digits,digitsSize,d1[0],sum);}else if(top[2]>=2){rst=remove2(digits,digitsSize,d2[0],d2[1],sum);}else{rst[0]='\0';}}else if(sum%3==2){if(top[2]!=0){rst=remove1(digits,digitsSize,d2[0],sum);}else if(top[1]>=2){rst=remove2(digits,digitsSize,d1[0],d1[1],sum);}else{rst[0]='\0';}}return rst;
}
这篇关于LeetCode 第177场周赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!