力扣 (LeetCode) 刷题，简单 + 中等题 (第 26 期)

/** * Note: The returned array must be malloced, assume caller calls free(). */#define MY_MAX 20char 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);}

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

/** * 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;}

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

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

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

/** * 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;}

/** * 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;}

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

/** * 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;}