目录
第1题：翻转单词顺序
第2题：顺时针打印矩阵
第3题：总持续时间可被 60 整除的歌曲
第4题：字符串的最大公因子
第5题：上升下降字符串
第6题：将数组分成和相等的三个部分
第7题：可被 5 整除的二进制前缀
第8题：去除重复字母
第9题：重构字符串
第10题：三角形的最大周长
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：翻转单词顺序
试题要求如下：
回答（C语言）：
char* reverseWords(char* s){ // 去掉尾部的空格。最终至少留下一个空格，除非本身长度就为0 int n = strlen(s); while(n > 0 && s[n-1] == ' ') n--; // 去掉头部的空格 int front = 0; if(n > 0){ while(s[front] == ' ') front++; } // 如果为空，返回 if( n - front == 0) return ""; // 创建字符指针，长度大于等于实际长度 char *p = (char *)calloc(n + 1 - front, sizeof(char)); int index = 0; // 这是新字符串的下标 for( int i = n-1 , j = n-1; i >= front ; i--){ // 该写入单词了 if(i == front || (s[i] == ' ' && i != j) ){ int k = i + 1; // 如果到头了，那头也应该写入 if(i == front) k--; for(; k <= j ; k++,index++){ p[index] = s[k]; } // 注意！单词后要加上空格 if(i != front) p[index] = s[i]; j = i - 1; index = index + 1; } // 中间空格多时要跳过 else if(s[i] == ' '){ j--; } } return p; }
运行效率如下所示：
第2题：顺时针打印矩阵
试题要求如下：
解题思路：
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){ if(!matrixSize){ *returnSize=0; return NULL; } int ColSize=*matrixColSize; *returnSize=matrixSize*ColSize; int num=*returnSize; int* val=(int*)malloc(sizeof(int)*num); int x=0,y=0; int count=0; int no; while(count<num){ no=0; //左到右 while(no++<ColSize&&count<num){ val[count++]=matrix[y][x++]; } y++,x--,matrixSize--,no=0; //上到下 while(no++<matrixSize&&count<num){ val[count++]=matrix[y++][x]; } y--,x--,ColSize--,no=0; //右到左 while(no++<ColSize&&count<num){ val[count++]=matrix[y][x--]; } x++,y--,matrixSize--,no=0; //下到上 while(no++<matrixSize&&count<num){ val[count++]=matrix[y--][x]; } ColSize--,y++,x++; } return val; }
运行效率如下所示：
第3题：总持续时间可被 60 整除的歌曲
试题要求如下：
回答（C语言）：
int numPairsDivisibleBy60(int* time, int timeSize){ int temp[61] = {0}; int cnt = 0; //统计余数出现的次数，余数作为下标 for(int i = 0;i < timeSize;i++) { temp[time[i]%60]++; } //余数为0和30的情况，对数为组合Cn2 = n*（n-1）/2 cnt = temp[0]*(temp[0] - 1)/2 + temp[30]*(temp[30] - 1)/2; //余数为其他情况，每个余数i都能够与余数60-i配对，所以对数为temp[i]*temp[60-i] for(int i = 0;i < 30;i++) { cnt = cnt +temp[i]*temp[60-i]; } return cnt; }
运行效率如下所示：
第4题：字符串的最大公因子
试题要求如下：
解题思路：
递归法。
1、保证当前str1长度大于等于str2(通过判断交换实现)；
2、如果当前str1长度大于str2，且str1的前部与str2不一致，那么它们之间不存在公因字串；
3、如果当前str1长度大于str2，且str1的前部与str2一致，否则截取str1后面部分重新与str2比较；
4、如果当前str1与str2一致，则最大公因子就是本身。
回答（C语言）：
char * gcdOfStrings(char * str1, char * str2){ int len1 = strlen(str1); int len2 = strlen(str2); if (len2 > len1) { char *tmp = str1; str1 = str2; str2 = tmp; len2 = len1; } if (memcmp(str1, str2, len2)) { return ""; } else if (str1[len2] == '\0' && str2[len2] == '\0') { return str1; } return gcdOfStrings(str1 + len2, str2); }
运行效率如下所示：
第5题：上升下降字符串
试题要求如下：
回答（C语言）：
char* sortString(char* s) { int num[26]; memset(num, 0, sizeof(num)); int n = strlen(s); for (int i = 0; i < n; i++) { num[s[i] - 'a']++; } char* ret = malloc(sizeof(char) * (n + 1)); int retSize = 0; while (retSize < n) { for (int i = 0; i < 26; i++) { if (num[i]) { ret[retSize++] = i + 'a'; num[i]--; } } for (int i = 25; i >= 0; i--) { if (num[i]) { ret[retSize++] = i + 'a'; num[i]--; } } } ret[retSize] = 0; return ret; }
运行效率如下所示：
第6题：将数组分成和相等的三个部分
试题要求如下：
解题思路：
1、求和，若和不是3的倍数，直接false；
2、求和的三分之一，从头开始遍历累加，遇到等于和三分之一，跳出循环，并指向下一个元素；
3、继续遍历求和，若等于和的三分之二，跳出循环；
4、判断此时的位置，如果是最后一位，则不符合条件，false，否则true。
回答（C语言）：
bool canThreePartsEqualSum(int* A, int ASize){ int sum = 0,i,j,temp,sum1 = 0; //求和，若和不是3的倍数，直接false for(int i = 0;i < ASize;i++) { sum = sum + A[i]; } if(sum%3 != 0) return false; //求和的三分之一 temp = sum/3; //遍历累加，遇到等于和三分之一，跳出循环，并指向下一个元素 for(i = 0;i < ASize;i++) { sum1 = sum1 + A[i]; if(sum1 == temp) break; } //继续遍历求和，若等于和的三分之二，跳出循环 for(j = i + 1;j < ASize;j++) { sum1 = sum1 + A[j]; if(sum1 == temp*2) break; } //判断此时的位置，如果是最后一位，则不符合条件，false，否则true if(j > ASize - 2) return false; else return true; }
运行效率如下所示：
第7题：可被 5 整除的二进制前缀
试题要求如下：
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ bool* prefixesDivBy5(int* A, int ASize, int* returnSize) { int temp = 0; *returnSize = ASize; bool* ret = (bool*)malloc(ASize * sizeof(bool)); for (int i = 0; i < ASize; i++) { temp = (temp << 1) + A[i]; temp = temp % 5; if (temp == 0) { ret[i] = true; } else { ret[i] = false; } } return ret; }
运行效率如下所示：
第8题：去除重复字母
试题要求如下：
解题思路：
1、初始化一个数组recode[26];
2、遍历s记录每个字母出现的次数;
3、新建一个栈，遍历s进行入栈；
4、遍历栈，如果s[i]存在于栈中，则recode[s[i]-’a‘]--,并且继续下一次遍历；
5、否则比较栈顶字母和s[i]的大小，如果stack[top]>s[i]并且recode[stack[top]-'a']>1(说明stack[top]在后边还会出现)就出栈，并且recode[s[i]-’a‘]--；
6、入栈；
7、最后stack[++top]=’\0‘转成字符串。
回答（C语言）：
char * removeDuplicateLetters(char * s){ if (s == NULL || strlen(s) == 0) { return ""; } if (strlen(s) == 1) { return s; } int len = (int)strlen(s); //注意，这里需要初始化为0 char recode[26] = {0}; for (int i=0; i<len; i++) { recode[s[i] - 'a']++; } char * stack = (char *)malloc(sizeof(char) * (len+1)); int top = -1; int isExist; for (int i=0; i<len; i++) { isExist = 0; for (int j=0; j<=top; j++) { if (s[i] == stack[j]) { isExist = 1; break; } } if (isExist) { recode[s[i] - 'a']--; }else{ while(top>-1 && stack[top] > s[i] && recode[stack[top] - 'a'] > 1) { //如果栈顶字符比当前大，并且后边还会出现 recode[stack[top] - 'a']--; //出栈 top--; } //入栈 stack[++top] = s[i]; } } stack[++top] = '\0'; return stack; }
运行效率如下所示：
第9题：重构字符串
试题要求如下：
回答（C语言）：
int cmp(const void* a , const void* b) { int *aa = (int*)a; int *bb = (int*)b; /* sort from big to small */ return bb[0] - aa[0]; } char * reorganizeString(char * S){ int rcnt = 0; int len = strlen(S); char * ret = (char *)malloc(sizeof(char)*len+1); memset(ret, 0, sizeof(char)*len+1); int a[26][2] = {0}; for (int i = 0; i < len; i++) { a[S[i] - 'a'][0]++; a[S[i] - 'a'][1] = S[i] - 'a'; } int tmp = 0; while (rcnt < len) { tmp = 0; qsort(a, 26, sizeof(int)*2, cmp); for (int i = 0; i < 26 && tmp < 2; i++) { if (a[i][0] > 0) { ret[rcnt++] = 'a' + a[i][1]; tmp++; a[i][0]--; } } } for (int i = 1; i < rcnt; i++) { if (ret[i] == ret[i-1]) { return ""; } } return ret; }
运行效率如下所示：
C
第10题：三角形的最大周长
试题要求如下：
解题思路：
三角形两边之和，一定大于第三边。
回答（C语言）：
int cmp(void *_a, void *_b) { int a = *(int *)_a, b = *(int *)_b; return a - b; } int largestPerimeter(int *A, int ASize) { qsort(A, ASize, sizeof(int), cmp); for (int i = ASize - 1; i >= 2; --i) { if (A[i - 2] + A[i - 1] > A[i]) { return A[i - 2] + A[i - 1] + A[i]; } } return 0; }
运行效率如下所示：
