罗马整数 - 但使用 "different" 罗马数字系统

Question

我接受了一次面试，结果很糟糕。所以，现在我正试图找到问题的解决方案。这是采访问题：

“我们有以下映射：
M:1000,D:500,C:100,L:50,X:10,V:5,I:1.

我们有以下规则：

每个字母对应一个正整数值
您将这些值相加，除了...
...当一个值（或运行个相同值）后跟一个更大的值时，您减去该运行个值的总和。

示例：

IIX -> 8

MCCMIIX -> 1808

我们得到了这个 Java 方法：int valueOfRoman(char roman)。我们已经实现了 Java 方法：int romanToInt(String s)"

我知道这不是一个正确的罗马数字系统，但这是实际问题。

我能够为一个合适的罗马系统编写一个可行的解决方案。但我无法更改它以使其适应这些新规则，尤其是规则 3。我已经尝试过，但没有成功。我现在的解决方案是，对于 IIX，它打印 10，而不是正确答案 8。这是我的代码（我还为测试实现了 valueOf）：

static int romanToInt(String s) {
    char curr;
    int currVal;
    char prev;
    int prevVal;

    int total = valueOfRoman(s.charAt(0));

    for (int i = 1; i < s.length(); i++) {
        curr = s.charAt(i);
        currVal = valueOfRoman(curr);

        prev = s.charAt(i-1);
        prevVal = valueOfRoman(prev);

        total += currVal;
        if(currVal > prevVal) {
            total = total - (2*prevVal);
        }

    }
    return total;
}


static int valueOfRoman(char c) {
    if (c == 'M') {
        return 1000;
    } else if (c == 'D') {
        return 500;
    } else if (c == 'C') {
        return 100;
    } else if (c == 'L') {
        return 50;
    } else if (c == 'X') {
        return 10;
    } else if (c == 'V') {
        return 5;
    } else if (c == 'I') {
        return 1;
    } 

    return -1;
}

非常感谢任何帮助。如果您能告诉我如何修改我的代码，那将特别有用。谢谢！

编辑：我编辑了方法的名称，使它们更清晰。

Answer 1

以下是我解决问题的方法：

逐个字符读取字符串，并在每一步中记下当前字符和前一个字符。
- 如果当前字符与前一个字符相同，则运行长度增加1。
- 如果当前字符的值小于前一个字符的值，则将运行长度 * 前一个字符的值添加到总数，并将运行长度重置为1。
- 如果当前字符的值大于前一个字符的值，则减去 运行长度 * 前一个字符的值 总数，并将运行长度重置为1。

Answer 2

这种问题通常用递归的思路很容易解决。解决方案可能如下所示：

public int rom2int(String s)
{               
    if(s.length() == 0)   
        // no string --> 0
        return  0;
    else if(s.length() == 1)
        // One Character --> Value of Character
        return valueOf(s.charAt(0)); 
    else if((valueOf(s.charAt(0)) > valueOf(s.charAt(1))) ) 
        // The value is NOT followed by a greater value --> We had the value
        return rom2int(s.substring(1, s.length())) + valueOf(s.charAt(0));      
    else if(valueOf(s.charAt(0)) <= valueOf(s.charAt(1)) )
        // The value is followed by a greater (or same) value --> We substract the value
        return rom2int(s.substring(1, s.length())) - valueOf(s.charAt(0));
    else
        // Shouldn't Happen. 0 as neutral element in in a Sum.
        return 0;
}

即使禁止递归解决方案，在我看来，反递归该算法比第一次尝试找到过程算法更简单 =)

编辑：我的结果：

Value of MCCMIIX is : 1808

Value of IIX is : 8

Value of IVX is : 4

Value of IIVVL is : 38

Answer 3

我的看法。

编辑更改 #2

public class Romans {

private int valueOf(char c) {
    if (c == 'M') {
        return 1000;
    } else if (c == 'D') {
        return 500;
    } else if (c == 'C') {
        return 100;
    } else if (c == 'L') {
        return 50;
    } else if (c == 'X') {
        return 10;
    } else if (c == 'V') {
        return 5;
    } else if (c == 'I') {
        return 1;
    }

    return 0;
}

public int rom2int(String s) {
    int currVal;
    int runValue = 0;
    int repetition = 0;
    int total = 0;
    boolean alreadyAdded = false;
    for (int i = 0; i < s.length(); i++) {
        currVal = valueOf(s.charAt(i));
        if (runValue == 0) {
            runValue = currVal;
            repetition = 1;
            alreadyAdded = false;
        } else if (currVal > runValue) {
            total = total + (currVal - (runValue * repetition));
            repetition = 1;
            runValue = currVal;
            alreadyAdded = true;
        } else if (currVal < runValue) {
            if(!alreadyAdded) {
                total += (runValue * repetition);
            }
            repetition = 1;
            runValue = currVal;
            alreadyAdded = false;
        } else {
            repetition++;
            alreadyAdded = false;
        }
    }

    if (!alreadyAdded) {
        total += (runValue * repetition);
    }

    return total;
}

}

