yoruru的努力日記

179. Largest Number

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

SOL：

解題思路參考：【每日一题】179. Largest Number, 9/26/2020

如同Huifeng Guan說的，這個解法好實現，但並不容易想出來。

解法是先將nums轉換成string，qsort排序後再將它們連成 Largest Number(string) 再回傳。

用C++寫起來容易的，用Ｃ語言又有更多細節要注意（累

程式：

#define STR_SIZE 10
int cmp(const void *s1, const void *s2){
    const char *rec1 = *(char**)s1;
    const char *rec2 = *(char**)s2;
    char result1[20];
    strcpy(result1, rec1);
    strcat(result1, rec2);
    char result2[20];
    strcpy(result2, rec2);
    strcat(result2, rec1);
    int val = strcmp(result1, result2);
    return val;
}

char * largestNumber(int* nums, int numsSize){
    char** StrNums = (char**)malloc(sizeof(char*)*numsSize);
    for(int i = 0; i < numsSize; i++){
        StrNums[i] = (char*)malloc(sizeof(char)*STR_SIZE);
        sprintf(StrNums[i], "%d", nums[i]);
    }
    qsort(StrNums,numsSize,sizeof(char*),cmp);

    // char *result=(char *)malloc(sizeof(char)*500);
    static char result[500];
    strcpy(result, StrNums[(numsSize-1)]);
    for(int i = numsSize-2; i >= 0; i--){
        strcat(result, StrNums[i]);
    }
    if(result[0]=='0')
        return "0";
    return result;
}

首先就是 qsort的cmp要怎麼寫：

雖然在前兩天 [LeetCode-C] 56. Merge Intervals 我就有用過 qsort，但對於字串數組的排序，還是要再找一下資料。

How to use qsort for an array of strings?

順利用 qsort 之後，結果大概會是這樣：

nums = [3,30,34,5,9]

排序前（已經有先把nums轉成string）
StrNums[0]=3
StrNums[1]=30
StrNums[2]=34
StrNums[3]=5
StrNums[4]=9

排序後
StrNums[0]=30
StrNums[1]=3
StrNums[2]=34
StrNums[3]=5
StrNums[4]=9

接下來就是要把答案倒序連接起來，並回傳。

結果這也能出包，我不管 return &result; 還是 return a; output都是null。(心累again
後來發現是因為 char * largestNumber 是一個函式，程式呼叫完區域變數 result 就被清除了，所以要用malloc/static。

Returning a C string from a function

宣告一個500 char大小的string來存答案（剛好看到有人用500個就跟著用了。
此外，連接字串除了strcpy+strcat的寫法，也可以用memset+memcpy。

程式（另一種寫法）：

#define STR_SIZE 10
int cmp(const void *s1, const void *s2){
    const char *rec1 = *(char**)s1;
    const char *rec2 = *(char**)s2;
    char result1[20];
    strcpy(result1, rec1);
    strcat(result1, rec2);
    char result2[20];
    strcpy(result2, rec2);
    strcat(result2, rec1);
    int val = strcmp(result1, result2);
    return val;
}

char * largestNumber(int* nums, int numsSize){
    char** StrNums = (char**)malloc(sizeof(char*)*numsSize);
    for(int i = 0; i < numsSize; i++){
        StrNums[i] = (char*)malloc(sizeof(char)*STR_SIZE);
        sprintf(StrNums[i], "%d", nums[i]);
    }
    qsort(StrNums,numsSize,sizeof(char*),cmp);

    char *result=(char *)malloc(sizeof(char)*500);
    int idx = 0;
    memset(result, 0, 500);
    for(int i = numsSize-1; i >= 0; i--){
        memcpy(result+idx, StrNums[i], strlen(StrNums[i]));
        idx += strlen(StrNums[i]);
    }
    result[idx]='\0';
    if(result[0]=='0')
        return "0";
    return result;
}

最後處理 "00" 這種狀況時，因為題目是要找最大數，所以答案不會有 "01" 這種答案，如果輸入是 0, 1，那答案必定是 "10"，因為1比較大一定會在前面。所以只要檢查第一個字是 '0'，就可以直接 return "0"。

3/30重新練習一次，把 strcpy+strcat 全都改成 memset+memcpy ，然後想到可以把 string nums free掉。

int cmp(void* s1, void* s2){
    const char* c1 = *(char**)s1;
    const char* c2 = *(char**)s2;
    char r1[20];
    memset(r1,0,20);
    memcpy(r1,c1,strlen(c1));
    memcpy(r1+strlen(c1),c2,strlen(c2));
    char r2[20];
    memset(r2,0,20);
    memcpy(r2,c2,strlen(c2));
    memcpy(r2+strlen(c2),c1,strlen(c1));
    return strcmp(r1,r2);
}

char * largestNumber(int* nums, int numsSize){
    char ** strs = (char**)malloc(sizeof(char*)*numsSize);
    for(int i = 0; i < numsSize; i++){
        strs[i]=(char*)(malloc)(sizeof(char)*10);
        sprintf(strs[i],"%d",nums[i]);
        // printf("str[%d]=%s\n",i,strs[i]);
    }
    qsort(strs,numsSize,sizeof(strs[0]),cmp);
    static char ans[500];
    int idx=0;
    memset(ans,0,500);
    for(int i = numsSize-1; i >= 0; i--){
        memcpy(ans+idx,strs[i],strlen(strs[i]));
        idx += strlen(strs[i]);
        free(strs[i]);
        // printf("str[%d]=%s\n",i,strs[i]);
    }
    ans[idx]='\0';
    free(strs);
    if(ans[0]=='0')
        return "0";
    return ans;
}