目录
第1题:有序数组的平方
第2题:增减字符串匹配
第3题:数字的补数
第4题:Nim游戏
第5题:删除字符串中的所有相邻重复项
第6题:除数博弈
第7题:转换成小写字母
第8题:生成每种字符都是奇数个的字符串
第9题:按奇偶排序数组
第10题:转置矩阵
力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。
第1题:有序数组的平方
试题要求如下:
回答(C语言):
/** * Note: The returned array must be malloced, assume caller calls free(). */ int cmp (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int* sortedSquares(int* A, int ASize, int* returnSize){ *returnSize=ASize; for(int i=0;i<ASize;i++){ A[i]=A[i]*A[i]; } qsort(A, ASize, sizeof(int), cmp); return A; }
运行效率如下所示:
第2题:增减字符串匹配
试题要求如下:
回答(C语言):
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* diStringMatch(char * S, int* returnSize) { int N = strlen(S); int a=N; int b=0; int *ret = (int *)malloc(sizeof(int)*(N+1)); *returnSize = N + 1; for (int i=0;i<N;i++){ if (S[i] == 'I'){ ret[i] = b; b++; } else{ ret[i] = a; a--; } } ret[N] = b; return ret; }
运行效率如下所示:
第3题:数字的补数
试题要求如下:
回答(C语言):
int findComplement(int num){ long temp = 1; while (num >= temp){ temp <<= 1; } return (temp - 1 - num); }
运行效率如下所示:
第4题:Nim游戏
试题要求如下:
回答(C语言):
bool canWinNim(int n){ return (n % 4 != 0); }
运行效率如下所示:
第5题:删除字符串中的所有相邻重复项
试题要求如下:
回答(C语言):
char * removeDuplicates(char * S){ int i, cnt, len = strlen(S); for(i = 1, cnt = 0;i <= len;++i) { if(cnt == -1 || S[i] != S[cnt]) S[++cnt] = S[i]; else --cnt; } return S; }
运行效率如下所示:
第6题:除数博弈
试题要求如下:
回答(C语言):
bool divisorGame(int N){ // 如果爱丽丝拿到奇数,则必输, // 因为奇数的因数必为奇数,则N-x必为偶数, // 鲍勃拿到偶数之后,只需要-1交还给爱丽丝,则爱丽丝再次拿到奇数, // 这样鲍勃永远拿到偶数,直到拿到2赢下比赛 // 反过来,如果爱丽丝拿到偶数,只需要-1给鲍勃,那么鲍勃就必输。 return N%2==0; }
运行效率如下所示:
第7题:转换成小写字母
试题要求如下:
回答(C语言):
char * toLowerCase(char * str){ for(int i=0;i<strlen(str);i++){ if(str[i]>='A'&&str[i]<='Z') str[i]=str[i]+32; } return str; }
运行效率如下所示:
第8题:生成每种字符都是奇数个的字符串
试题要求如下:
回答(C语言):
char * generateTheString(int n) { char *ret=(char *)malloc(sizeof(char)*(n+1)); ret[n]='\0'; memset(ret,'a',n); ret[n-1]='a'+(n%2==0); return ret; }
运行效率如下所示:
第9题:按奇偶排序数组
试题要求如下:
回答(C语言):
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* sortArrayByParity(int* A, int ASize, int* returnSize){ int i=0,j=ASize-1; int temp=0; while(i<j){ if(A[i]%2!=0 && A[j]%2==0){ temp=A[j]; A[j]=A[i]; A[i]=temp; } if(A[i]%2==0) i++; if(A[j]%2!=0) j--; } *returnSize=ASize; return A; }
运行效率如下所示:
第10题:转置矩阵
试题要求如下:
回答(C语言):
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int** transpose(int** A, int ASize, int* AColSize, int* returnSize, int** returnColumnSizes){ int** num=(int**)malloc(sizeof(int*)*(*AColSize)); *returnColumnSizes=(int*)malloc(sizeof(int)*(*AColSize)); *returnSize=*AColSize; //分配内存 for(int i=0;i<*AColSize;i++){ num[i]=(int*)malloc(sizeof(int)*ASize); returnColumnSizes[0][i] = ASize; } //矩阵转置 for(int i=0;i<ASize;i++){ for(int j=0;j<*AColSize;j++){ num[j][i]=A[i][j]; } } return num; }
运行效率如下所示: