时间戳

首页 > 解决方案 > 为什么我的 Super Reduced String(HackerRank) 问题的解决方案在我的计算机上运行良好，但在 HackerRank 中给出错误答案？

c - 为什么我的 Super Reduced String(HackerRank) 问题的解决方案在我的计算机上运行良好，但在 HackerRank 中给出错误答案？

问题描述

当我在 Hackerrank 中运行我的代码时，它失败了 6/16 个测试用例，但是当我在我的计算机上尝试相同的测试用例时它工作正常。

这是我在计算机上运行的代码：（我使用 Clion 作为 ide，使用最新的 MinGW 作为编译器。）

我使用在 HackerRank 上失败的测试用例之一初始化字符串。

#include <string.h>
#include <stdio.h>
//#include <stdlib.h>
char* superReducedString(char* s);
int contain(char *S,char find);
void copyWithout(char *S,char *T,char trash);
int countWithout(char *S,char trash);
int findSize(char *S);
void fillString(char *S,char filler);
int main(){
    char s[] = {"ppffccmmssnnhhbbmmggxxaaooeeqqeennffzzaaeeyyaaggggeessvvssggbbccnnrrjjxxuuzzbbjjrruuaaccaaoommkkkkxx"};
    char *result = superReducedString(s);
    printf("%s",result);
}
int findSize(char *S){
    int i = 0;
    while(*(S+i) != '\0'){
        i++;
    }
    return i;
}
void fillString(char *S,char filler){
    int i = 0;
    while(*(S+i) != '\0'){
        *(S+i) = filler;
        i++;
    }
}
void copyWithout(char *S,char *T,char trash){
    fillString(T,'0');
    int i = 0;
    int count = 0;
    while(*(S+i) != '\0'){
        if(*(S+i) != trash){
            *(T+count) = *(S+i);
            count++;
        }
        i++;
    }
}
int countWithout(char *S,char trash){
    int i = 0;
    int count = 0;
    while(*(S+i) != '\0'){
        if(*(S+i) != trash){
            count++;
        }
        i++;
    }
    return count;
}
int contain(char *S,char find){
    int i = 0;
    int flag = 0;
    while(*(S+i) != '\0'){
        if(*(S+i) == find){
            flag = 1;
        }
        i++;
    }
    return flag;
}
char* superReducedString(char* s){
    static char empty[] = "Empty String";
    static char result[1024];
    int flag = 1;
    char temp[findSize(s)];
    fillString(temp,'0');
    int i,j;//Loop variable.
    i = 0;
    while(*(s + i) != '\0'){
        j = 0;
        //Checking if adjacent numbers is same. If it is changing them to '0'.
        while(s[j] != '\0') {
            if (s[j] == s[j + 1]) {
                *(s + j) = '0';
                *(s + j + 1) = '0';
            }
            j++;
        }
        if(contain(s,'0') == 0){ //If there is no zero in original string that means nothing changed.
            return s;
        }else{
            copyWithout(s,temp,'0');//If there are zeros in it, copy it to a temp char array without zeros.
        }
        strcpy(s,temp);//Copy temp to s again for swapping.
        i++;
    }
    int count = countWithout(s,'0'); //Calculate the size of original string without zeros.
    char finalString[count];//Initialize a new string with the calculated size.
    copyWithout(s,finalString,'0'); //Copy original string to finalString without zeros to obtain a clear zeroless string.
    strcpy(result,finalString);//copy finalstring to static result string to return it.
    i = 0;
    while(*(result+i) != '\0'){ //Check if result string consists of zeroes. If it is code will return empty string.
        if(*(result+i) != '0'){
            flag = 0;
        }
        i++;
    }
    if(flag == 0){
        return result;
    }else{
        return empty;
    }
}

