对于MCMXCIV，C中的罗马到整数leetcode失败

zf2sa74q 于 2023-03-28 发布在其他

关注(0)|答案(4)|浏览(148)

s = "MCMXCIV"的最后一个测试用例不工作。输出是3099而不是1994。我已经将所有的罗马数字添加到整数中，但无法找出问题所在。前两个用例已正确执行，以给予预期的输出。

// code start
int romanToInt(char *s) {
    int sum = 0;
    if (*s == NULL) {
        return NULL;
    }
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == 'M') {
            sum = sum + 1000;
        }
        if (s[i] == 'D') {
            sum = sum + 500;
        }
        if (s[i] == 'C') {
            sum = sum + 100;
        }
        if (s[i] == 'L') {
            sum = sum + 50;
        }
        if (s[i] == 'X') {
            sum = sum + 10;
        }
        if (s[i] == 'V') {
            sum = sum + 5;
        }
        if (s[i] == 'I') {
            sum = sum + 1;
        }
        if (i > 0) {
            if (s[i] == 'V' && s[i - 1] == 'I') {
                sum = sum + 3;
            }
            if (s[i] == 'X' && s[i - 1] == 'I') {
                sum = sum + 8;
            }
            if (s[i] == 'L' && s[i - 1] == 'X') {
                sum = sum + 30;
            }
            if (s[i] == 'C' && s[i - 1] == 'X') {
                sum = sum + 80;
            }
            if (s[i] == 'D' && s[i - 1] == 'C') {
                sum = sum + 300;
            }
            if (s[i] == 'M' && s[i - 1] == 'C') {
                sum = sum + 800;
            }
        }
        //sum represents the converted integer
    }
    return sum;
}//code end

来源：https://stackoverflow.com/questions/75844454/roman-to-integer-leetcode-in-c-fails-for-mcmxciv

4条答案

按热度按时间

6gpjuf901#

存在多个问题：

将*s与NULL进行比较是不正确的：NULL是一个表示空指针的宏，*s不是指针，它是一个字符，你可以把它与'\0'或0进行比较。如果NULL被定义为0或0L，你的代码会偶然编译，但如果是另一个经典定义((void *)0)，就不会编译。
这个初始测试是无用的，因为for循环将立即停止一个空字符串。
测试i < strlen(s)可能会在每次迭代时重新计算字符串长度，这是低效的。您可以只测试if s[i] != '\0'。
罗马数字的规则很简单：如果一个字母的值小于下一个字母的值，则从下一个字母的值中减去该字母的值。

以下是修改后的版本：

int romanDigit(char c) {
    switch (c) {
      case 'I': return 1;
      case 'V': return 5;
      case 'X': return 10;
      case 'L': return 50;
      case 'C': return 100;
      case 'D': return 500;
      case 'M': return 1000;
      default: return 0;
    }
}

int romanToInt(const char *s) {
    int sum = 0;
    while (*s) {
        int digit = romanDigit(*s++);
        int next = romanDigit(*s);
        if (digit && digit < next) {
            sum += next - digit;
            s++;
        } else {
            sum += digit;
        }
    }
    return sum;
}

这种简单的实现适用于MCMXCIV（1994），但不会检测到无效数字，如MXMIV，MVMI，XMMIV ......这些数字也会产生1994。经典的表示法只在接下来的2个字母前面使用I，X和C，但是在Roman Numerals的漫长历史中已经发现了许多变化。
罗马数字体现了人类有史以来最持久的发明之一：计数。字母I，V和X的形状看起来与史前文物上发现的Tally marks惊人地相似。在最先进的科学出版物中看到石器时代穴居人用来计数的形状让我不寒而栗。

