目录
第1题：字典序排数
第2题：字符串解码
第3题：查找常用字符
第4题：所有奇数长度子数组的和
第5题：长按键入
第6题：分割字符串的最大得分
第7题：回文链表
第8题：有多少小于当前数字的数字
第9题：两个相同字符之间的最长子字符串
第10题：分式化简
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
中等题，可太吃力了，我觉得刷题C语言费劲。
第1题：字典序排数
试题要求如下：
解题思路：
字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ #define MY_MAX 20 char g_sa[MY_MAX]; char g_sb[MY_MAX]; int cmp(const void *a, const void *b) { int *pa = (int*)a; int *pb = (int*)b; sprintf(g_sa, "%d", *pa); sprintf(g_sb, "%d", *pb); return strcmp(g_sa, g_sb); } int* proc(int n, int* returnSize){ int i; int *rlt = (int*)calloc(n, sizeof(int)); if (rlt == NULL) { return NULL; } for (i = 0; i < n; i++) { rlt[i] = i + 1; } qsort(rlt, n, sizeof(int), cmp); *returnSize = n; return rlt; } int* lexicalOrder(int n, int* returnSize){ if (n <= 0) { returnSize = 0; return NULL; } return proc(n, returnSize); }
运行效率如下所示：
第2题：字符串解码
试题要求如下：
解题思路：
从右向左扫描，发现符合条件的，就替换，然后继续从右向左扫描，直到没有[]需要替换为止。
回答（C语言）：
char *decodeString(char *s) { if (s == NULL) { return NULL; } char *a = strdup(s); while (true) { int len = strlen(a); int left = 0, right = len; int i = len - 1, num = 0, w = 1; for (; i >= 0; i--) { if (a[i] == ']') { right = i; } else if(a[i] == '[') { left = i; } else if (a[i] >= '0' && a[i] <= '9') { do { // 组合数字 num += w * (a[i] - '0'); w *= 10; i--; } while (i >= 0 && (a[i] >= '0' && a[i] <= '9')); break; } } if (num == 0) { //没有[]了 return a; } else { int slen = (right - left - 1); int count = (i + 1) + (len - right - 1) + num * slen + 1; char *t = (char*)calloc(count, sizeof(char)); if (i + 1 > 0) { // 左 memcpy(t, a, i + 1); } for (int k = 0; k < num; k++) { // 中 memcpy(t + (i + 1) + k * slen, a + left + 1, slen); } if (len - right - 1 > 0) { memcpy(t + (i + 1) + num * slen, a + right + 1, len - right - 1); } free(a); a = t; } } }
运行效率如下所示：
第3题：查找常用字符
试题要求如下：
解题思路：
遍历所有的字符串，记录（26个小写字母）每个字符在所有字符串中都出现过的“最小”次数，则为结果。
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ char ** commonChars(char ** A, int ASize, int* returnSize){ if (NULL == A || 0 == ASize) { *returnSize = 0; return NULL; } int minfreq[26]; // 记录每个‘字符’出现的最小频率 int freq[26]; // 缓存每个字符串中每个’字符‘出现的频率 for (int i = 0; i < 26; i++) { minfreq[i] = INT_MAX; } // 遍历所有字符串 for (int i = 0; i < ASize; i++) { // 遍历每个字符串前，重置’字符‘出现的频率 memset(freq, 0, sizeof(freq)); int n = strlen(A[i]); // 当前字符串长度 // 遍历当前字符串 for (int j = 0; j < n; j++) { int idx = A[i][j] - 'a'; // 字符的下标 ++freq[idx]; // 统计’字符‘出现的次数 } // 每遍历一个字符串，都需更新所有字符出现的最小频率 for (int k = 0; k < 26; k++) { minfreq[k] = fmin(minfreq[k], freq[k]); } } // 计算结果字符 int sum = 0; for (int i = 0; i < 26; i++) { sum += minfreq[i]; } // 构造结果字符列表 char** result = (char**)malloc(sizeof(char*) * sum); *returnSize = 0; for (int i = 0; i < 26; i++) // 遍历 26 个小写字符 { for (int j = 0; j < minfreq[i]; j++) // 遍历每个‘字符’在所有字符串中都出现的最小次数 { result[*returnSize] = (char*)malloc(sizeof(char) * 2); // 每个字符串都有结束符，所以需 +1 result[*returnSize][0] = i + 'a'; // 第 i 个字符 result[*returnSize][1] = '\0'; // '\0' 作为字符串结束标识 (*returnSize)++; } } return result; }
运行效率如下所示：
第4题：所有奇数长度子数组的和
试题要求如下：
回答（C语言）：
int sumOddLengthSubarrays(int* arr, int arrSize){ int res = 0; for (int i = 0; i < arrSize; i++) { for (int j = 1; j < arrSize - i + 1; j += 2) { for (int m = i; m < i + j; m++) { res = res + arr[m]; } } } return res; }
运行效率如下所示：
第5题：长按键入
试题要求如下：
回答（C语言）：
bool isLongPressedName(char* name, char* typed) { int n = strlen(name), m = strlen(typed); int i = 0, j = 0; while (j < m) { if (i < n && name[i] == typed[j]) { i++; j++; } else if (j > 0 && typed[j] == typed[j - 1]) { j++; } else { return false; } } return i == n; }
运行效率如下所示：
第6题：分割字符串的最大得分
试题要求如下：
回答（C语言）：
int max(int x,int y){ return x>y?x:y; } int maxScore(char * s){ int l=strlen(s); int lsum=0; int rsum=0; int maxN=0; for(int i=0;i<l-1;i++){ if(s[i]=='0') lsum++; for(int j=i+1;j<l;j++){ if(s[j]=='1'){ rsum++; } } maxN=max(maxN,lsum+rsum); rsum=0; } return maxN; }
运行效率如下所示：
第7题：回文链表
试题要求如下：
解答思路：
1、复制链表值到数组列表中；
2、使用双指针法判断是否为回文。
回答（C语言）：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool isPalindrome(struct ListNode* head) { int vals[50001], vals_num = 0; while (head != NULL) { vals[vals_num++] = head->val; head = head->next; } for (int i = 0, j = vals_num - 1; i < j; ++i, --j) { if (vals[i] != vals[j]) { return false; } } return true; }
运行效率如下所示：
第8题：有多少小于当前数字的数字
试题要求如下：
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) { int* ret = malloc(sizeof(int) * numsSize); *returnSize = numsSize; for (int i = 0; i < numsSize; i++) { int cnt = 0; for (int j = 0; j < numsSize; j++) { if (nums[j] < nums[i]) { cnt++; } } ret[i] = cnt; } return ret; }
运行效率如下所示：
第9题：两个相同字符之间的最长子字符串
试题要求如下：
解题思路：
1、初始化哈希表，定义max = -1；
2、如果当前字符第一次出现，记下当前下标i；
3、如果字符已经出现过，利用当前下标i减去表中的记录值tmp，判断如果max小于tmp，则更新max，否则不更新；
4、释放缓冲区hash。
回答（C语言）：
#define Max( a , b ) ( ( a > b ) * a + ( a <= b ) * b ) int maxLengthBetweenEqualCharacters( char * s ){ //creating hash table int * hash = ( int * )malloc( sizeof( int ) * 26 ); int max = -1; //intializing hash table for( int i = 0 ; i < 26 ; i++ ) { hash[ i ] = -1; } for( int i = 0 ; s[ i ] != '\0' ; i++ ) { if( hash[ s[ i ] - 97 ] != -1 ) { max = Max( max , ( i - hash[ s[ i ] - 97 ] - 1 ) ); } else { hash[ s[ i ] - 97 ] = i; } } free( hash ); return max; }
运行效率如下所示：
第10题：分式化简
试题要求如下：
解题思路：
回答（C语言）：
/** * arr[0]: 分子 * arr[1]: 分母 * * 1、简单的通分，因为每次都是 1/a，所以需要分数翻转，即分子分母交换一下 * 2、这题不需要约分，本来就是最简 */ int* fraction(int* cont, int contSize, int* returnSize) { int* arr = (int*)malloc(sizeof(int) * 2); arr[0] = 1; arr[1] = 0; for (int i = contSize - 1; i >= 0; i--) { int temp = arr[1]; arr[1] = arr[0]; arr[0] = cont[i] * arr[1] + temp; } *returnSize = 2; return arr; } 运行效率如下所示：
运行效率如下所示：
