HackerRank字符串数组排序程序部分测试用例失败求助

问题背景 #

我在完成字符串数组排序题目时，编写的C语言程序有3个测试用例未通过，以下是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <string.h>

int lexicographic_sort(const char* a, const char* b) {
    if (strcmp(a,b)>0)
    return 1;
    else
    return 0;
}

int lexicographic_sort_reverse(const char* a, const char* b) {
    if (strcmp(a,b)<0)
    return 1;
    else
    return 0;
}

int sort_by_number_of_distinct_characters(const char* a, const char* b) {
    int count1[26]={0},count2[26]={0};
    
    for (int i = 0; i < strlen(a); i++)
    {
        count1[a[i]-97]++;
    }
    for (int i = 0; i < strlen(b); i++)
    {
        count2[b[i]-97]++;
    }
    int distict1=0,distict2=0;
    
    for (int i = 0; i < 26; i++)
    {
        if (count1[i]>0)
        distict1++;
        if (count2[i]>0)
        distict2++;
    }

    if (distict1>distict2)
    {
        return 1;
    }
    else if (distict1<distict2)
    {
        return 0;
    }
    else
    {
        return lexicographic_sort(a,b);
    }
    
}

int sort_by_length(const char* a, const char* b) {
    if (strlen(a)>strlen(b))
    return 1;
    else if (strlen(a)<strlen(b))
    return 0;
    else
    return lexicographic_sort(a,b);
}

void string_sort(char** arr,const int len,int (*cmp_func)(const char* a, const char* b)){


    char store[2500];
    
    for (int j = 0; j < len - 1; j++)
    {
        for (int i = 0; i < len - j - 1; i++)
        {
            if ((*cmp_func)(arr[i],arr[i+1]))
            {
                strcpy(store,arr[i]); 
                strcpy(arr[i],arr[i+1]);
                strcpy(arr[i+1],store);
            }
        }
    }

}


int main() 
{
    int n;
    scanf("%d", &n);
  
    char** arr;
    arr = (char**)malloc(n * sizeof(char*));
  
    for(int i = 0; i < n; i++){
        *(arr + i) = malloc(1024 * sizeof(char));
        scanf("%s", *(arr + i));
        *(arr + i) = realloc(*(arr + i), strlen(*(arr + i)) + 1);
    }
  
    string_sort(arr, n, lexicographic_sort);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]);
    printf("\n");

    string_sort(arr, n, lexicographic_sort_reverse);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]); 
    printf("\n");

    string_sort(arr, n, sort_by_length);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]);    
    printf("\n");

    string_sort(arr, n, sort_by_number_of_distinct_characters);
    for(int i = 0; i < n; i++)
        printf("%s\n", arr[i]); 
    printf("\n");
}

失败的测试用例输入 #

24
kkhcvkjrjcbyqixf
rbbxaogunbzkusueaycmhvvlwwdg
jdnmekotqiiuhuocqveozqyuol
mpbhaeumlebgxlotvkjxaedqfvqblcuxrxfrbbfmi
sfuiarujowqtnvodxaftz
qerrixgqfax
jxsdgicwbpssursc
rccyuvgtbyycvcnuuscfuziltagms
ymmamgvuzzsabpeqjailfdm
ohqwtlitxvtjdrddqxftmjjxlrkrwzhngxlci
xhprssixxauetipchbv
usrbhzasdlmbsduly
kvefczprbxuyposirzjuupfiszmmmkqxhwe
vtdyqzwhorrhsdbmsivmkjywvqveozqjvtjlshviyosr
tflecxolxmgnil
jdmewxsqfnbfdtwxoeisgiiufv
vdnyoqntoklhraixfdvcrzlkgvsacncxs
yhkncbxnkppsmuvjxmjkyrhrtjgvjbphkcumdtbpiqh
meglsrvrickbosyxvqefsar
tumemvczbk
tbimlmwoarnzmffuzfnybikhuhlviwidzsqngobjfqiuv
outduwlefinrdvpnbofrdmffvnvfjtt
ppckloqt
ekbbzrcpyvtmbajqxpzsiyixculqmgosqsurl

预期输出 #

ekbbzrcpyvtmbajqxpzsiyixculqmgosqsurl
jdmewxsqfnbfdtwxoeisgiiufv
jdnmekotqiiuhuocqveozqyuol
jxsdgicwbpssursc
kkhcvkjrjcbyqixf
kvefczprbxuyposirzjuupfiszmmmkqxhwe
meglsrvrickbosyxvqefsar
mpbhaeumlebgxlotvkjxaedqfvqblcuxrxfrbbfmi
ohqwtlitxvtjdrddqxftmjjxlrkrwzhngxlci
outduwlefinrdvpnbofrdmffvnvfjtt
ppckloqt
qerrixgqfax
rbbxaogunbzkusueaycmhvvlwwdg
rccyuvgtbyycvcnuuscfuziltagms
sfuiarujowqtnvodxaftz
tbimlmwoarnzmffuzfnybikhuhlviwidzsqngobjfqiuv
tflecxolxmgnil
tumemvczbk
usrbhzasdlmbsduly
vdnyoqntoklhraixfdvcrzlkgvsacncxs
vtdyqzwhorrhsdbmsivmkjywvqveozqjvtjlshviyosr
xhprssixxauetipchbv
yhkncbxnkppsmuvjxmjkyrhrtjgvjbphkcumdtbpiqh
ymmamgvuzzsabpeqjailfdm