赞(0）回复(0）举报 2023-03-28

sycxhyv72#

这里有一个相当简单的程序来做这件事。注意，它不检查无效字符串。但它有一个更清晰的设计，并将实际的罗马值与计算它们的逻辑分离开来。
它使用这些规则：

重复的数字互相相加
较小的数字后面跟着较大的数字意味着减法
当上述任何一项完成后，计算结果并与其余部分相加

它不遵循这些规则

D、L和V不能重复
任何字母都不能重复超过3次
可减去的字母是I、X或C
减法必须用最大的可减字母

可能还有其他一些我没有执行的规则。
验证码：

#include <stdio.h>

int val(char c) {
    switch(c) {
    case 'M': return 1000;
    case 'D': return 500;
    case 'C': return 100;
    case 'L': return 50;
    case 'X': return 10;
    case 'V': return 5;
    case 'I': return 1; 
    default: return 0; // To make base case work
    }   
}

int roman(char *s) {
    char cur = *s;

    // Base case
    if(cur == 0) return 0;

    // Subtraction like IX
    char next = s[1];
    int diff = val(next) - val(cur);
    if(diff > 0) return diff + roman(&s[2]);

    // This takes care of repeating numbers, or just continues
    return val(cur) + roman(&s[1]);;
}
 
void printRoman(char *s) {
    printf("%s = %d\n", s, roman(s));
}
 
int main(void) {
    printRoman("M");
    printRoman("MM");
    printRoman("MMM");
    printRoman("MMMCM");
    printRoman("IV");
    printRoman("MCMXCIV");
}

输出：

M = 1000
MM = 2000
MMM = 3000
MMMCM = 3900
IV = 4
MCMXCIV = 1994

https://onlinegdb.com/poJLQy70C

赞(0）回复(0）举报 2023-03-28

htrmnn0y3#

在使用if()语句级联的OP方法之后，有以下内容。（注意没有不必要的花括号，并且使用了C的逗号运算符。）这利用了C的“配对”else与“最后一个else-less if”。

#include <stdio.h>

int romanToInt( char *s ) {
    int sum = 0;

    for( size_t i = 0; s[i]; i++ ) {
        char d = s[i], n = s[i+1]; // this 'd'igit and the 'n'ext...
        int v = 0;

             if( d == 'M' )     v = 1000;
        else if( d == 'D' )     v = 500;
        else if( d == 'C' )
                 if( n == 'M' ) v = 900, i++; // "CM" is two chars meaning 900
            else if( n == 'D' ) v = 400, i++; // ... and so on.
            else                v = 100;
        else if( d == 'L' )     v = 50;
        else if( d == 'X' )
                 if( n == 'C' ) v = 90, i++;
            else if( n == 'L' ) v = 40, i++;
            else                v = 10;
        else if( d == 'V' )     v = 5;
        else if( d == 'I' )
                 if( n == 'X' ) v = 9, i++;
            else if( n == 'V' ) v = 4, i++;
            else                v = 1;

        sum += v;
    }
    return sum;
}

int main( void ) {
    char *test[] = { "MCMXCIV", "MMXXIII", "MCDXCII" };

    for( size_t i = 0; i < sizeof test/sizeof test[0]; i++ )
        printf( "%d: %s - %d\n", i, test[i], romanToInt( test[i] ) );

    return 0;
}

0: MCMXCIV - 1994
1: MMXXIII - 2023
2: MCDXCII - 1492

没有努力确保源字符串是有效的罗马数字。

编辑：

另一方面，交织数据和处理可能会导致头痛。
对于像这样的转换，一个经过深思熟虑的存储Map的查找表可以通过一小段代码（如以下代码）来提供。

int romanToInt( char *ps ) {
    struct { int v; char *s; } rnc[] = {
        { 1000, "M"  }, {  900, "CM" }, {  500, "D"  }, {  400, "CD" },
        {  100, "C"  }, {   90, "XC" }, {   50, "L"  }, {   40, "XL" },
        {   10, "X"  }, {    9, "IX" }, {    5, "V"  }, {    4, "IV" },
        {    1, "I"  },
    }, *p = rnc;

    int val = 0;

    while( *ps )
        if( ( p->s[0] == ps[0] ) && ( p->s[1] == '\0' || p->s[1] == ps[1] ) )
            val += p->v, ps += 1 + (p->s[1] != '\0');
        else
            p++;

    return val;
}

编辑2：

花括号爱好者似乎不喜欢这个答案。
作为回应，这里是以前的版本修改，以检查和拒绝无效的罗马数字...易于维护时，设计已经健全：

int romanToInt( char *ps ) {
    struct { int v; char *s; int skip; } rnc[] = {
        { 1000, "M", 0 }, {  900, "CM", 4 }, {  500, "D", 2  }, {  400, "CD", 2 },
        {  100, "C", 0 }, {   90, "XC", 4 }, {   50, "L", 2  }, {   40, "XL", 2 },
        {   10, "X", 0 }, {    9, "IX", 4 }, {    5, "V", 2  }, {    4, "IV", 2 },
        {    1, "I", 0  },
    }, *p = rnc;

    int val = 0, cnt = 0;

    while( *ps && val >= 0 && p < sizeof rnc/sizeof rnc[0] )
        if( ( p->s[0] == ps[0] ) && ( p->s[1] == '\0' || p->s[1] == ps[1] ) )
            if( ++cnt > (p-skip ? 1 : 3) ) // Disallow some multiples
                val = -1;
            else
                val += p->v, // add the value
                ps += 1 + (p->s[1] != '\0'), // skip 1 or 2 chars of input
                p += p->skip, // advance to next(?) allowable substring
                cnt = p->skip ? 0 : cnt; // reset counter (if needed)
        else
            if( ++p > rnc + 12 )
                val = -1;
            else
                cnt = 0;

    return val;
}

int main( void ) {
    char *test[] = {
        "MCMXCIV", "MMXXIII", "MCDXCII", // all good
        "MCDCDXCII", "MCDXCCCCII", // both bad
        "III", "IIII" // good and bad
    };

    for( size_t i = 0; i < sizeof test/sizeof test[0]; i++ )
        printf( "%15s ==> %4d\n", test[i], romanToInt( test[i] ) );

    return 0;
}

输出：

MCMXCIV ==> 1994
        MMXXIII ==> 2023
        MCDXCII ==> 1492
      MCDCDXCII ==>   -1
     MCDXCCCCII ==>   -1
            III ==>    3
           IIII ==>   -1

赞(0）回复(0）举报 2023-03-28

nx7onnlm4#

你的基本方法是可靠的，但是你的条件顺序不正确，你可能想使用else来确保只有一个分支可以执行，因为字符是整数，你可以使用switch语句。
然后，您可以检查是否在第一个字符和continue上，以跳过循环剩余部分的控制流，在循环剩余部分中，您检查前面的字符，并直接进入下一次迭代。

for (int i = 0; i < strlen(s); i++) {
    switch (s[i]) {
        case 'M':
        sum += 1000;
        break;

        case 'D':
        sum += 500;
        break;

        case 'C':
        sum += 100;
        break;
 
        case 'L': 
        sum += 50;
        break;
       
        case 'X':
        sum += 10;
        break;
     
        case 'V':
        sum += 5;
        break;
  
        case 'I':
        sum += 1;
        break; 
    }

    if (i == 0) continue;

    if (s[i] == 'M' && s[i-1] == 'C') 
        sum -= 100;
    else if (s[i] == 'V' && s[i-1] == 'I')
        sum -= 1;
    // and so on...
}

赞(0）回复(0）举报 2023-03-28

我来回答

对于MCMXCIV，C中的罗马到整数leetcode失败

4条答案

相关问题

热门标签

最新问答