目录
第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; i--) {
if (a[i] == ']') {
right = i;
} else if(a[i] == '[') {
left = i;
} else if (a[i] >= '0' && a[i] = 0 && (a[i] >= '0' && a[i] 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;
}
}
}运行效率如下所示：
试题要求如下：
解题思路：
遍历所有的字符串，记录（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;
}运行效率如下所示：
试题要求如下：
回答（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;
}运行效率如下所示：
试题要求如下：
回答（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;
}运行效率如下所示：
试题要求如下：
回答（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;inext;
}
for (int i = 0, j = vals_num - 1; i < j; ++i, --j) {
if (vals[i] != vals[j]) {
return false;
}
}
return true;
}运行效率如下所示：
试题要求如下：
回答（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;
}运行效率如下所示：
试题要求如下：
解题思路：
1、初始化哈希表，定义max = -1；
2、如果当前字符第一次出现，记下当前下标i；
3、如果字符已经出现过，利用当前下标i减去表中的记录值tmp，判断如果max小于tmp，则更新max，否则不更新；
4、释放缓冲区hash。
回答（C语言）：
#define Max( a , b ) ( ( a > b ) * a + ( a = 0; i--) {
int temp = arr[1];
arr[1] = arr[0];
arr[0] = cont[i] * arr[1] + temp;
}
*returnSize = 2;
return arr;
}运行效率如下所示：
