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

運行效率如下所示：