主要是我运行:

public static void main(String[] args) {
    Romans r = new Romans();
    String[] inputs =  {"MVVV", "IIX","MCCMIIX", "IVX"};
    for(String input : inputs) {
        System.out.println("Value of " + input + " is: " + r.rom2int(input));
    }
}

输出：

Value of MVVV is: 1015
Value of IIX is: 8
Value of MCCMIIX is: 1808
Value of IVX is: 9

Answer 4

我的看法 - 使用您提供的公认的小测试。

static int rom2int(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    // Total value.
    int total = 0;
    // The most recent.
    char current = s.charAt(0);
    // Total for the current run.
    int run = valueOf(current);

    for (int i = 1; i < s.length(); i++) {
        char next = s.charAt(i);
        int value = valueOf(next);
        if (next == current) {
            // We're in a run - just keep track of its value.
            run += value;
        } else {
            // Up or down?
            if (value < valueOf(current)) {
                // Gone down! Add.
                total += run;
            } else {
                // Gone UP! Subtract.
                total -= run;
            }
            // Run ended.
            run = valueOf(next);
        }
        // Kee track of most recent.
        current = next;
    }
    return total + run;
}

private void test(String s) {
    System.out.println("Value of " + s + " = " + rom2int(s));
}

public void test() {
    test("IVX");
    test("IIVVL");
    test("IIX");
    test("MCCMIIX");
    test("MVVV");
}

打印

Value of IVX = 4 - Odd!!!
Value of IIVVL = 38
Value of IIX = 8
Value of MCCMIIX = 1808
Value of MVVV = 1015

Answer 5

我就是这样做的。

它适用于您提到的那两个值（IIX = 8 和 MCCMIIX = 1808）：

public static int rom2int(String s)
{
    int currVal = 0, prevVal = 0, subTotal = 0, total = 0;
    for (int i = 0; i < s.length(); i++) {
        currVal = valueOf(s.charAt(i));
        if (currVal > 0) {
            if (prevVal == 0) {
                subTotal = currVal;
            }
            else if (currVal > prevVal) {
                total += (currVal - subTotal);
                subTotal = 0;
            }
            else if (currVal < prevVal) {
                total += subTotal;
                subTotal = currVal;
            }
            else if (currVal == prevVal) {
                subTotal += currVal;
            }
            prevVal = currVal;
        }
    }
    total += subTotal;
    return total;
}

public static int valueOf(char c)
{
    if (c == 'M')
        return 1000;
    if (c == 'D')
        return 500;
    if (c == 'C')
        return 100;
    if (c == 'L')
        return 50;
    if (c == 'X')
        return 10;
    if (c == 'V')
        return 5;
    if (c == 'I')
        return 1;
    return 0;
}

编辑 1：

"IVX" 值的解释：

"...add values together except when a value (or runs of the SAME values) is followed by a greater value, you subtract the total of that run of values."

 IVX = 1 5 10
 if  5 > 1 then   5 - 1    = 4
 if 10 > 5 then  10 - 0(*) = 10 (*) we already have used V(5) before, so we discard it.

所以IVX的答案是14！

Answer 6

所以，没有人注意到我的暗示。那我也试试我不会讨论 "IVX"- 这件事，因为我认为这是一个语法错误。

int romanToInt( String s ){
    int total = 0;
    int pivot = 0;

    for( int i = s.length()-1; i >= 0; i--){ // We start at the **end**
        int current = valueOfRoman((s.charAt(i));
        if( current >= pivot ){ // We will have at least "I", so it **will** be > pivot for 1st char.
            pivot = current; 
            total += pivot;
        }else{
            total -= current;
        }
    }
    return total;
}

让我们看看：IIX

i    char    value    total    pivot   ->   total   pivot
2     X        10       0        0      >      10      10
1     I         1      10       10      <       9      10
0     I         1       9       10      <       8      10

MCCMIIX

i    char    value    total    pivot   ->   total   pivot
6     X        10       0        0     >       10      10
5     I         1      10       10     <        9      10
4     I         1       9       10     <        8      10
3     M      1000       8       10     >     1008    1000
2     C       100    1008     1000     <      908    1000
1     C       100     908     1000     <      808    1000
0     M      1000     808     1000     =     1808    1000

为简洁起见，该方法省略了输入验证。我假设所有输入都已检查并且仅包含根据 "the rules".

允许的字符

罗马整数 - 但使用 "different" 罗马数字系统

Roman to Integer - But using a "different" Roman number system

java

string

algorithm

roman-numerals