这是我在 HackerRank 上运行的代码：

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* superReducedString(char* s);
int contain(char *S,char find);
void copyWithout(char *S,char *T,char trash);
int countWithout(char *S,char trash);
int findSize(char *S);
void fillString(char *S,char filler);
char* readline();
int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* s = readline();

    char* result = superReducedString(s);

    fprintf(fptr, "%s\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) {
            break;
        }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
            break;
        }

        alloc_length <<= 1;

        data = realloc(data, alloc_length);

        if (!data) {
            data = '\0';

            break;
        }
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';

        data = realloc(data, data_length);

        if (!data) {
            data = '\0';
        }
    } else {
        data = realloc(data, data_length + 1);

        if (!data) {
            data = '\0';
        } else {
            data[data_length] = '\0';
        }
    }

    return data;
}
int findSize(char *S){
    int i = 0;
    while(*(S+i) != '\0'){
        i++;
    }
    return i;
}
void fillString(char *S,char filler){
    int i = 0;
    while(*(S+i) != '\0'){
        *(S+i) = filler;
        i++;
    }
}
void copyWithout(char *S,char *T,char trash){
    fillString(T,'0');
    int i = 0;
    int count = 0;
    while(*(S+i) != '\0'){
        if(*(S+i) != trash){
            *(T+count) = *(S+i);
            count++;
        }
        i++;
    }
}
int countWithout(char *S,char trash){
    int i = 0;
    int count = 0;
    while(*(S+i) != '\0'){
        if(*(S+i) != trash){
            count++;
        }
        i++;
    }
    return count;
}
int contain(char *S,char find){
    int i = 0;
    int flag = 0;
    while(*(S+i) != '\0'){
        if(*(S+i) == find){
            flag = 1;
        }
        i++;
    }
    return flag;
}
char* superReducedString(char* s){
    static char empty[] = "Empty String";
    static char result[1024];
    int flag = 1;
    char temp[findSize(s)];
    fillString(temp,'0');
    int i,j,k;//Loop variable.
    i = 0;
    while(*(s + i) != '\0'){
        j = 0;
        while(s[j] != '\0') {
            if (s[j] == s[j + 1]) {
                *(s + j) = '0';
                *(s + j + 1) = '0';
            }
            j++;
        }
        if(contain(s,'0') == 0){
            return s;
        }else{
        //    printf("temp0 = %s s0 = %s\n",temp,s);
            copyWithout(s,temp,'0');
        //    printf("temp1 = %s s1 = %s\n",temp,s);
        }
        //printf("%s\n",temp);
        strcpy(s,temp);
        i++;
    }
    int count = countWithout(s,'0');
    char finalString[count];
    copyWithout(s,finalString,'0');
    strcpy(result,finalString);
    i = 0;
    while(*(result+i) != '\0'){
        if(*(result+i) != '0'){
            flag = 0;
        }
        i++;
    }
    if(flag == 0){
        return result;
    }else{
        return empty;
    }
}

唯一的区别是 main 函数和 HackerRank 用于获取输入的函数。

我不知道这是否有帮助，但有时我的代码可能会为相同的输入给出错误的答案。我的意思是：

输入=“acdqglrfkqyuqfjkxyqvnrtysfrzrmzlygfveulqfpdbhlqdqrrqdqlhbdpfqluevfgylzmrzrfsytrnvqyxkjfquyqkfrlacdqj”

虽然它应该给出“acdqgacdqj”作为答案，但它给出了“acdqgacdqjÑ”最后一个字符随机变化。

但是对于其他输入，无论我运行多少次，它都会在我的计算机上给出正确的答案。

标签： cstringchar

解决方案

  • char temp[findSize(s)]; fillString(temp,'0');是无效的。在fillString你迭代直到元素等于'\0'。temp未初始化 - 您不能期望它具有任何特定值（甚至读取未初始化的值也是未定义的行为）。
  • Inchar finalString[count]; count太小 - 它不考虑零终止字符。copyWithout(s,finalString,'0');没有复制零终止字符。这会导致在strcpy(result,finalString);搜索.... 零终止字符时访问数组越界。

使用 C 字符串时，您通常会+ 1在代码中到处看到神奇的东西。

建议：

  • 最好不要使用可变长度数组（大小表达式不是常量表达式的数组）。更喜欢使用动态分配。
  • findSize只是strlen……
  • fillString只是memset(string, value, strlen(string));
  • 使用编译器时，请始终启用所有选项。使用时gcc，您可以使用gcc -g -Wall -Wextra -fsanitize=address sourcefile.c- sanitize 将允许真正快速找到堆栈变量上的所有越界访问。用于valgrind查找动态分配泄漏。
  • 我建议将参数的顺序更改为copyWithout与- 即(destination, source, fill)相同。strcpy(destination, source)目的地是第一位的。

似乎将部分代码修复为：

char* superReducedString(char* s){
    ...
    // char temp[findSize(s)];
    char temp[findSize(s) + 1];
    // fillString(temp,'0');
    memset(temp, '0', findSize(s));
    temp[findSize(s)] = '\0';
    ...
    char finalString[count + 1];//Initialize a new string with the calculated size.
    memset(finalString, '0', count);
    finalString[count] = '\0';
}

足以让我-fsanitize停止犯错。

推荐阅读