力扣(LeetCode)定期刷题，每期 10 道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
试题要求如下：
回答（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;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
回答（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;}
复制代码
运行效率如下所示：
试题要求如下：
回答（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;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
递归法。
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);}
复制代码
运行效率如下所示：
试题要求如下：
回答（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;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
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;}
复制代码
运行效率如下所示：
试题要求如下：
回答（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;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
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;}
复制代码
运行效率如下所示：
试题要求如下：
回答（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 语言）：
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;}
复制代码
运行效率如下所示：
评论