ymmamgvuzzsabpeqjailfdm
yhkncbxnkppsmuvjxmjkyrhrtjgvjbphkcumdtbpiqh
xhprssixxauetipchbv
vtdyqzwhorrhsdbmsivmkjywvqveozqjvtjlshviyosr
vdnyoqntoklhraixfdvcrzlkgvsacncxs
usrbhzasdlmbsduly
tumemvczbk
tflecxolxmgnil
tbimlmwoarnzmffuzfnybikhuhlviwidzsqngobjfqiuv
sfuiarujowqtnvodxaftz
rccyuvgtbyycvcnuuscfuziltagms
rbbxaogunbzkusueaycmhvvlwwdg
qerrixgqfax
ppckloqt
outduwlefinrdvpnbofrdmffvnvfjtt
ohqwtlitxvtjdrddqxftmjjxlrkrwzhngxlci
mpbhaeumlebgxlotvkjxaedqfvqblcuxrxfrbbfmi
meglsrvrickbosyxvqefsar
kvefczprbxuyposirzjuupfiszmmmkqxhwe
kkhcvkjrjcbyqixf
jxsdgicwbpssursc
jdnmekotqiiuhuocqveozqyuol
jdmewxsqfnbfdtwxoeisgiiufv
ekbbzrcpyvtmbajqxpzsiyixculqmgosqsurl

ppckloqt
tumemvczbk
qerrixgqfax
tflecxolxmgnil
jxsdgicwbpssursc
kkhcvkjrjcbyqixf
usrbhzasdlmbsduly
xhprssixxauetipchbv
sfuiarujowqtnvodxaftz
meglsrvrickbosyxvqefsar
ymmamgvuzzsabpeqjailfdm
jdmewxsqfnbfdtwxoeisgiiufv
jdnmekotqiiuhuocqveozqyuol
rbbxaogunbzkusueaycmhvvlwwdg
rccyuvgtbyycvcnuuscfuziltagms
outduwlefinrdvpnbofrdmffvnvfjtt
vdnyoqntoklhraixfdvcrzlkgvsacncxs
kvefczprbxuyposirzjuupfiszmmmkqxhwe
ekbbzrcpyvtmbajqxpzsiyixculqmgosqsurl
ohqwtlitxvtjdrddqxftmjjxlrkrwzhngxlci
mpbhaeumlebgxlotvkjxaedqfvqblcuxrxfrbbfmi
yhkncbxnkppsmuvjxmjkyrhrtjgvjbphkcumdtbpiqh
vtdyqzwhorrhsdbmsivmkjywvqveozqjvtjlshviyosr
tbimlmwoarnzmffuzfnybikhuhlviwidzsqngobjfqiuv

ppckloqt
qerrixgqfax
tumemvczbk
tflecxolxmgnil
usrbhzasdlmbsduly
jxsdgicwbpssursc
kkhcvkjrjcbyqixf
xhprssixxauetipchbv
outduwlefinrdvpnbofrdmffvnvfjtt
rccyuvgtbyycvcnuuscfuziltagms
sfuiarujowqtnvodxaftz
jdmewxsqfnbfdtwxoeisgiiufv
jdnmekotqiiuhuocqveozqyuol
meglsrvrickbosyxvqefsar
ymmamgvuzzsabpeqjailfdm
vtdyqzwhorrhsdbmsivmkjywvqveozqjvtjlshviyosr
ohqwtlitxvtjdrddqxftmjjxlrkrwzhngxlci
vdnyoqntoklhraixfdvcrzlkgvsacncxs
yhkncbxnkppsmuvjxmjkyrhrtjgvjbphkcumdtbpiqh
kvefczprbxuyposirzjuupfiszmmmkqxhwe
rbbxaogunbzkusueaycmhvvlwwdg
ekbbzrcpyvtmbajqxpzsiyixculqmgosqsurl
mpbhaeumlebgxlotvkjxaedqfvqblcuxrxfrbbfmi
tbimlmwoarnzmffuzfnybikhuhlviwidzsqngobjfqiuv

问题排查结果 #

程序存在两个核心问题导致测试用例失败：

1. 比较函数返回值不符合排序逻辑约定 #

C语言排序算法要求比较函数返回负数、0、正数，分别对应a < b、a == b、a > b。但你的比较函数仅返回0或1，会让排序算法错误判断元素顺序，尤其是处理相等元素或需要逆序的场景。

修正后的核心比较函数：

int lexicographic_sort(const char* a, const char* b) {
    return strcmp(a, b);
}

int lexicographic_sort_reverse(const char* a, const char* b) {
    return strcmp(b, a);
}

同时sort_by_length和sort_by_number_of_distinct_characters中，当长度或不同字符数相等时，直接调用修正后的lexicographic_sort即可。

2. 字符串交换方式存在缓冲区溢出风险 #

你在string_sort中用固定大小的char store[2500]复制字符串，若测试用例中存在更长的字符串会导致缓冲区溢出，破坏内存数据。更高效且安全的方式是直接交换字符串指针：

修正后的string_sort：

void string_sort(char** arr, const int len, int (*cmp_func)(const char* a, const char* b)) {
    for (int j = 0; j < len - 1; j++) {
        for (int i = 0; i < len - j - 1; i++) {
            if (cmp_func(arr[i], arr[i+1]) > 0) {
                char* temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
    }
}

其他细节优化 #

• 去掉重复的头文件包含：#include <stdio.h>和#include <string.h>各写了两次，可删除重复项；
• 修正变量名拼写错误：distict1/distict2改为distinct1/distinct2（不影响逻辑，但提升代码可读性）。

应用以上修正后，程序即可通过所有测试用例。

内容的提问来源于stack exchange，提问作者Aryan Mane