目錄

第1題：翻轉(zhuǎn)單詞順序

第2題：順時針打印矩陣

第3題：總持續(xù)時間可被 60 整除的歌曲

第4題：字符串的最大公因子

第5題：上升下降字符串

第6題：將數(shù)組分成和相等的三個部分

第7題：可被 5 整除的二進制前綴

第8題：去除重復(fù)字母

第9題：重構(gòu)字符串

第10題：三角形的最大周長

---

力扣(LeetCode)定期刷題，每期10道題，業(yè)務(wù)繁重的同志可以看看我分享的思路，不是最高效解決方案，只求互相提升。

第1題：翻轉(zhuǎn)單詞順序

試題要求如下：

回答（C語言）：

char* reverseWords(char* s){// 去掉尾部的空格。最終至少留下一個空格，除非本身長度就為0int 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 "";// 創(chuàng)建字符指針，長度大于等于實際長度char *p = (char *)calloc(n + 1 - front, sizeof(char));int index = 0; // 這是新字符串的下標(biāo)for( int i = n-1 , j = n-1; i >= front ; i--){// 該寫入單詞了if(i == front || (s[i] == ' ' && i != j) ){int k = i + 1;// 如果到頭了，那頭也應(yīng)該寫入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題：總持續(xù)時間可被 60 整除的歌曲

試題要求如下：

回答（C語言）：

int numPairsDivisibleBy60(int* time, int timeSize){int temp[61] = {0};int cnt = 0;//統(tǒng)計余數(shù)出現(xiàn)的次數(shù)，余數(shù)作為下標(biāo)for(int i = 0;i < timeSize;i++){temp[time[i]%60]++;}//余數(shù)為0和30的情況，對數(shù)為組合Cn2 = n*（n-1）/2cnt = temp[0]*(temp[0] - 1)/2 + temp[30]*(temp[30] - 1)/2;//余數(shù)為其他情況，每個余數(shù)i都能夠與余數(shù)60-i配對，所以對數(shù)為temp[i]*temp[60-i]for(int i = 0;i < 30;i++){cnt = cnt +temp[i]*temp[60-i];}return cnt;
}

運行效率如下所示：

---

第4題：字符串的最大公因子

試題要求如下：

解題思路：

遞歸法。

1、保證當(dāng)前str1長度大于等于str2(通過判斷交換實現(xiàn))；

2、如果當(dāng)前str1長度大于str2，且str1的前部與str2不一致，那么它們之間不存在公因字串；

3、如果當(dāng)前str1長度大于str2，且str1的前部與str2一致，否則截取str1后面部分重新與str2比較；

4、如果當(dāng)前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題：將數(shù)組分成和相等的三個部分

試題要求如下：

解題思路：

1、求和，若和不是3的倍數(shù)，直接false；

2、求和的三分之一，從頭開始遍歷累加，遇到等于和三分之一，跳出循環(huán)，并指向下一個元素；

3、繼續(xù)遍歷求和，若等于和的三分之二，跳出循環(huán)；

4、判斷此時的位置，如果是最后一位，則不符合條件，false，否則true。

回答（C語言）：

bool canThreePartsEqualSum(int* A, int ASize){int sum = 0,i,j,temp,sum1 = 0;//求和，若和不是3的倍數(shù)，直接falsefor(int i = 0;i < ASize;i++){sum = sum + A[i];}if(sum%3 != 0) return false;//求和的三分之一temp = sum/3;//遍歷累加，遇到等于和三分之一，跳出循環(huán)，并指向下一個元素for(i = 0;i < ASize;i++){sum1 = sum1 + A[i];if(sum1 == temp) break;}//繼續(xù)遍歷求和，若等于和的三分之二，跳出循環(huán)for(j = i + 1;j < ASize;j++){sum1 = sum1 + A[j];if(sum1 == temp*2) break;}//判斷此時的位置，如果是最后一位，則不符合條件，false，否則trueif(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題：去除重復(fù)字母

試題要求如下：

解題思路：

1、初始化一個數(shù)組recode[26];

2、遍歷s記錄每個字母出現(xiàn)的次數(shù);

3、新建一個棧，遍歷s進行入棧；

4、遍歷棧，如果s[i]存在于棧中，則recode[s[i]-’a‘]--,并且繼續(xù)下一次遍歷；

5、否則比較棧頂字母和s[i]的大小，如果stack[top]>s[i]并且recode[stack[top]-'a']>1(說明stack[top]在后邊還會出現(xiàn))就出棧，并且recode[s[i]-’a‘]--；

6、入棧；

7、最后stack[++top]=’\0‘轉(zhuǎn)成字符串。

回答（C語言）：

char * removeDuplicateLetters(char * s){if (s == NULL || strlen(s) == 0) {return "";}if (strlen(s) == 1) {return s;}int len = (int)strlen(s);//注意，這里需要初始化為0char 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) {//如果棧頂字符比當(dāng)前大，并且后邊還會出現(xiàn)recode[stack[top] - 'a']--;//出棧top--;}//入棧stack[++top] = s[i];}}stack[++top] = '\0';return stack;
}

運行效率如下所示：

---

第9題：重構(gòu)字符串

試題要求如下：

回答（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;
}

運行效率如下所示：

---

第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;
}

運行效率如下所示：

總結(jié)

以上是生活随笔為你收集整理的力扣(LeetCode)刷题，简单+中等题(第28期)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。